朝日新聞2005年9月2日のパズル横丁問題

問題

１０２３４５６７８９の10個の数字の間に「＋」，「÷」を2個ずつ入れて結果が100になるようにするには?

解答への道(ヒント)

そういえば今年は夏休みも無く出題されているなー。

パズルパーク2004年12月11日の問題に似ている。

「＋」と「÷」を入れる場所を決め，その後に計算式を検算する手法を取る。

a,b,c,d,e,f,g,h,iには0,1,2の数字を割り当て，1が「＋」，2が「÷」，0が数字を連結すると見なすと以下のようなコードになる。

int cnt[10];
int main( int argc, cstring argv[])
{
  for( int a=0; a<= 2; a++) {
    cnt[a]++;
    for( int b=0; b<= 2; b++) {
      if( b && cnt[b] >= 2) continue;
      cnt[b]++;
      for( int c=0; c<= 2; c++) {
        if( c && cnt[c] >= 2) continue;
        cnt[c]++;
        for( int d=0; d<= 2; d++) {
          if( d && cnt[d] >= 2) continue;
          cnt[d]++;
          for( int e=0; e<= 2; e++) {
            if( e && cnt[e] >= 2) continue;
            cnt[e]++;
            for( int f=0; f<= 2; f++) {
              if( f && cnt[f] >= 2) continue;
              cnt[f]++;
              for( int g=0; g<= 2; g++) {
                if( g && cnt[g] >= 2) continue;
                cnt[g]++;
                for( int h=0; h<= 2; h++) {
                  if( h && cnt[h] >= 2) continue;
                  cnt[h]++;
                  for( int i=0; i<= 2; i++) {
                    if( i && cnt[i] >= 2) continue;
                    cnt[i]++;
                    if( cnt[1] == 2 && cnt[2] == 2) { // 「＋」が2個，「÷」が2個使用しているか?
                      int pos[] = {a,b,c,d,e,f,g,h,i};
                      char buf[128]; astring s = buf;
                      cstring ns = "1023456789";
                      for( int k=0; k< 9; k++) { // 文字列の間に「＋」と「÷」を入れて計算式を作成する
                        *s++ = ns[k];
                        if( pos[k] == 1) *s++= '+';
                        else if( pos[k] == 2) *s++ = '/';
                      }
                      *s++ = ns[k];
                      *s = NIL;
                      eval( buf); // 作成した計算式を評価する
                    }
                    cnt[i]--;
                  }
                  cnt[h]--;
                }
                cnt[g]--;
              }
              cnt[f]--;
            }
            cnt[e]--;
          }
          cnt[d]--;
        }
        cnt[c]--;
      }
      cnt[b]--;
    }
    cnt[a]--;
  }
  return    0;
}

buf[ ]に計算式を入れ，eval( )で式を計算する。計算部分はパズルパーク2004年12月11日の問題のソースから拝借する。

void eval( cstring s)
{
  cstring ss = s;
  iop = idig = 0;
  int n = 0;
  int num[10], o[10];
  int inum = 0;
  while( *s) {
    if( *s == '+') {
      num[inum] = n;
      o[inum] = 0;
      inum++;
      n = 0;
    }
    else if( *s == '/') {
      num[inum] = n;
      o[inum] = 3;
      inum++;
      n = 0;
    }
    else {
      n *= 10; n += *s - '0';
    }
    s++;
  }
  num[inum] = n;
  push(num[0]);
  for( int i=0; i< 4; i++) {
    push(num[i+1]);
    ope(o[i]);
  }
  while( iop--> 0) {
    calc(op[iop]);
  }
  if( dig[0].n != 0 && (dig[0].m / dig[0].n) == 100 && (dig[0].m % dig[0].n) == 0) { 
    ps( "%s = %6d / %6d = %4d\n", ss, dig[0].m, dig[0].n, dig[0].m/dig[0].n);
  }
}

eval( )が少し綺麗でないのが玉に瑕。

答えは1件出力されました。

解速度

即