プログラムの実行結果は以下の通り。
NN N − N ÷
逆ポーランド記法のままだと判りづらいので判りやすく表示すると以下の演算式になる。
( NN - N ) ÷ N
プログラムのソースは以下の通り。
#include "puzutl.h"
int val = 0; // 後で1〜9の数字を割り当てる
int numop[6] = {/*0に数字を割り当てる*/ val, 0/*前後の数字を連結*/, /*以降演算子*/ -1/*＋*/,-2/*−*/,-3/*×*/,-4/*÷*/};
int cal[9];
cstring opstr[] = { "NA", "＋", "−", "×", "÷"};
YesNo calcRPN( int cal[], int n)
{
// cal[] を逆ポーランド記法で数字と演算子が入っていると仮定し計算する。
// エラーがあれば計算を打ち切り，エラーが無ければ結果を計算する。
int bunsi[9], bunbo[9], sp = 0;
for( int i=0; i< n; i++) {
if( cal[i] > 0) { // 数字なのでスタックに積む
bunsi[sp] = cal[i];
bunbo[sp] = 1;
sp++;
}
else if( cal[i] == 0) { // ここに来る前に連結は処理しているはず
pe( "Program Error\n");
return NO;
}
else if( sp > 1) { // 演算子なので計算する。但し数字が２つあることが前提。
int op = cal[i];
int m = bunsi[sp-2], n = bunbo[sp-2]; // m/n op t/s
int t = bunsi[sp-1], s = bunbo[sp-1];
if( op == -1/*＋*/) { --sp; bunsi[sp-1] = m*s + n*t; bunbo[sp-1] = s*n;}
if( op == -2/*−*/) { --sp; bunsi[sp-1] = m*s - n*t; bunbo[sp-1] = s*n;}
if( op == -3/*×*/) { --sp; bunsi[sp-1] = m*t ; bunbo[sp-1] = s*n;}
if( op == -4/*÷*/) { --sp; bunsi[sp-1] = m*s ; bunbo[sp-1] = n*t;}
}
else {
// 計算不能
return NO;
}
}
if( sp == 1 && bunsi[0] != 0 && bunsi[0] == bunbo[0]*10) { // ( 分子 == 分母*10 ) ⇒ 10
return YES; // 計算結果が10になる場合だけ
}
return NO; // それ以外はダメ
}
int main( int argc, cstring argv[])
{
set<string> match[10]; // 数字が1〜9の場合の計算式,計算結果が10になったら計算式を記憶する。
for( int val=1; val< 10; val++) { // 1〜9の場合の全て計算してみる
numop[0] = val; // 全ての数字で計算結果が10になることが必要
for( int a=0; a< 1; a++) { // 最初は数字でなければ計算式が成り立たない
for( int b=0; b< 6; b++) {
if( numop[b] == 0 && numop[a] < 0) continue; // 前が数字でなければ連結できない
for( int c=0; c< 6; c++) {
if( numop[b] == 0 && numop[c] < 0) continue; // 前が連結なら後ろは数字でなければならない。
if( numop[c] == 0 && numop[b] < 0) continue; // 前が数字でなければ連結できない
for( int d=0; d< 6; d++) {
if( numop[c] == 0 && numop[d] < 0) continue; // 前が連結なら後ろは数字でなければならない。
if( numop[d] == 0 && numop[c] < 0) continue; // 前が数字でなければ連結できない
for( int e=0; e< 6; e++) {
if( numop[d] == 0 && numop[e] < 0) continue; // 前が連結なら後ろは数字でなければならない。
if( numop[e] == 0 && numop[d] < 0) continue; // 前が数字でなければ連結できない
for( int f=0; f< 6; f++) {
if( numop[e] == 0 && numop[f] < 0) continue; // 前が連結なら後ろは数字でなければならない。
if( numop[f] == 0 && numop[e] < 0) continue; // 前が数字でなければ連結できない
for( int g=0; g< 6; g++) {
if( numop[f] == 0 && numop[g] < 0) continue; // 前が連結なら後ろは数字でなければならない。
if( numop[g] == 0) continue; // 最後に連結は出来ない
// 演算式をスタックに積んで計算する。
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];
// 数字を連結している箇所があれば纏める
int n = 0;
for( int p=0; p< 7; p++) {
if( cal[p] > 0) cal[n++] = cal[p];
else if( cal[p] == 0) { // 数字を連結する
cal[n-1] = cal[n-1]*10 + cal[++p];
}
else cal[n++] = cal[p];
}
// 実際に計算し結果が10になるものが解候補
if( calcRPN( cal, n)) {
string s = "";
for( int p=0; p< n; p++) {
if( cal[p] > 0) {
int w = cal[p];
while( w > 0) {
s += "N"; // 1〜9まで同じ式になるように具体的数字で記録しない
w /= 10;
}
}
else {
s += opstr[-cal[p]];
}
s += " ";
}
match[val].insert(s);
}
}
}
}
}
}
}
}
}
// 全ての数字(1〜9)で計算結果が10になったものが記録されているはず。
set<string>::iterator ite;
for( ite=match[1].begin(); ite != match[1].end(); ite++) { // 1の場合の計算式全てを調べ
YesNo ynOK = YES;
for( int i=2; i< 10; i++) { // 2〜9でも同じ計算式があれば解
if( match[i].find(*ite) == match[i].end()) {
ynOK = NO; // 同じ計算式が無かった
break;
}
}
if( ynOK) { // 1〜9の場合で全て同じ計算式で結果が10になった
ps( "%s\n", (*ite).c_str()); // この計算式が求める答え
}
}
return 0;
}