「プログラマ脳を鍛える数学パズル」を解いてみる上級編#２【アルゴリズム学習】
概要
翔泳社から出版されている「プログラマ脳を鍛える数学パズル」のプログラミング問題を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++では配列を答えとして返せない。そのため、引数に配列のポインタを渡し、その配列を直接書き換えることで、実装している。
参考文献
「プログラマを鍛える数学パズル」著:増井敏克