となるように□に適当な＋，−，×，÷を入れる。但し，＋は1個，−は3個，×は2個，÷は2個使用すること。
□の部分に＋，−，×，÷を割り当てる虱潰し問題。
数字の割り当て問題をコピーして利用する。
と見なし，a〜hに対し，0〜3の数を割り当てる。
0は＋，1:−，2:×，3:÷とする。虱潰すところは以下のようなコードになる。
int cnt[8] ; // ＋，−，×，÷の利用回数
int num[4] = { 1, 3, 2, 2}; // ＋，−，×，÷の最大出現可能回数
int main( int argc, cstring argv[])
{
int lcnt = 0;
for( int a=0; a< 4; a++) {
cnt[a]++;
for( int b=0; b< 4; b++) {
if( cnt[b] >= num[b]) continue;
cnt[b]++;
for( int c=0; c< 4; c++) {
if( cnt[c] >= num[c]) continue;
cnt[c]++;
for( int d=0; d< 4; d++) {
if( cnt[d] >= num[d]) continue;
cnt[d]++;
for( int e=0; e< 4; e++) {
if( cnt[e] >= num[e]) continue;
cnt[e]++;
for( int f=0; f< 4; f++) {
if( cnt[f] >= num[f]) continue;
cnt[f]++;
for( int g=0; g< 4; g++) {
if( cnt[g] >= num[g]) continue;
cnt[g]++;
for( int h=0; h< 4; h++) {
if( cnt[h] >= num[h]) continue;
cnt[h]++;
// ここで １ a ２ b ３ c ４ d ５ e ６ f ７ g ８ h ９ を計算する。
lcnt++; // ここに制約処理を書く
cnt[h]--;
}
cnt[g]--;
}
cnt[f]--;
}
cnt[e]--;
}
cnt[d]--;
}
cnt[c]--;
}
cnt[b]--;
}
cnt[a]--;
}
ps( "cnt:%d\n", lcnt);
return 0;
}
ループの中で式を計算する。
最初に出現する計算式は以下の通り。
注意しなければならないのは，掛け算，割り算は足し算，引き算に優先するということ。計算のための処理は以下のようになる。
iop = idig = 0;
push(1);push(2);ope(a);push(3);ope(b);push(4);ope(c);push(5);ope(d);push(6);ope(e);push(7);ope(f);push(8);ope(g);push(9);ope(h);
while( iop--> 0) {
calc(op[iop]);
}
足し算，引き算は演算子をスタックに積み，掛け算，割り算はスタックトップの２つの数を演算し，結果をスタックトップに積む。
数字のスタックと演算子のスタックを用意し，演算は通分して行う。
struct struct_number { // 数字を通分して記録する
int m; // 分子
int n; // 分母
struct_number() { m=n=0;}
struct_number( int x) { m=x; n=1;}
} dig[9];
int idig = 0;
int op[8]; // 0:+, 1:-, 2:*, 3:/
int iop = 0;
push()は数字のスタックに積むだけ。
void push( int n)
{
dig[idig++] = n;
}
ope()は演算子に応じて以下のように処理する。
void ope( int p) {
if( p == 2 || p == 3) {
// ×，÷は出現したら即実行する
calc( p);
}
else {
// ＋または−は計算せずに取っておく
if( p == 1) { dig[idig-1].m = -dig[idig-1].m; p = 0;}// −は+負数に変換する
op[iop++] = p;
}
}
calc()は実際に計算する関数。分子，分母を通分して計算する。実際は引き算は足し算に変換されているので，実行されることはない。
void calc( int p) {
if( idig < 2) { pe( "Stack short\n"); exit(16);}
int m1 = dig[idig-2].m, n1 = dig[idig-2].n;
int m2 = dig[idig-1].m, n2 = dig[idig-1].n;
idig--;
int m, n;
switch( p) {
case 0: // ＋
n = n1*n2; m = m1*n2 + n1*m2;
dig[idig-1].m = m; dig[idig-1].n = n;
//ps( "%d/%d + %d/%d = %d/%d\n", m1, n1, m2, n2, m, n);
break;
case 1: // −
n = n1*n2; m = m1*n2 - n1*m2;
dig[idig-1].m = m; dig[idig-1].n = n;
//ps( "%d/%d - %d/%d = %d/%d\n", m1, n1, m2, n2, m, n);
break;
case 2: // ×
n = n1*n2; m = m1*m2;
dig[idig-1].m = m; dig[idig-1].n = n;
//ps( "%d/%d * %d/%d = %d/%d\n", m1, n1, m2, n2, m, n);
break;
case 3: // ÷
n = n1*m2; m = m1*n2;
dig[idig-1].m = m; dig[idig-1].n = n;
//ps( "%d/%d / %d/%d = %d/%d\n", m1, n1, m2, n2, m, n);
break;
default:
pe( "unknown calc(%d)\n", p);
exit(16);
}
}
0になったかどうかの判定は分子だけで行う。print()はそれなりの出力をする関数を自分で用意する。
if( dig[0].m == 0) { ps( "Find\n"); print(a,b,c,d,e,f,g,h);}
プログラムを実行すると結果が1件だけ出力される。
実行速度
即