朝日新聞2006年10月13日パズル横丁解答

プログラムを２つ作ってみた。

プログラムの実行結果は以下の通り。

1*2*3*456*7/8/9 =  19152 /     72 =  266

もう一つのプログラムの実行結果は以下の通り。

1*2*3*4 5 6*7/8/9

プログラムのソースは以下の通り。

#include "puzutl.h"

struct struct_number {          // 数字を通分して記録する
  int m;                        // 分子
  int n;                        // 分母
  struct_number() { m=n=0;}
  struct_number( int x) { m=x; n=1;}
} dig[100];
int idig = 0;
int op[100];                      // 0:+, 1:-, 2:*, 3:/
int iop = 0;
void push( int n)
{
  dig[idig++] = n;
}
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);
  }
}
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;
  }
} 
cstring opestr( int o) {
  cstring s[] = { "+", "-", "*", "/" };
  if( o >= 0 && o <= 3) return s[o];
  return "?";
}

void eval( cstring s)
{
  cstring ss = s;
  iop = idig = 0;
  int n = 0;
  int num[100], o[100];
  int inum = 0;
  while( *s) {
    if( *s == '+') {
      num[inum] = n;
      o[inum] = 0;
      inum++;
      n = 0;
    }
    else if( *s == '-') {
      num[inum] = n;
      o[inum] = 1;
      inum++;
      n = 0;
    }
    else if( *s == '*') {
      num[inum] = n;
      o[inum] = 2;
      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< inum; 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) == 266 && (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);
  }
}

int main( int argc, cstring argv[])
{
  char          ope[] = { '\0', '*', '/'}; // 途中に挟める演算は×と÷だけ,＋,−は挟めない。'\0'は数字を連結するため。
  char          cal[100];       // 計算式をここに入れる。
  astring       p = cal;
  for( int a=0; a< sizeof(ope); a++) {
    *p++        = '1';
    if(ope[a]) *p++ = ope[a];   // 演算子があるときは数字の間に挿入する
    for( int b=0; b< sizeof(ope); b++) {
      *p++    = '2';
      if(ope[b]) *p++ = ope[b];
      for( int c=0; c< sizeof(ope); c++) {
        *p++    = '3';
        if(ope[c]) *p++ = ope[c];
        for( int d=0; d< sizeof(ope); d++) {
          *p++    = '4';
          if(ope[d]) *p++ = ope[d];
          for( int e=0; e< sizeof(ope); e++) {
            *p++    = '5';
            if(ope[e]) *p++ = ope[e];
            for( int f=0; f< sizeof(ope); f++) {
              *p++    = '6';
              if(ope[f]) *p++ = ope[f];
              for( int g=0; g< sizeof(ope); g++) {
                *p++    = '7';
                if(ope[g]) *p++ = ope[g];
                for( int h=0; h< sizeof(ope); h++) {
                  *p++    = '8';
                  if(ope[h]) *p++ = ope[h];
                  *p++    = '9';
                  *p  = NIL;
                  eval(cal);    // 1〜9までの数字を使った式を評価する
                  --p;          // '9' の分
                  if(ope[h]) --p;
                  --p;          // '8' の分
                }
                if(ope[g]) --p;
                --p;            // '7' の分
              }
              if(ope[f]) --p;
              --p;              // '6' の分
            }
            if(ope[e]) --p;
            --p;                // '5' の分
          }
          if(ope[d]) --p;
          --p;                  // '4' の分
        }
        if(ope[c]) --p;
        --p;                    // '3' の分
      }
      if(ope[b]) --p;
      --p;                      // '2' の分
    }
    if(ope[a]) --p;
    --p;                        // '1' の分
  }
  return    0;
}

もう一つのプログラムのソースは以下の通り。

#include "puzutl.h"

const int N = 9;
int ope[N+1];                   // 演算子
void find( char prev_ope, char new_ope, int n, int bunsi, int bunbo, int ope_val)
// prev_ope     :確定演算子(実際に計算する演算子)
// new_ope      :次の演算子(数字の連結を示すための' 'の場合もあるので必ず「演算子」という訳ではない)
// n            :1〜9までの数字
// bunsi,bunbo  :現在までの計算結果(割り算があるので分子,分母で記憶する)
// ope_val      :被演算子(new_opeが' 'の場合演算を保留するのでnを計算に使えない)
{
  if( n > N || new_ope != ' ') { // この時点までの計算式が確定する。
    if( prev_ope == '*') bunsi = bunsi * ope_val; // 掛け算が分子のみに作用
    if( prev_ope == '/') bunbo = bunbo * ope_val; // 割り算は分母のみに作用
    prev_ope    = new_ope;
    ope_val     = n;
    
  }
  else {  
    ope_val     = ope_val * 10 + n; // 計算式が確定しないので被演算子は10倍して記憶
  }
  if( n > N) {
    if( new_ope == ' ' && (bunsi/bunbo) == 266 && (bunsi%bunbo) == 0) { // 計算結果が266になるか?
      for( int i=1; i< n; i++) {
        ps( "%c", ope[i]);
        ps( "%d", i);
      }
      ps( "\n");
    }
    return;
  }
  ope[n]        = new_ope;      // 演算子を記憶しておく
  find( prev_ope, ' ',   n+1, bunsi, bunbo, ope_val);
  find( prev_ope, '*',   n+1, bunsi, bunbo, ope_val);
  find( prev_ope, '/',   n+1, bunsi, bunbo, ope_val);
}

int main( int argc, cstring argv[])
{
  find( ' ', ' ', 1, 1, 1, 0);
  return 0;
}