小町算
1□2□3□4□5□6□7□8□9 = 100 という数式の□の中に、+, -, 空白のいずれかを入れて、正しい数式を完成させるプログラムです。
using System; using System.Collections.Generic; using System.Linq; class Program { const int EMPTY = -1; // 空白 const int ADD = -2; // 足し算 const int SUB = -3; // 引き算 static int Eval(int[] xs) { // EMPTY を取り除く。 var expr = new List<int>(); expr.Add(xs[0]); for (int i = 2; i < xs.Length; i += 2) { if (xs[i-1] == EMPTY) { // 数字を連結する expr[expr.Count-1] = 10 * expr[expr.Count-1] + xs[i]; } else { expr.Add(xs[i-1]); expr.Add(xs[i]); } } // 式を評価する int ret = expr[0]; for (int i = 2; i < expr.Count; i += 2) { switch (expr[i-1]) { case ADD: ret += expr[i]; break; case SUB: ret -= expr[i]; break; default: throw new InvalidOperationException(); } } return ret; } static void Show(int[] xs) { var ss = new List<string>(); foreach (int x in xs) { if (x == EMPTY) continue; if (x == ADD) ss.Add(" + "); else if (x == SUB) ss.Add(" - "); else ss.Add(x.ToString()); } Console.WriteLine(string.Join("", ss)); } static void Calc(int p, int[] xs, int k) { if (p == xs.Length) { if (Eval(xs) == 100) { Show(xs); } return; } foreach (int op in new[] { EMPTY, ADD, SUB }) { xs[p] = op; xs[p+1] = k; Calc(p+2, xs, k+1); } } static void Main() { var xs = new int[9+8]; // 数値が 9 つと、演算子(+, -, 空白)が 8 つ。 xs[0] = 1; Calc(1, xs, 2); } }
実行結果です。
123 + 45 - 67 + 8 - 9 123 + 4 - 5 + 67 - 89 123 - 45 - 67 + 89 123 - 4 - 5 - 6 - 7 + 8 - 9 12 + 3 + 4 + 5 - 6 - 7 + 89 12 + 3 - 4 + 5 + 67 + 8 + 9 12 - 3 - 4 + 5 - 6 + 7 + 89 1 + 23 - 4 + 56 + 7 + 8 + 9 1 + 23 - 4 + 5 + 6 + 78 - 9 1 + 2 + 34 - 5 + 67 - 8 + 9 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9