小町算の解法

小町算とは 123456789 の数字の間に幾つか四則演算子を挿入して計算しその結果を 100 に するというものです. 例えば 123-45-67+89=100 や 1*2+34-56/7+8*9=100 のようなものです.
考え方は如何にして全ての計算パターンを尽くすかと言うことにあります. ここでは 8個ある全ての文字の間に演算子を入れることにするが、四則演算子に加えて数字を連なったものと 見なす演算子として # を用いることにする. これは四則演算子記号以外なら何でもよい. つまり 1#2#3 は数 123 を表すことにするのである. このように考えれば全ての計算パターンは8重の繰り返しループで表すことができる. ここではC++言語を使用するが、ネストしたループの数には制限があるので心配でしたが Borland の BCC コンパイラ、MinGW の g++ コンパイラどちらでも 8重ループは使用できました. 今の場合 5^8=390625 通りありますがPCにとってはたいした問題にはなりません（8重のループなど はじめて使用しました）. また使用した環境では整数の範囲が10桁（-2,147,483,648〜2,147,483,647）ですから9桁の数の 計算途中で桁あふれの心配はありません.
例えば 1+2×34-56+78+9 は 1+2*3#4-5#6+7#8+9 で表されます. 計算はまず # 文字が 現れた順に両側の文字を結合し、次に演算の優先順位から現れた順に ＊, / の計算を行い 最後に ＋,− を現れた順に計算すればよいことになります.

次の例では上から下に順次処理を行っています.

1+2*3　#4-5　#6+7　#8+9
1+2*34-56+78+9
1+68-56+78+9
69-56+78+9
13+78+9
91+9
100
この場合には目的の数である 100 になりました.

コンピューターなら計算結果を 1/17 にすることも問題なく求めることができます. この場合 3 パターンで可能でした.

1＋ 2/34− 5− 6− 7＋ 8＋ 9
1×2/34＋ 5＋ 67− 8×9
1×2/34− 5− 67＋ 8×9

double でも計算できますがこの場合目的の数 1/17 になったかどうかの判断は結構めんどくさいです. もし等号で判断すると1つも検出されない場合もある. 0.00001以下を等しいと見なすと3個であるが、0.0001とすると 5個検出され間違いがある. 最後の二つは正しくない.

　　　1 ＋  2 ／ 34 − 5 −   6 − 7  ＋ 8 ＋ 9
　　　1 ×  2 ／ 34 ＋ 5 ＋  67 − 8  × 9
　　　1 ×  2 ／ 34 − 5 −  67 ＋ 8  × 9
　　　1 ／  2 ×  3 ／ 4 ／ 567 × 89      ＝ 1／17 ＋ 1／25704
　　　1 ／ 23 ＋  4 ／ 5 ／   6 ／ 78 × 9 ＝ 1／17 ＋ 1／10465

この問題、多分江戸時代に名付けられたのでしょうが, 教え子から質問されて考えてみました. 解法はすぐに思いつきましたが、プログラムを整理整頓するのに時間が掛かりました. 特に両終端キューの使用方法は少し調べる必要がありました. 使い慣れたスタックでまず制作しましたが、その場合 スタックを逆順に並べ替える処理が必要となりコーディングが汚くなるので両終端キューで制作し直しました.
C++ で私が制作したソースは以下のようなものです. 101 のパターンで100にすることができました.
12-94行目までは有理数クラスの宣言部分でこの問題では実数を用いても結果は同じになるようです.

ここでは演算子を渡して計算していますが、計算式そのものを渡す関数で記述した方がきれいかも知れません. いずれ書き直そうかとも.

Microsoft Visual C では 574 重にネストしたループが可能のようです. BCCでも 8重ループなど問題なくコンパイルできるのは当然かも知れません. 杞憂でした. 


  1.  // 小町算

  2.  // 2020/06/18-2020/06/20

  3.  #include <iostream>

  4.  #include <sstream>  // string stream を用いるので

  5.  #include <fstream>  // ファイルを用いるので

  6.  #include <queue>    // que 使用

  7.  #ifdef __GNUC__ 

  8.  #include <climits> //mingw で必要    INT_MAX

  9.  #endif

  10.  using namespace std;

  11.  

  12.  //   有理数(分数)クラスの定義

  13.  class    RATIONAL{

  14.      int    xi, yi;  //    private

  15.  public:

  16.      RATIONAL(int a=0,int b=1){xi=a;yi=b;};  // コンストラクタ 分母yiの既定値は１

  17.      int      numerator(){ return xi; };     // 分子

  18.      int      denominator(){ return yi; };   // 分母

  19.      RATIONAL operator +(RATIONAL a);

  20.      RATIONAL operator -(RATIONAL a);

  21.      RATIONAL operator *(RATIONAL a);

  22.      RATIONAL operator /(RATIONAL a);

  23.      int      operator ==(RATIONAL a);

  24.      int      operator !=(RATIONAL a);

  25.      int      operator >(RATIONAL a);

  26.      int      operator >=(RATIONAL a);

  27.      int      operator <(RATIONAL a);

  28.      int      operator <=(RATIONAL a);

  29.      friend  ostream& operator << ( ostream &os, RATIONAL &a );

  30.      friend  istream& operator >> ( istream &os, RATIONAL &a );

  31.  };

  32.  const  RATIONAL  RATIONAL_ZERO(0,1);

  33.  const  RATIONAL  RATIONAL_INF=INT_MAX;

  34.  

  35.  // 有理数演算の実装

  36.  RATIONAL  RATIONAL :: operator +(RATIONAL a){

  37.      RATIONAL b(xi * a.yi + yi * a.xi, yi * a.yi );

  38.      return    b;

  39.  }

  40.  RATIONAL  RATIONAL :: operator -(RATIONAL a){

  41.      RATIONAL b(xi * a.yi - yi * a.xi, yi * a.yi );

  42.      return    b;

  43.  }

  44.  RATIONAL  RATIONAL :: operator *(RATIONAL a){

  45.      RATIONAL b(xi * a.xi, yi * a.yi );

  46.      return    b;

  47.  }

  48.  RATIONAL  RATIONAL :: operator /(RATIONAL a){

  49.      RATIONAL b(xi * a.yi, yi * a.xi );

  50.      return    b;

  51.  }

  52.  int  RATIONAL :: operator ==(RATIONAL a){

  53.      if( (xi*a.yi) == (yi*a.xi) )    return 1;

  54.      return 0;

  55.  }

  56.  int  RATIONAL :: operator !=(RATIONAL a){

  57.      return    !((xi*a.yi) == (yi*a.xi));

  58.  }

  59.  int  RATIONAL :: operator >(RATIONAL a){

  60.      return ( (xi*a.yi-yi*a.xi) * (yi*a.yi) > 0 );

  61.  }

  62.  int  RATIONAL :: operator <(RATIONAL a){

  63.      return ( (xi*a.yi-yi*a.xi) * (yi*a.yi) < 0 );// 分母分子が同符号

  64.  }

  65.  int  RATIONAL :: operator >=(RATIONAL a){

  66.      return !(RATIONAL(xi,yi) < a);

  67.  }

  68.  int  RATIONAL :: operator <=(RATIONAL a){

  69.      return !(RATIONAL(xi,yi) > a);

  70.  }

  71.  //    入出力

  72.  ostream& operator << (ostream &os, RATIONAL &a){

  73.      if( a.yi == 1 )    os << a.xi;

  74.      else      os << a.xi << "/" << a.yi;

  75.      return    os;

  76.  }

  77.  istream& operator >> (istream &is, RATIONAL &a){

  78.      is >> a.xi >> a.yi;

  79.      return    is;

  80.  }

  81.  // ユークリッドの互除法による有理数の既約化

  82.  RATIONAL Euclidean_Algorithm( RATIONAL ra ){

  83.      int a = ra.numerator(), b = ra.denominator();

  84.      int a0 = a, b0 = b;

  85.      int mod = a % b;

  86.      while( mod ){

  87.          a   = b;

  88.          b   = mod;

  89.          mod = a%b;

  90.      }

  91.      RATIONAL rra( a0/b, b0/b );// lcd 最大公約数 b で約分

  92.      return rra;

  93.  }

  94.  //#####    有理数クラス宣言はここまで    #####

  95.  

  96.  RATIONAL g_TARGETr = RATIONAL(100,1);// (1,17); 演算結果として目指す数

  97.  RATIONAL g_nr[9] = {1,2,3,4,5,6,7,8,9};//    default 123456789

  98.  

  99.  ofstream ofs("小町算解答.txt",ios::app);// ファイル追加モードで開く

  100.  

  101.  void GetNumbers();

  102.  //    式の計算を行い100になるかどうかをチェック

  103.  int Check100( char op[8] );

  104.  

  105.  // -----------------------------------

  106.  // ##### main #####

  107.  // -----------------------------------

  108.  int main( void )

  109.  {

  110.      //    TARGETr と 9桁の数字を入力させる

  111.      GetNumbers();

  112.  

  113.      //  計算式が格納される    例えば 1+2#3+4+5+6+7#8*9

  114.      char op[5] = {'+','-','*','/','#'};// # は空白無し つまり 1#2 は 12 を表す

  115.      char Operator[8];

  116.      int i=0;    //    全処理候補数=390625=5^8

  117.      int noi=0;    //    答えの数

  118.      //    可能な計算式を全て求める

  119.      for(int i0=0;i0<5;i0++){

  120.          Operator[0]=op[i0];                     //    1 と 2 の間に入る記号 +-*/#

  121.          for(int i1=0;i1<5;i1++){

  122.              Operator[1]=op[i1];                                //    2 3 間 +-*/#

  123.              for(int i2=0;i2<5;i2++){

  124.                  Operator[2]=op[i2];                            //    3 4 間 +-*/#

  125.                  for(int i3=0;i3<5;i3++){

  126.                      Operator[3]=op[i3];                        //    4 5 間 +-*/#

  127.                      for(int i4=0;i4<5;i4++){

  128.                          Operator[4]=op[i4];                    //    5 6 間 +-*/#

  129.                          for(int i5=0;i5<5;i5++){

  130.                              Operator[5]=op[i5];                //    6 7 間 +-*/#

  131.                              for(int i6=0;i6<5;i6++){

  132.                                  Operator[6]=op[i6];            //    7 8 間 +-*/#

  133.                                  for(int i7=0;i7<5;i7++){

  134.                                      Operator[7]=op[i7];        //    8 9 間 +-*/#

  135.                                      i ++;

  136.                                      if( Check100( Operator ) ){//  検算  100？

  137.                                          noi++;//    候補数を増やす

  138.                                      }

  139.                                  }

  140.                              }

  141.                          }

  142.                      }

  143.                  }

  144.              }

  145.          }

  146.      }

  147.      ofs << "\t\t" << g_TARGETr << endl;

  148.      ofs << "\t\t(" << noi << ")/(" << i << ")" << endl;

  149.      ofs.close();    //    ファイルを閉じる

  150.      cout << g_TARGETr << endl;

  151.      cout << "(" << noi << ")/(" << i << ")" << endl;

  152.      return noi;

  153.  }

  154.  //    ---------------------------------------------

  155.  //    Check100

  156.  //    ---------------------------------------------

  157.  int Check100( char op[8] ){

  158.      ostringstream osstrm;

  159.      deque<RATIONAL> Rdq0;           // 両終端キュー double-ended queue

  160.      for(int i=0;i<9;i++){

  161.          Rdq0.push_back( g_nr[i] );  // 順にqueに格納

  162.      }

  163.  

  164.      deque<RATIONAL> Rdq;    // 両終端キュー double-ended queue

  165.      deque<char> Opdq;      // 両終端キュー double-ended queue

  166.  

  167.      RATIONAL Rtmp0, Rtmp1, Rtmp2;

  168.      //    前処理 ＃ 演算子の場合

  169.      for(int i=0; i<8; i++){

  170.          if(op[i]=='#'){            //    前後の数字を纏める preprocess

  171.              Rtmp1 = Rdq0.front();    Rdq0.pop_front();

  172.              Rtmp2 = Rdq0.front();    Rdq0.pop_front();

  173.              Rtmp0 = Rtmp1*10 + Rtmp2;    //  例えば 1#2#3 -> 12#3 -> 123 とする

  174.                  Rdq0.push_front( Rtmp0 );  //  元の場所に戻す

  175.          }else{                            //  加減乗除はそのままpush

  176.              Rtmp1 = Rdq0.front();

  177.                  Rdq.push_back( Rtmp1 );  //  登録

  178.                  Opdq.push_back( op[i] ); //  登録

  179.                  Rdq0.pop_front();        //  取り去る

  180.          }

  181.      }

  182.      Rdq.push_back(Rdq0.front());        //    登録

  183.      Rdq0.pop_front();                    //    取り去る

  184.      //    ここまででque セット

  185.  

  186.      deque<RATIONAL> Rdq1;    // 両終端キュー double-ended queue

  187.      deque<char> Opdq1;        // 両終端キュー double-ended queue

  188.      RATIONAL R1,R2,R3;

  189.      while( !Opdq.empty() ){    //    ＊／の処理

  190.          switch(Opdq.front()){

  191.          case '*' :

  192.              R1 = Rdq.front();    Rdq.pop_front();

  193.              R2 = Rdq.front();    Rdq.pop_front();

  194.              R3 = R1*R2;

  195.                  Rdq.push_front(R3);            //登録

  196.                  break;

  197.          case '/' :

  198.              R1 = Rdq.front();    Rdq.pop_front();

  199.              R2 = Rdq.front();    Rdq.pop_front();

  200.              R3 = R1/R2;

  201.                  Rdq.push_front( R3 );        //登録

  202.                  break;

  203.          default :

  204.              Rdq1.push_back(Rdq.front());Rdq.pop_front();

  205.                  Opdq1.push_back(Opdq.front());    //登録

  206.                  break;

  207.          }

  208.          Opdq.pop_front();

  209.      }

  210.      Rdq1.push_back( Rdq.front() );    Rdq.pop_front();

  211.      while( !Opdq1.empty() ){//    ＋−の処理

  212.          switch( Opdq1.front() ){

  213.          case '+' :

  214.              R1 = Rdq1.front();    Rdq1.pop_front();

  215.              R2 = Rdq1.front();    Rdq1.pop_front();

  216.              R3 = R1+R2;

  217.                  Rdq1.push_front( R3 );        // 登録

  218.                  break;

  219.          case '-' :

  220.              R1 = Rdq1.front();    Rdq1.pop_front();

  221.              R2 = Rdq1.front();    Rdq1.pop_front();

  222.              R3 = R1-R2;

  223.                  Rdq1.push_front( R3 );        // 登録

  224.                  break;

  225.          default : break;

  226.          }

  227.          Opdq1.pop_front();

  228.      }

  229.      R1 = Euclidean_Algorithm(Rdq1.front());Rdq1.pop_front();// 既約分数へ

  230.      if( R1 == g_TARGETr ){

  231.          for( int j=0;j<8;j++){

  232.              osstrm << g_nr[j];

  233.              if( op[j] != '#' )osstrm<<op[j];// #文字は数字を連結

  234.          }osstrm<<g_nr[8]<<endl;

  235.          ofs << osstrm.str();                //  ファイルに書き出す

  236.          osstrm.str("");                     //  buffa clear

  237.          return 1;

  238.      }

  239.      return 0;

  240.  }

  241.  //---------------

  242.  void GetNumbers()

  243.  {

  244.      char na[16];

  245.      cout << "標的の数(有理数)は(100)? 100 1 ";

  246.          cin >> g_TARGETr;    cin.ignore();

  247.      cout << "9桁の数は? 123456789(Enter) ";

  248.          cin.getline(na,sizeof(na));

  249.      if( na[0] ){//  数字の入力があった場合

  250.          for(int i=0;i<9;i++){

  251.              g_nr[i]=int(na[i])-48; //int('0')=48 etc

  252.          }

  253.      }

  254.  }

  255.
inserted by FC2 system