Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* We are given numbers N and M and the following operations:
- N = N+1
- N = N+2
- N = N*2
- Write a program that finds the shortest sequence of operations from the list above that starts from N and finishes in M. Hint: use a queue.
- Example: N = 5, M = 16
- Sequence: 5 -> 7 -> 8 -> 16 */
- class Node<T>
- {
- internal T Value { get; set; }
- private Node<T> parent;
- internal Node<T> Parent
- {
- get { return parent; }
- set { parent = value; }
- }
- public Node()
- {
- }
- public Node(T value)
- {
- this.Value = value;
- }
- }
- class Program
- {
- static int m = 1225;
- static int n = 5;
- private static int GetM()
- {
- Console.Write("Input M: ");
- return int.Parse(Console.ReadLine());
- }
- private static int GetN()
- {
- Console.Write("Input N: ");
- return int.Parse(Console.ReadLine());
- }
- private static Node<int> FindElement(Node<int> element)
- {
- Queue<Node<int>> elementsQueue = new Queue<Node<int>>();
- elementsQueue.Enqueue(element);
- while (elementsQueue.Count > 0)
- {
- Node<int> currentElement = elementsQueue.Dequeue();
- if (currentElement.Value == m)
- {
- return currentElement;
- }
- else if (currentElement.Value < m)
- {
- Node<int> nextElement = new Node<int>(currentElement.Value + 1);
- nextElement.Parent = currentElement;
- elementsQueue.Enqueue(nextElement);
- nextElement = new Node<int>(currentElement.Value + 2);
- nextElement.Parent = currentElement;
- elementsQueue.Enqueue(nextElement);
- nextElement = new Node<int>(currentElement.Value * 2);
- nextElement.Parent = currentElement;
- elementsQueue.Enqueue(nextElement);
- }
- }
- throw new ArgumentException("The searched element can not be reached.");
- }
- private static Node<int> PrintChain(int n, Node<int> searchedElement)
- {
- Stack<int> result = new Stack<int>();
- while (searchedElement.Parent != null)
- {
- result.Push(searchedElement.Value);
- searchedElement = searchedElement.Parent;
- }
- result.Push(n);
- while (result.Count > 0)
- {
- if (result.Count != 1)
- {
- Console.Write("{0} -> ", result.Pop());
- }
- else
- {
- Console.WriteLine("{0}", result.Pop());
- }
- }
- return searchedElement;
- }
- static void Main(string[] args)
- {
- //n = GetN();
- //m = GetM();
- bool elementReached = false;
- Node<int> root = new Node<int>(n);
- Node<int> searchedElement = new Node<int>();
- try
- {
- searchedElement = FindElement(root);
- elementReached = true;
- }
- catch (ArgumentException e)
- {
- Console.WriteLine(e.Message);
- }
- if (elementReached)
- {
- searchedElement = PrintChain(n, searchedElement);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement