５つの数字11,111,1111,11111,111111と演算子＋,−,×,÷，それに括弧を組み合わせて計算結果が1になる計算式を求める。
(2005.11.11)新聞の答えを見ると四則演算を一つずつ使わなくても良いみたいだ。
私は一つずつ使うと読んだんだけど新聞の答えはそうなっていない。
例えば，以下のような計算式があるとする。
ａ＋ｂ×ｃ−ｄ÷ｅ
これに括弧を付けると，答えが変わってくる。
（ａ＋ｂ）×ｃ÷ｄ−ｅ
（ａ＋ｂ×ｃ）÷ｄ−ｅ
問題では括弧の数を規定していないので，
（ａ＋ｂ×ｃ）÷（ｄ−ｅ）
なんてのも考えられる。
括弧の位置と数を含めて虱潰そうとするとちょっと難しい。
そこで括弧を抜いた演算を考えることにした。
逆ポーランド記法を使った演算式を考える。これを閃いた時はちょっとうれしかった。
ａ，ｂ，ｃ，ｄ，ｅ，＋，−，×，÷の９個の数字と演算子を組み合わせて，それを逆ポーランド記法の計算式と見なす。
組合せは９！(362880)通りある。
計算が出来ない場合はエラー。
計算が出来る場合は最後にスタックに残ったのが答え。
整数演算で済ませるために，分母と分子を分けて記録していく。
以上の方針で以下のようなコードになる。
#include "puzutl.h"
YesNo used[9]; //
int numop[9] = {/*0〜4に5個の数字を割り当てる*/ 11,111,1111,11111,111111, /*以降演算子*/ 1/*＋*/,2/*−*/,3/*×*/,4/*÷*/};
int cal[9];
cstring opstr[] = { "NA", "＋", "−", "×", "÷"};
void calcRPN( int cal[])
{
// cal[] を逆ポーランド記法で数字と演算子が入っていると仮定し計算する。
// エラーがあれば計算を打ち切り，エラーが無ければ結果を計算する。
int bunsi[9], bunbo[9], sp = 0;
for( int i=0; i< 9; i++) {
if( cal[i] > 10) { // 数字なのでスタックに積む
…省略…
}
else if( sp > 1) { // 演算子なので計算する。但し数字が２つあることが前提。
…省略…
}
else {
// 計算不能
return;
}
}
if( bunsi[0] == bunbo[0]) { // ( 分子 == 分母 ) ⇒ １
// 計算式を出力する。式は逆ポーランドのままなのでちょっと読みにくい。
for( int i=0; i< 9; i++) {
if( cal[i] > 10) ps( "%d ", cal[i]);
else ps( "%s ", opstr[cal[i]]);
}
ps( "\n");
}
}
int main( int argc, cstring argv[])
{
for( int a=0; a< 9; a++) {
used[a] = YES;
for( int b=0; b< 9; b++) {
if( used[b]) continue;
used[b] = YES;
for( int c=0; c< 9; c++) {
if( used[c]) continue;
used[c] = YES;
for( int d=0; d< 9; d++) {
if( used[d]) continue;
used[d] = YES;
for( int e=0; e< 9; e++) {
if( used[e]) continue;
used[e] = YES;
for( int f=0; f< 9; f++) {
if( used[f]) continue;
used[f] = YES;
for( int g=0; g< 9; g++) {
if( used[g]) continue;
used[g] = YES;
for( int h=0; h< 9; h++) {
if( used[h]) continue;
used[h] = YES;
for( int i=0; i< 9; i++) {
if( used[i]) continue;
used[i] = YES;
// 演算式をスタックに積んで計算する。
cal[0] = numop[a];
cal[1] = numop[b];
cal[2] = numop[c];
cal[3] = numop[d];
cal[4] = numop[e];
cal[5] = numop[f];
cal[6] = numop[g];
cal[7] = numop[h];
cal[8] = numop[i];
// 実際に計算し結果が1になるものが解
calcRPN( cal);
used[i] = NO;
}
used[h] = NO;
}
used[g] = NO;
}
used[f] = NO;
}
used[e] = NO;
}
used[d] = NO;
}
used[c] = NO;
}
used[b] = NO;
}
used[a] = NO;
}
return 0;
}
出力は逆ポーランド記法のままなのでちょっと見づらい。
答えは4件出力されるが，式自体は同じなので実質1件。
順調に48時間ダイエットを実行中。近所の子供に暗がりの中で会ったら，
「なーんだ，若くなったように見えたと思ったけど，近くで見たら大したことないじゃん」と言われてしまった。
痩せるとちょっと若く見えるのかな？
解速度
即