2001/??/??

パズルを解こう！

次のようなパズルを解いてみましょう。

おのおのの□の中に四則演算の記号（＋−×÷）のいずれかをいれて 次式が成り立つようにしなさい：

1□2□3□4□5□6□7□8□9□10=100

この問題は次のようなスクリプトで解くことができます。 行番号は説明のために付けてあるものです。

puzzle01.pl

 1: #!/usr/bin/perl
 2: #
 3: # 1□2□3□4□5□6□7□8□9□10=100
 4: #
 5: 
 6: @ind = (0,0,0,0,0,0,0,0,0,0);
 7: 
 8: @op = ('+', '-', '*', '/');
 9: # 0:+, 1:-, 2:*, 3:/
10: 
11: do {
12:     $x = '';
13:     for ($j=1; $j<=9; $j++) {
14:         $x .= "$j $op[$ind[$j]] ";
15:     }
16:     $x .= "10";
17: 
18:     $y = eval($x);
19:     if ($y > 99.999 && $y < 100.001) { print "$x = $y\n"; }
20: 
21:     $i = 9; $s = $ind[$i] + 1;
22:     while ($s > 3) {
23:         $ind[$i] = 0; $i--; $s = $ind[$i] + 1;
24:     }
25:     $ind[$i] = $s;
26: 
27: } while ($ind[0] < 1);

このスクリプトを実行してみましょう： 

I:\www>jperl puzzle01.pl
1 + 2 + 3 + 4 + 5 - 6 - 7 + 8 + 9 * 10 = 100
1 + 2 + 3 + 4 - 5 + 6 + 7 + 8 * 9 + 10 = 100
1 + 2 + 3 + 4 - 5 + 6 + 7 - 8 + 9 * 10 = 100
..............
..............
..............
1 / 2 - 3 / 4 + 5 + 6 * 7 / 8 + 9 * 10 = 100
1 / 2 * 3 * 4 - 5 - 6 + 7 + 8 + 9 * 10 = 100
1 / 2 / 3 - 4 + 5 / 6 * 7 + 8 + 9 * 10 = 100

ちょっと時間がかかるかもしれません。辛抱して待つ間にスクリプトの 勉強をしましょう。

□は９個あります。＋−×÷の４種類の記号をこの９個の□にいれるやり方は 49通りあります。これらのすべてに対して左辺の値が100になるか どうかを調べ、100になるときだけ画面に出力するようにすればいいわけです。 さて49通りあるやり方をどういう順で試していけばいいでしょうか。

そこで＋−×÷の４つの記号に数字の0123を対応させることにします。 ４進数で９桁の数を考えます。そして１の位の数字が右端の□にはいる 記号を表し、４の位の数字が右から２番目の記号を表し、……というように 数と記号の入れ方の対応をつけます。例えば

102302103
−＋×÷＋×−＋÷

と考えます。したがってこの場合の左辺は

1−2＋3×4÷5＋6×7−8＋9÷10

になります。これは100になっていませんね。４進数の数は0から始めて 1ずつ増やしていき、10桁に達したらやめるということにしましょう。 


 1: #!/usr/bin/perl
 2: #
 3: # 1□2□3□4□5□6□7□8□9□10=100
 4: #
 5:

まず最初の５行はコメントおよび空白行ですからまだ何も起きていません。 


 6: @ind = (0,0,0,0,0,0,0,0,0,0);
 7: 
 8: @op = ('+', '-', '*', '/');
 9: # 0:+, 1:-, 2:*, 3:/
10:

６行目で、４進数を表すための配列 @ind を用意しています。 要素は１０桁分用意してあります。初期値はどの桁も０です。 次に８行目で@opという配列を用意して、 ＋−×÷の４つの記号を数字の0123に対応させています： 


11: do {
12:     $x = '';
.........
.........
25:     $ind[$i] = $s;
26: 
27: } while ($ind[0] < 1);

ここが中心部分です。先程の４進数を１ずつ増やしながら、１０桁の数字になるまで、 １２行目から２６行目までの内容を繰り返し実行します。 


12:     $x = '';
13:     for ($j=1; $j<=9; $j++) {
14:         $x .= "$j $op[$ind[$j]] ";
15:     }
16:     $x .= "10";
17:

ここでは、１から１０までの数と与えられた９桁以下の４進数に対応する記号を 交互に並べて等式の左辺を表す文字列 $x を作っています。 $x は最初は空の文字列です(１２行目)。次に１から順に数字とそれに続く記号を 追加しています(１３行目から１５行目)。最後に１０を付け足します(１６行目)。 


18:     $y = eval($x);
19:     if ($y > 99.999 && $y < 100.001) { print "$x = $y\n"; }
20:

上で作った文字列 $x を数式と解釈して値を計算し、その値を変数 $y に格納します(１８行目)。 $y の値が 100 に等しければ、該当する等式を出力します(１９行目)。 割り算がはいるので計算誤差により必ずしも正確な値が出てくるとは限らないので $y が 100 であるかどうかの判定には少し余裕を持たせています。 誤差の見積もりをきちんとしていないので必ずしも正しい解がもとまるかどうか怪しいです。気になる人は気にしてみて下さい。 


21:     $i = 9; $s = $ind[$i] + 1;
22:     while ($s > 3) {
23:         $ind[$i] = 0; $i--; $s = $ind[$i] + 1;
24:     }
25:     $ind[$i] = $s;
26:

ここでは配列 @ind に対応する４進数の数字が１だけ大きくします。 まず臨時に１の位の数 $ind[9] を1だけ増やし、その値を $s という変数に 格納します。もしこれが1, 2, 3 ならそのままそれを新しい１の位にすればよいのですが、 運悪く4になった場合は繰り上げなければなりません：$ind[9] は 0 にし、 $ind[8] に 1 を加えた値を考え、それを新たに $s に代入します。 もしこれが1, 2, 3 ならばそのままそれを新しい４の位にすればよいのですが、 運悪く 4 になった場合は繰り上げを行わなければなりません。 このような操作を必要に応じて繰り返していけば、いつかは繰り上げなくても よいところまできます。 上では２２行目から２４行目が繰り上げの処理を行っています。

以上でこのスクリプトの解説を終わりにします。なお、このスクリプトは 奥村晴彦著「アルゴリズム事典」（技術評論社）に掲載されているＣ言語ソースを Perl に書き換えたものです。



●今回の課題

問題を少し変えてみましょう。

おのおのの□の中に＋−のいずれかをいれて次式が成り立つようにしなさい：

1□2□3□4□5□6□7□8=10

各自のWebページに自分の書いたスクリプト、およびそれを実行して 出力した解答を掲載して下さい。掲載の仕方は自由とします。