【問題】
1～9までの数字が並んでいます。
1 2 3 4 5 6 7 8 9
数字の間に【+】や【-】を入れて、答えが100になるようにして下さい。
1＋2＋3・・・のような形だけでなく、12＋3のような形もありです。
答えは複数あります。
という問題があったので、プログラミングで答えを探してみることにしました。
考え方
数字が 1 2 3 4 5 6 7 8 9 と並んでいるので、各数字の前に＋または－の記号が付くか付かないかを考えます。「＋」、「－」、何もないの3通りが9個なので、全部で3の9乗（＝ 19,683）通り考えられます。あとはそれぞれを計算して100になるかどうかを調べます。
まず「＋」、「－」、スペースを9個選んで文字列を作ります。順列を作ればよいということになります。
これでよさそうです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
List<string> permutation = GetPermutation(new string[] { "+", "-", " ", }); List<string> GetPermutation(string [] strings) { List<string> vs = new List<string>(); vs.Add(""); for(int i=0; i<9; i++) { List<string> newvs = new List<string>(); foreach(string str in vs) { foreach(string s in strings) newvs.Add(str + s); } vs = newvs; } return vs; } |
次に得られた9文字の文字列と123456789を組み合わせて計算式をつくります。以下のようにすれば stringsにすべての計算式を格納することができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
List<string> permutation = GetPermutation(new string[] { "+", "-", " ", }); List<string> strings = new List<string>(); foreach(string str in permutation) { string string1 = ""; for(int i=0; i<9; i++) { string1 += str[i] + (i+1).ToString(); } string1 = string1.Replace(" ", ""); if(string1[0].ToString() == "+") continue; strings.Add(string1); } |
次に生成された 123-45-67＋89 のような計算式を計算する必要がありますが、これでいいのではないでしょうか？
文字列を先頭から1文字ずつ取得していき、符号をみつけるまで文字列をつなぎ合わせていきます。符号をみつけたら最初に見つけていた符号が＋なら足し、－なら引きます。実際には足すべきものと引くべきものをそれぞれ別のリストに格納し、最後にそれぞれの総和を計算します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
int Calc(string str) { int len = str.Length; List<int> plus = new List<int>(); List<int> minus = new List<int>(); bool isPlus = true; string value = ""; for(int i=0; i<len; i++) { string sub = str.Substring(i, 1); if(sub == "+" || sub == "-") { if(value != "") { int k = int.Parse(value); value = ""; if(isPlus) plus.Add(k); else minus.Add(k); } } if(sub == "+") { isPlus = true; } else if(sub == "-") { isPlus = false; } else { value += sub; } } if(value != "") { int k = int.Parse(value); if(isPlus) plus.Add(k); else minus.Add(k); } return plus.Sum() - minus.Sum(); } |
ボタンがクリックされたら以下の処理をすれば、答えが100になる数式をゲットすることができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
private void button1_Click(object sender, EventArgs e) { List<string> permutation = GetPermutation(new string[] { "+", "-", " ", }); List<string> strings = new List<string>(); foreach(string str in permutation) { string string1 = ""; for(int i=0; i<9; i++) { string1 += str[i] + (i+1).ToString(); } string1 = string1.Replace(" ", ""); if(string1[0].ToString() == "+") continue; strings.Add(string1); } List<string> ret = new List<string>(); foreach(string str in strings) { if(Calc(str) == 100) { ret.Add(str); } } richTextBox1.Text = String.Join("\n", ret); } |
実行結果
実行結果は以下のとおり。全部で12種類あります。
-1+2-3+4+5+6+78+9
1+2+3-4+5+6+78+9
1+2+34-5+67-8+9
1+23-4+5+6+78-9
1+23-4+56+7+8+9
12+3+4+5-6-7+89
12+3-4+5+67+8+9
12-3-4+5-6+7+89
123+4-5+67-89
123+45-67+8-9
123-4-5-6-7+8-9
123-45-67+89
100ではなく別の数にしていろいろやってみるとおもしろいかも。
