朝日新聞2006年3月3日のパズル横丁問題

問題

数字Aを4個と演算子+,−,×,÷,それに括弧を組み合わせて計算結果が10になる計算式を求める。

但しAは1〜9の数字とする。

解答への道(ヒント)

3×3+3÷3=10 ?

これで良いの?

え?

どういうこと?

意味が判らない。

うーん。延々と悩んだ。

判ってしまえば,確かに星一つ問題にふさわしいけど,星一つ問題だから上のように勘違いする人も多いんじゃないんかな?

ということで今回はプログラムは無し。

と思ったけど作ってみました。2005年10月28日の問題に似ているのでソースはそこから拝借して少し修正する。

具体的な修正は以下の通り。

ソースは以下のような感じになる。

int val = 0;                    // 後で1〜9の数字を割り当てる
int numop[6] = {/*0に数字を割り当てる*/ val, 0/*前後の数字を連結*/, /*以降演算子*/ -1/*+*/,-2/*−*/,-3/*×*/,-4/*÷*/};

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;
}

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

 

最近ゴミメールが一段と増えてきた。

ゴミメール自体は無視すれば良いのだがReturn-Pathを偽っているから始末が悪い。

他のサイトに迷惑になるので,宛先不明の場合も全て受け入れることも考えないとダメかな。

解速度