Заданы 6 цифр и число. Используя скобки и бинарные арифметические операции +,-,*,/, получить заданное число - C#

Узнай цену своей работы

Формулировка задачи:

помогите написать программу на C#, как-нибудь отблагодарю Заданы 6 цифр и число. Используя скобки и бинарные арифметические операции +,-,*,/, получить заданное число, результатом функции должно быть арифметическое выражение в инфиксной форме. Если ответов несколько, вывести а)любой из них б) все ,(Примечание: деление разрешается использовать лишь в том случае, если частное будет целым) пример: (f(8 9 4 3 9 2) 100) (89*(4-3)+9+2) или (89+(4-3)*9+2) или (8*(9+4)-3+9-2)

Решение задачи: «Заданы 6 цифр и число. Используя скобки и бинарные арифметические операции +,-,*,/, получить заданное число»

textual
Листинг программы
using System;
using System.Collections.Generic;
 
namespace ConsoleApplication175
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            var counter = 0;
            var calc = new Solver();
            var list = calc.Solve(100, new int[] {8, 9, 4, 3, 9, 2});
            foreach (var solution in list)
            {
                Console.WriteLine(solution);
                counter++;
                if (counter >= 100)
                {
                    Console.WriteLine("Found 100 solutions. Continue? (y/n)");
                    switch ((char) Console.Read())
                    {
                        case 'y':
                        case 'Y':
                            continue;
                        default:
                            break;
                    }
                    counter = 0;
                }
            }
            Console.ReadLine();
        }
    }
 
    class Solver
    {
        public IEnumerable<string> Solve(int target, params int[] arguments)
        {
            //генерируем всевозможные перестановки аргументов
            foreach (var permutation in GetPermutations(arguments, 0, arguments.Length - 1))
            //генерируем всевозможные объединения цифр в числа
            foreach (var union in GetUnions(arguments))
            {
                var calc = new Calculator(union);
                //генерируем всевозможные операции над аргументами, вычисляем результат
                foreach (var res in calc.CalcVariants())
                    if (res == target)
                        yield return calc.ExpressionStack.Peek();
            }
        }
 
        IEnumerable<IList<int>> GetUnions(IList<int> arr)
        {
            var res = new List<int>();
            return GetUnions(arr, 0, res);
        }
 
        IEnumerable<IList<int>> GetUnions(IList<int> arr, int from, IList<int> res)
        {
            if (from >= arr.Count)
                yield return res;
 
            for(int i=from; i < arr.Count;i++)
            {
                res.Add(Union(arr, from, i));
                foreach (var r in GetUnions(arr, i + 1, res))
                    yield return r;
                res.RemoveAt(res.Count - 1);
            }
        }
 
        int Union(IList<int> arr, int from, int to)
        {
            var res = arr[from];
            for (int i = from + 1; i <= to; i++)
                res = Union(res, arr[i]);
 
            return res;
        }
 
        int Union(int a, int b)
        {
            if (b == 0)
                return a*10;
            return a*(int)Math.Pow(10, 1 + (int)Math.Log10(b)) + b;
        }
 
        IEnumerable<IList<int>> GetPermutations(IList<int> arr, int i, int n)
        {
            int j;
            if (i == n)
                yield return arr;
            else
            {
                for (j = i; j <= n; j++)
                {
                    Swap(arr, i, j);
                    foreach(var p in GetPermutations(arr, i + 1, n))
                        yield return p;
                    Swap(arr, i, j);
                }
            }
        }
 
        void Swap(IList<int> arr, int i, int j)
        {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
 
    class Calculator
    {
        public StackWithUndo<int> Stack = new StackWithUndo<int>();
        public StackWithUndo<string> ExpressionStack = new StackWithUndo<string>();
        public StackWithUndo<int> Arguments;
        public string Solution = "";
 
        private readonly Func<bool>[] AllowedOperations;
 
        public Calculator(IList<int> arguments)
        {
            Arguments = new StackWithUndo<int>(arguments);
            AllowedOperations = new Func<bool>[] { Up, Add, Sub, Mul, Div };
        }
 
        public IEnumerable<int> CalcVariants()
        {
            if (Stack.Count == 1)
                yield return Stack.Peek();
 
            var argState = Arguments.RememberState();
            var stackState = Stack.RememberState();
            var expressionState = ExpressionStack.RememberState();
            var s = Solution;
 
            foreach(var op in AllowedOperations)
            {
                if (op())
                    foreach (var res in CalcVariants())
                        yield return res;
 
                Stack.RestoreState(stackState);
                Arguments.RestoreState(argState);
                ExpressionStack.RestoreState(expressionState);
                Solution = s;
            }
        }
 
 
        bool Up()
        {
            if(Arguments.Count > 0)
            {
                var arg = Arguments.Pop();
                ExpressionStack.Push(arg.ToString());
                Stack.Push(arg);
                return true;
            }
 
            return false;
        }
 
        bool Add()
        {
            if (Stack.Count > 1)
            {
                var arg1 = Stack.Pop();
                var arg2 = Stack.Pop();
                ExpressionStack.Push(string.Format("({1}+{0})", ExpressionStack.Pop(), ExpressionStack.Pop()));
                Stack.Push(arg2 + arg1);
                return true;
            }
 
            return false;
        }
 
        bool Sub()
        {
            if (Stack.Count > 1)
            {
                var arg1 = Stack.Pop();
                var arg2 = Stack.Pop();
                ExpressionStack.Push(string.Format("({1}-{0})", ExpressionStack.Pop(), ExpressionStack.Pop()));
                Stack.Push(arg2 - arg1);
                return true;
            }
 
            return false;
        }
 
        bool Mul()
        {
            if (Stack.Count > 1)
            {
                var arg1 = Stack.Pop();
                var arg2 = Stack.Pop();
                ExpressionStack.Push(string.Format("{1}*{0}", ExpressionStack.Pop(), ExpressionStack.Pop()));
                Stack.Push(arg2 * arg1);
                return true;
            }
 
            return false;
        }
 
        bool Div()
        {
            if (Stack.Count > 1)
            {
                var arg1 = Stack.Pop();
                var arg2 = Stack.Pop();
                if (arg1 != 0 && (arg2 % arg1 == 0))
                {
                    ExpressionStack.Push(string.Format("{1}/{0}", ExpressionStack.Pop(), ExpressionStack.Pop()));
                    Stack.Push(arg2/arg1);
                    return true;
                }
                Stack.Push(arg2);
                Stack.Push(arg1);
            }
 
            return false;
        }
    }
 
    class StackWithUndo<T>: Stack<T>
    {
        public StackWithUndo()
        {
        }
 
        public StackWithUndo(IEnumerable<T> coll) : base(coll)
        {
        }
 
        public List<T> RememberState()
        {
            return new List<T>(this);
        }
 
        public void RestoreState(List<T> state)
        {
            base.Clear();
            for (int i = state.Count - 1; i >= 0;i--)
                base.Push(state[i]);
        }
    }
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

13   голосов , оценка 4.462 из 5
Похожие ответы