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

概要

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

ぜひ、いいねと思ったらスキお願いいたします！！！
見出し画像は三重県で食べためちゃめちゃ大きいエビフライです。食べ応えもあり、おいしかったです。

【今回のキーワード】
メモ化
左シフト
排他的論理和

問題１

Q20:受難のファザードの魔方陣

解答１

ソースコード

#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 main(void){
   std::vector<int> magic_square={1,14,14,4,11,7,6,9,8,10,10,5,13,2,3,15};
   int msize=magic_square.size();
   int sum_all=accumulate(all(magic_square),0); //魔方陣の合計値
   int sum[1000];
   //初期化
   rep(i,1000){
       sum[i]=0;        
   }
   sum[0]=1;
   
   //一つを固定して計算
   rep(i,msize){
       for (int j = sum_all-magic_square[i]; j >=0 ; j--){
           sum[j+magic_square[i]]+=sum[j];
       }
   }
   
   //結果の出力
   int maxnum=0;
   int num=0;
   rep(i,1000){
       if(maxnum<sum[i]){
           num=i;
       }
       maxnum=max(maxnum,sum[i]);
   }
   std::cout << num << std::endl;
   std::cout <<"組み合わせ数は" <<maxnum <<"個"<< std::endl;
   
}

実行結果

問題２

Q21:排他的論理和で作る三角形

解答２

ソースコード
・64bitでは長さが足りないため、128bitで計算
・全ての0を数えるのではく、数えたい０は必ず"１"で囲われているので、内側の0を数える

#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 main(void){
   int cnt=0;  //0の数
   int line=1; //現在の段数
   //一列を128bit列として表現
   bitset<128> row("1");
   
   while(cnt<2014){
       bitset<128> shiftedRow=row<<1;  //左シフトした列を作成
       row^=shiftedRow;    //排他的論理和をとる
       
       //初めて1がでてきたところからカウントを開始する
       bool t=false;
       for(int i=128;i>=0;i--){    //列の後ろから数える
           if(row[i]){
              t=true; 
           }
           if(t && !row[i]){
               cnt++;
           }
       }
       line++;
   }
   
   std::cout << line << std::endl;
   
}

実行結果

今回の学び

・左シフト(<<)、排他的論理和(^)の方法について

・rubyと違い、作成する列の長さ(bit数)を気にする必要がある。今回は正確な計算はしていないが、128bitで十分だと判断して使用した。

・bitsetのfor文の回し方について。作成した列v[]が0011の場合、v[0]には"1"、v[3]には”0”が格納されている。通常の文字列と違い、後ろから数えて何番目かという扱いになる。

参考文献

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

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