「プログラマ脳を鍛える数学パズル」を解いてみる中級編#6【アルゴリズム学習】

概要

翔泳社から出版されている「プログラマ脳を鍛える数学パズル」のプログラミング問題をC++で解きます。
この本ではRuby,JavaScript,Cでの解答はありますが、C++は載っていないため練習として解いてみようと思います。
記事、コード共にまだまだな部分も多いので、何かお気づきの点があれば、コメントお願いいたします。

入門編はコチラ
初級編はコチラ

ぜひ、いいねと思ったらスキお願いいたします！！！
見出し画像は最近食べたおいしいものです。

問題１

Q41：美しい？IPアドレス

解答１

ソースコード
16ビットを反転して結合することで、左右対称を実現しています。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define repi(i,a,n) for(int i = (int)a; i < (int)(n); i++)
#define ll long long

std::vector<string> val;

//文字列が重複している文字をつかっていないかチェックする
bool checkUnique(string s){
   sort(all(s));
   auto result = std::unique(all(s));
   
   s.erase(result, s.end());
   
   int b=s.size();
   if(b==11){
       return true;
   }else{
       return false;
   }
}


int main(void){
   //16ビットの2進数を反転させ、IPアドレスを作成
   //そのアドレスを8ビットに分割し、10進数に変換する
   //10進数の数値が数字を一度ずつ使っているかどうかチェックする
   
 rep(i,65536){
      bitset<16> bs(i);
      string bs_string=bs.to_string();
      string rbs_string=bs_string;
      reverse(all(rbs_string));

      string s=bs_string+rbs_string;
      string r="";
      rep(i,4){
          bitset<8> t(s.substr(i*8,8));
          r+=to_string(t.to_ulong());
          if(i!=3){
              r+=".";
          }
      }
     if(checkUnique(r)){
         std::cout << r << std::endl;
         val.push_back(r);
     }
 }
   std::cout << "上記の"<<val.size()<<"個"<< std::endl;
}

実行結果

問題２

Q42：1つの数字で作る1234

解答２

ソースコード
数値の計算のメソッドは自作しました

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define repi(i,a,n) for(int i = (int)a; i < (int)(n); i++)
#define ll long long


//文字列の数式を計算する
int eval(string s){
   //std::cout << s << std::endl;
   std::stack<int> num;
   std::stack<int> sign;
   int t=0;
   for (char i : s) {
       if(i=='*'|| i=='/' || i=='+'|| i=='-'){
           num.push(t);
           t=0;
           if(sign.size()>=1 && sign.top()=='*'){
               int a,b;
               b=num.top();
               num.pop();
               a=num.top();
               num.pop();
               num.push(a*b);
               sign.pop();
           }else if(sign.size()>=1 && sign.top()=='/'){
               int a,b;
               b=num.top();
               num.pop();
               a=num.top();
               num.pop();
               num.push(a/b);
               sign.pop();
           }
           sign.push(i);
       }else{
           t = t*10+((int)(i-'0'));
       }
   }
   num.push(t);
   while(sign.size()>0){
       int a,b;
       b=num.top();
       num.pop();
       a=num.top();
       num.pop();
       char j=sign.top();
       switch(j){
           case '+':num.push(a+b);
           break;
           case '-':num.push(a-b);
           break;
           case '*':num.push(a*b);
           break;
           case '/':num.push(a/b);
           break;
       }
       sign.pop();
   }
   //std::cout << num.top() << std::endl;
   return num.top();
}

string op[5]={"+","-","*","/",""};


//lenは残り文字数、num_stringは現在の式、numは使える数字
bool check(int len,string num_string,int num){
   //残り文字列が0の場合は、計算する
   if(len==0){
       if(eval(num_string)==1234){
           std::cout << num_string << std::endl;
           return true;
       }else{
           return false;
       }
   }else{
   //文字列を追加する
   //10倍するか、符号を追加する
       rep(i,5){
           string t=num_string+op[i]+to_string(num);
           if(check(len-1,t,num)){
               return true;
           }
       }
   }
   return false;
}

int main(void){
   //時間計測用
   std::chrono::system_clock::time_point  start, end;
   start = std::chrono::system_clock::now();
   
   //文字列を増やしていき、もしみつかればループを止める
   int len=1;
   bool flag=true;
   while(flag){
       repi(i,1,10){
           if(check(len,to_string(i),i)){
               flag=false;
               break;
           }
       }
       len++;
   }
   
   //時間計測用
   end = std::chrono::system_clock::now();
   double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count(); 
   std::cout << elapsed << std::endl;
}

実行結果
結果と実行時間が表示されています。

今回の学び

・q41について、本では2つ目の解法に組み合わせを用いていますが、c++ではそのようなライブラリがないため（順列は存在する）、16ビットを反転させる方が実装が楽だった。

・q41の一度だけ出現しているの判定について、unique関数を実行する前に、sortを実行する必要がある。これはunique関数が隣り合った重複要素を除いたものを、先頭に集めるという仕様のため、sortを実行していないと、隣り合うという条件を満たさないからである。そのため、uniqueとsortはセットで行う必要がある。

・q42の文字列の数式を計算する関数は、文字列を一文字ずつ読み、各数値をスタックし、適切なタイミングで計算する。数字が読み込まれている場合は、10倍して追加していき、符号が読み取られた時点で数字を確定（スタック）させる。符号の読み取りについては、"*"または”/"が読み込まれた場合、その直前（符号のスタックとトップを確認）に、"+"と"-"が存在していれば、その時点で計算する。ない場合は、最後にまとめて計算する。"+"と"-"については、他の符号にかかわらず最後にまとめて計算する。

・q42は本で取り扱っているRubyではevalという関数があり、計算が非常に楽に行えているが、c＋＋ではそういったものはないため、自分で実装する必要がある。今回は括弧が使用不可という条件のため、比較的簡単に実装できた。括弧を使用する場合は逆ポーランド記法の計算を実装する必要がある。

参考文献

「プログラマを鍛える数学パズル」著:増井敏克

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問