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

2020年1月13日 17:07

概要

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

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

ぜひ、いいねと思ったらスキお願いいたします！！！

問題１

Q59：「ハンカチ落としの総走行距離」

解答１

ソースコード

#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 N=8;
int min_step=N*16;
std::vector<std::vector<int>> goal;
string ans_log="";

void search(std::vector<int> child,int oni,int oni_pos,int step,string oni_pos_log){
   
   if(oni==0){//鬼が円から外れたとき
       if(find(all(goal),child)!=goal.end()){//座っている人がゴールの1つと一致した時
           if(min_step>step){//答えが最小の時
               min_step=step;
               ans_log=oni_pos_log;
           }
           return;
       }
   }
   
   //鬼の位置から順番に探索
   repi(i,1,N){
       if(step+N+i<=min_step){//枝刈り
           std::vector<int> next_child=child;
           int pos=(oni_pos+i)%N;
           next_child[pos]=oni;
           int next_oni=child[pos];
           string next_log=oni_pos_log+","+to_string(pos);
           search(next_child,next_oni,pos,step+N+i,next_log);
       }
   }
}

int main(void){
   //ゴールの作成.
   repi(i,1,N+1){
       std::vector<int> tmp;
       repi(j,1,N+1){
           tmp.push_back(N-(i+j)%N);
       }
       goal.push_back(tmp);
   }
   
   //初期化
   std::vector<int> init;
   init.push_back(0);
   repi(i,2,N+1){
       init.push_back(i);
   }
   search(init,1,0,N,"0");
   std::cout <<"最小移動距離:"<< min_step << std::endl;
   std::cout <<"鬼の位置のログ:"<< ans_log << std::endl;
}

実行結果

問題２

Q60：「セルの結合パターン」

解答２

ソースコード

#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=4;
int H=4;

//1マスずつ四角形をセットしながら、長方形ができるかどうかを探索
//ans　答えを格納する配列 0に結合できるパターン数 1に1*1のセルがないパターン数
//pos　探索する位置
//cells　セルが使用済みかどうか　サイズはw*h
//hasOneCell　1*1のセルがあるかどうか
void search(int ans[2],int pos,std::vector<int> cells,bool hasOneCell){
   
   //最後まで探索できた場合
   if(pos==W*H){
       if(hasOneCell){
           ans[0]=1;
           ans[1]=0;
       }else{
           ans[0]=1;
           ans[1]=1;
       }
   }
   
   //探索位置が探索済みの場合は次の位置に移動して探索
   if(cells[pos]==1){
       search(ans,pos+1,cells,hasOneCell);
       return;
   }
   
   //探索していない部分に四角形をセットして長方形を作り探索する
   int x=pos%W;
   int y=pos/W;
   repi(dy,1,H-y+1){
       repi(dx,1,W-x+1){
           std::vector<int> next_cells=cells;
           bool settable=true;//長方形ができるかどうか
           rep(i,dy){
               rep(j,dx){
                   if(next_cells[(x+j)+(y+i)*W]==1){
                       settable=false;
                   }else{
                       next_cells[(x+j)+(y+i)*W]=1;
                   }
               }
               
           }
           //長方形ができる場合は、次を探索
           if(settable){
               int tmp[2]={0};
               search(tmp,pos+1,next_cells,hasOneCell||(dx==1&&dy==1));
               ans[0]+=tmp[0];
               ans[1]+=tmp[1];
           }
       }
   }
}

int main(void){
   //初期化
   std::vector<int> cells(W*H,0);
   int ans[2]={0};
   search(ans,0,cells,false);
   std::cout <<"結合してできるパターン数:"<< ans[0] << std::endl;
   std::cout <<"1＊1のセルがないように結合するパターン数:"<< ans[1] << std::endl;
   
}

実行結果

今回の学び

・q59の27行目で

if(step+N+i<=min_step){//枝刈り

で枝刈りを行った。これによって、プログラムの処理時間を短くすることができる。

・当たり前のことだが、配列などは必ず初期化を行う。そうしないと、よくわからない数値が答えとして出力される。

・q60について、c++では配列を答えとして返せない。そのため、引数に配列のポインタを渡し、その配列を直接書き換えることで、実装している。

参考文献

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

この記事が気に入ったらサポートをしてみませんか？