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

概要

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

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

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

問題１

Q39：「白」で埋め尽くせ！

解答１

ソースコード

**注意**このコードは処理量が多く、計算に時間がかかります

#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

struct masu{
 bitset<16> steplog;
 bitset<16> board;
};

std::vector<bitset<16>> board_log;

//過去調べたことあるかどうかを判定
bool isContain(bitset<16> bs){
   for (bitset<16> i : board_log) {
       if(i==bs){
           return true;
       }
   }
   board_log.push_back(bs);
   return false;
}

int main(void){
   std::vector<bitset<16>> steplog;
   bitset<16> first("000000000000");
   bitset<16> white("000000000000");

   masu firstM;
   firstM.steplog=first;
   firstM.board=white;
   
   std::queue<masu> scanner;
   scanner.push(firstM);
   
   int ans=0;
   while(scanner.size() > 0){
       masu check=scanner.front();
       scanner.pop();
       //1枚ずつひっくり返してみる
       rep(i,16){
           if(!check.steplog.test(i)){
               masu n;
               n.steplog=check.steplog;
               n.board=check.board;
               
               //ひっくり返す
               int row=i/4;
               int col=i%4;
               n.board.flip(i);
               rep(j,4){
                   n.board.flip(j*4+col);
               }
               rep(j,4){
                   n.board.flip(row*4+j);
               }

               n.steplog.set(i);
               if(!isContain(n.board)){
                   scanner.push(n);
               }
               int cnt=n.steplog.count();
               ans=std::max(cnt,ans);
           }
       }
   }
   std::cout << ans << std::endl;
}

実行結果
今回は写真を撮り忘れたのですが、結果は正しく表示されます

16

問題２

Q40：並び替えの繰り返し

解答２

ソースコード
愚直に求める場合ｎ!の初期状態がありますが、答えから逆算する場合は最初が固定のため、(n-1)!の初期状態に数を減らすことができます。

#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 ans=0;
std::vector<std::vector<int>> ans_list;

void showvec(std::vector<int> num){
   for (int i : num) {
       std::cout << i;
   }
   std::cout  << std::endl;
}

//i番目のカードがiのとき、順番を入れ替えて、再帰する
void search(std::vector<int> num,std::vector<int> init,int cnt){
   if(ans < cnt){
       ans=cnt;
       ans_list.clear();
       ans_list.push_back(num);
   }else if(ans==cnt){
       ans_list.push_back(num);
   }
   repi(i,1,num.size()) {
       if(i+1 == num[i]){
           std::vector<int> rNum=num;
           reverse(rNum.begin(),rNum.begin()+i+1);
           search(rNum,init,cnt+1);

       }
   }
}


int main(void){
   std::vector<int> num={2,3,4,5,6,7,8,9};
   std::vector<std::vector<int>> num_list;

   //先頭の1以外を並び替えて検索する
   do{
       std::vector<int> tmp=num;
       tmp.insert(tmp.begin(),1);
       search(tmp,tmp,0);
       
   }while(std::next_permutation(all(num)));
   
   std::cout <<"処理回数:" <<ans << std::endl;
   for (std::vector<int> i: ans_list) {
       showvec(i);
   }

}

実行結果

今回の学び

・q39は、処理量を減らす方法が思いつかず、とても時間のかかるコードになってしまった（自分の環境では約3分程度かかる）。実装としては、マスを2進数で表現し、0・1で白黒を表現して、反転した。結果はあっていたが、処理が長すぎて使えるコードではないので、処理量を減らす方法を思いつき次第、修正したい。

・q40は答えから逆算することで、簡単に求めることができた。nの値が変わる時は、mainの最初で定義している配列の値を変えるだけで対応することができる。

参考文献

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

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