アルゴリズムが聞きたいのか、プログラムが聞きたいのか分かりませんが、小町算を知らなかったので、少し調べてみました。
小町算-Wikipedia
小町算(こまちざん)は数の遊びである数学パズルの一種。1□2□3□4□5□6□7□8□9 = 100 という数式の□の中に、+,-,×,÷,空白 のいずれかを一つずつ入れて正しい数式を完成させるというものである。方程式などは解法が研究されており、虫食い算、覆面算も繰り上がりなどを手がかりに答えを絞り込んでいけるが、小町算はそのような解法はなく、ひたすらトライ&エラーで答えを探すしかない。
こちらの変則型の質問(数字の並び方を固定せず(←指摘があり追記しました。)、解を0とする)と理解しました。
ひたすら トライ&エラー ということなので、全組み合わせをループで回すことになります。ただし、ループとしては、外側にある数字を使用してはイケない制限が発生するので、それをスキップする機構を組み込みます。
四則演算とは、そのまま4通りなので、ループで回せばイイです。
===追記===
*ルールを勘違いしていました。計算方法は四則演算だけでなく、空白を含むのですね^^;
回答を修正しました。
多分、再帰で全部記述することもできる気もしますが、ちょっと頭が追いつかなくなったので、大きく3部分に分けました。
otn さんの回答見ると、Ruby だと create_number
と operation_combination
に似た内容が関数化されてるんですかね。羨ましい。。。
ざっくりと解説すると
create_number
与えられた配列に対して、重複のない組み合わせの数字を作成
すでに使用した数字はスキップし、それ以外は桁数になるまで再帰することで作成しています。
こんな数字が並びます。
123456789,
123456798,
operation_combination
+-/空白 の組み合わせを与えられた桁数分用意
+- /空白 を 1-5 の数字に置き換えて考えています。
1-5 を桁数分の組み合わせで作成します。
こんな数字が並びます。
111111111,
111111112,
意味は
+++++++++,
++++++++-,
です。
get_sum
ぐるぐる計算するところ
create_number と operation_combination で作成した配列を空になるまで計算しています。
今回は、値の正当性を確認したかったので、0 のカウントとせず、式と合計値を表示するサンプルにしています。
結局、eval のお世話になってしまいました^^;
面白かったです。
php
1 <?php
2 class Komachi {
3 private $base_array ;
4 private $count_base_array ;
5 private $result_array = [ ] ;
6 private $base_op_array = [ 1 , 2 , 3 , 4 , 5 ] ; //1:+,2:-,3:*,4:/,5:''
7 private $count_base_op_array = 5 ;
8 private $combination_op_array = [ ] ;
9
10 public function __construct ( $base_array ) {
11 $this -> base_array = $base_array ;
12 $this -> count_base_array = count ( $base_array ) ;
13 }
14
15 public function result ( ) {
16 return ( $this -> result_array ) ;
17 }
18
19 public function combination_op_array ( ) {
20 return ( $this -> combination_op_array ) ;
21 }
22
23 public function create_number ( $org_number , $count ) {
24 for ( $i = 0 ; $i < $this -> count_base_array ; $i ++ ) {
25 $org_number_array = str_split ( $org_number , 1 ) ;
26 if ( in_array ( $this -> base_array [ $i ] , $org_number_array ) ) {
27 continue ;
28 }
29 $new_number = $org_number * 10 + $this -> base_array [ $i ] ;
30 if ( $count === $this -> count_base_array ) {
31 $this -> result_array [ ] = $new_number ;
32 continue ;
33 }
34 $this -> create_number ( $new_number , $count + 1 ) ;
35 }
36 }
37
38 public function operation_combination ( $org_number , $count ) {
39 for ( $i = 0 ; $i < $this -> count_base_op_array ; $i ++ ) {
40 $new_number = $org_number * 10 + $this -> base_op_array [ $i ] ;
41 if ( $count === $this -> count_base_array - 1 ) {
42 $this -> combination_op_array [ ] = $new_number ;
43 continue ;
44 }
45 $this -> operation_combination ( $new_number , $count + 1 ) ;
46 }
47 }
48
49 public function get_sum ( ) {
50 $this -> create_number ( 0 , 1 ) ;
51 $this -> operation_combination ( 0 , 1 ) ;
52 foreach ( $this -> result_array as $num ) {
53 $num_array = str_split ( $num , 1 ) ;
54 foreach ( $this -> combination_op_array as $combination_op ) {
55 $op_array = str_split ( $combination_op , 1 ) ;
56 for ( $i = 0 ; $i < $this -> count_base_array ; $i ++ ) {
57 if ( $i === 0 ) {
58 $sum = $num_array [ $i ] ;
59 continue ;
60 }
61 if ( ( int ) $op_array [ $i - 1 ] === 1 ) {
62 $sum = $sum . '+' . $num_array [ $i ] ;
63 }
64 if ( ( int ) $op_array [ $i - 1 ] === 2 ) {
65 $sum = $sum . '-' . $num_array [ $i ] ;
66 }
67 if ( ( int ) $op_array [ $i - 1 ] === 3 ) {
68 $sum = $sum . '*' . $num_array [ $i ] ;
69 }
70 if ( ( int ) $op_array [ $i - 1 ] === 4 ) {
71 $sum = $sum . '/' . $num_array [ $i ] ;
72 }
73 if ( ( int ) $op_array [ $i - 1 ] === 5 ) {
74 $sum = $sum . $num_array [ $i ] ;
75 }
76 }
77 $result = eval ( "return { $sum } ;" ) ;
78 echo $sum . ' = ' . $result . PHP_EOL ;
79 }
80 }
81 }
82 }
83
84 // $tmp = new Komachi([1,2,3,4,5,6,7,8,9]);
85 $komachi = new Komachi ( [ 1 , 2 , 3 ] ) ;
86 $komachi -> get_sum ( ) ;
以下、[1,2,3] の結果です。
1+2+3 = 6
1+2-3 = 0
1+2*3 = 7
1+2/3 = 1.6666666666667
1+23 = 24
1-2+3 = 2
1-2-3 = -4
1-2*3 = -5
1-2/3 = 0.33333333333333
1-23 = -22
1*2+3 = 5
1*2-3 = -1
1*2*3 = 6
1*2/3 = 0.66666666666667
1*23 = 23
1/2+3 = 3.5
1/2-3 = -2.5
1/2*3 = 1.5
1/2/3 = 0.16666666666667
1/23 = 0.043478260869565
12+3 = 15
12-3 = 9
12*3 = 36
12/3 = 4
123 = 123
1+3+2 = 6
1+3-2 = 2
1+3*2 = 7
1+3/2 = 2.5
1+32 = 33
1-3+2 = 0
1-3-2 = -4
1-3*2 = -5
1-3/2 = -0.5
1-32 = -31
1*3+2 = 5
1*3-2 = 1
1*3*2 = 6
1*3/2 = 1.5
1*32 = 32
1/3+2 = 2.3333333333333
1/3-2 = -1.6666666666667
1/3*2 = 0.66666666666667
1/3/2 = 0.16666666666667
1/32 = 0.03125
13+2 = 15
13-2 = 11
13*2 = 26
13/2 = 6.5
132 = 132
2+1+3 = 6
2+1-3 = 0
2+1*3 = 5
2+1/3 = 2.3333333333333
2+13 = 15
2-1+3 = 4
2-1-3 = -2
2-1*3 = -1
2-1/3 = 1.6666666666667
2-13 = -11
2*1+3 = 5
2*1-3 = -1
2*1*3 = 6
2*1/3 = 0.66666666666667
2*13 = 26
2/1+3 = 5
2/1-3 = -1
2/1*3 = 6
2/1/3 = 0.66666666666667
2/13 = 0.15384615384615
21+3 = 24
21-3 = 18
21*3 = 63
21/3 = 7
213 = 213
2+3+1 = 6
2+3-1 = 4
2+3*1 = 5
2+3/1 = 5
2+31 = 33
2-3+1 = 0
2-3-1 = -2
2-3*1 = -1
2-3/1 = -1
2-31 = -29
2*3+1 = 7
2*3-1 = 5
2*3*1 = 6
2*3/1 = 6
2*31 = 62
2/3+1 = 1.6666666666667
2/3-1 = -0.33333333333333
2/3*1 = 0.66666666666667
2/3/1 = 0.66666666666667
2/31 = 0.064516129032258
23+1 = 24
23-1 = 22
23*1 = 23
23/1 = 23
231 = 231
3+1+2 = 6
3+1-2 = 2
3+1*2 = 5
3+1/2 = 3.5
3+12 = 15
3-1+2 = 4
3-1-2 = 0
3-1*2 = 1
3-1/2 = 2.5
3-12 = -9
3*1+2 = 5
3*1-2 = 1
3*1*2 = 6
3*1/2 = 1.5
3*12 = 36
3/1+2 = 5
3/1-2 = 1
3/1*2 = 6
3/1/2 = 1.5
3/12 = 0.25
31+2 = 33
31-2 = 29
31*2 = 62
31/2 = 15.5
312 = 312
3+2+1 = 6
3+2-1 = 4
3+2*1 = 5
3+2/1 = 5
3+21 = 24
3-2+1 = 2
3-2-1 = 0
3-2*1 = 1
3-2/1 = 1
3-21 = -18
3*2+1 = 7
3*2-1 = 5
3*2*1 = 6
3*2/1 = 6
3*21 = 63
3/2+1 = 2.5
3/2-1 = 0.5
3/2*1 = 1.5
3/2/1 = 1.5
3/21 = 0.14285714285714
32+1 = 33
32-1 = 31
32*1 = 32
32/1 = 32
321 = 321
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2017/02/17 09:33
2017/02/17 12:29