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

概要

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

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

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

問題１

Q61：「同じ大きさに分割」

解答１

ソースコード

#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 m=5;
int n=4;

//条件通り分割できているか判定
bool check(std::vector<int> map){
   std::queue<int> q;
   std::vector<int> num_log;
   q.push(0);
   num_log.push_back(0);    
   int first_cnt=0;
   
   //1色目を確認
   while(q.size()!=0){
       int i=q.front();
       q.pop();
       if(i>=m){
           if(map[i]==map[i-m]){
               if(find(all(num_log),i-m)==num_log.end()){
                   q.push(i-m);
                   num_log.push_back(i-m);
               }
           }
       }
       //下
       if(i<(n-1)*m){
           if(map[i]==map[i+m]){
               if(find(all(num_log),i+m)==num_log.end()){
                   q.push(i+m);
                   num_log.push_back(i+m);

               }
           }
       }
       //左
       if(i%m!=0){
           if(map[i]==map[i-1]){
               if(find(all(num_log),i-1)==num_log.end()){
                   q.push(i-1);
                   num_log.push_back(i-1);
               }
           }
       }
       //右
       if((i%m+1)!=m){
           if(map[i]==map[i+1]){
               if(find(all(num_log),i+1)==num_log.end()){
                   q.push(i+1);
                   num_log.push_back(i+1);
               }
           }
       }
       first_cnt++;
   }

   num_log={0};

   rep(i,m*n){
       if(map[0]!=map[i]){
           q.push(i);
           num_log.push_back(i);
           break;
       }
   }
   
   //もう片方の色を確認
   int second_cnt=0;
   while(q.size()!=0){
       int i=q.front();
       q.pop();
       if(i>=m){
           if(map[i]==map[i-m]){
               if(find(all(num_log),i-m)==num_log.end()){
                   q.push(i-m);
                   num_log.push_back(i-m);
               }
           }
       }
       //下
       if(i<(n-1)*m){
           if(map[i]==map[i+m]){
               if(find(all(num_log),i+m)==num_log.end()){
                   q.push(i+m);
                   num_log.push_back(i+m);

               }
           }
       }
       //左
       if(i%m!=0){
           if(map[i]==map[i-1]){
               if(find(all(num_log),i-1)==num_log.end()){
                   q.push(i-1);
                   num_log.push_back(i-1);
               }
           }
       }
       //右
       if((i%m+1)!=m){
           if(map[i]==map[i+1]){
               if(find(all(num_log),i+1)==num_log.end()){
                   q.push(i+1);
                   num_log.push_back(i+1);
               }
           }
       }
       second_cnt++;
   }
   
   if(first_cnt==second_cnt && first_cnt==m*n/2){
       return true;
   }else{
       return false;
   }
}


int main(void){
   //初期化
   //長方形の2色を0，1で表現
   std::vector<int> map;
   rep(i,m*n/2){
       map.push_back(0);
   }
   rep(i,m*n/2){
       map.push_back(1);
   }
   int cnt=0;
   do{
       if(check(map)){
           cnt++;
       }
   }while(next_permutation(all(map)));
   
   std::cout << cnt/2 << std::endl;
}

実行結果

問題２

Q62：「交差せずに一筆書き」

解答２

ソースコード

#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 W=5;
int H=4;
bitset<20> mas(0);

//x,y:これからひもをつなぐ位置、
//depth：ひもの長さ
//深さ優先探索で再帰的に探索する
int search(int x,int y,int depth){
   int cnt=0;
   if(x<0 || W<=x || y<0 || H<=y){//範囲外の場合
       return 0;
   }
   if(mas[x+y*W]){//すでに探索済みの場合
       return 0;
   }
   if(depth==W*H){//最後まで引けた場合
       return 1;
   }
   
   mas.set(x+y*W);
   cnt+=search(x+1,y,depth+1);//右
   cnt+=search(x-1,y,depth+1);//左
   cnt+=search(x,y+1,depth+1);//上
   cnt+=search(x,y-1,depth+1);//下
   mas.reset(x+y*W);
   return cnt;

}

int main(void){
   int ans=0;
   //開始地点を変えながら探索
   rep(i,W*H){
       ans+=search(i%W,i/W,1);
   }
   
   //反転の場合を考慮して結果出力
   std::cout << ans/2 << std::endl;
   
}

実行結果

今回の学び

・q61については、1色だけ確認するのではなく、2色ともちゃんとつながっているかを確認する必要がある。コードはもっとスマートに書けると思う。

・q62については、シンプルな深さ優先探索だった。本でも書かれているが、Rubyと比べた場合かなり処理時間は短い。

参考文献

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

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