Заданы 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]); } } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д