「プログラマ脳を鍛える数学パズル」を解いてみる上級編#5【アルゴリズム学習】
概要
翔泳社から出版されている「プログラマ脳を鍛える数学パズル」のプログラミング問題をC++で解きます。
この本ではRuby,JavaScript,Cでの解答はありますが、C++は載っていないため練習として解いてみようと思います。
記事、コード共にまだまだな部分も多いので、何かお気づきの点があれば、コメントお願いいたします。
入門編#1はコチラ
初級編#1はコチラ
中級編#1はコチラ
上級編#1はコチラ
ぜひ、いいねと思ったらスキお願いいたします!!!
問題1
Q64:迷路で待ち合わせ
解答2
ソースコード
注意:処理時間がかなりかかります
#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
#define N 5
#define S N*N
int dir[4][2]={{1,0},{0,-1},{-1,0},{0,1}};
struct move_log{
int x;
int y;
int pre;
bool equals(move_log t){
if(t.x==x && t.y==y && t.pre==pre){
return true;
}
return false;
}
};
//同じログがあるかどうか調べる
int check(std::vector<move_log> p1){
move_log last=p1.back();
int cnt=0;
rep(i,p1.size()){
if(p1[i].equals(last)){
cnt++;
}
}
return cnt;
}
//2人が合うかどうかを調べる
bool search(bitset<S> maze,std::vector<move_log> p1,int d1,std::vector<move_log> p2,int d2,int cnt){
if(p1.size()==p2.size()){
if(p1.back().x==p2.back().x && p1.back().y==p2.back().y){
return true;
}
if(p1.back().x==N-1 && p1.back().y==N-1){
return false;
}
if(p2.back().x==0 && p2.back().y==0){
return false;
}
}
if(check(p1)>1){
return false;
}
move_log pre=p1.back();
rep(i,4){
if(d1==0){
d1=4;
}
int d=(d1-1+i)%4;
move_log tmp;
tmp.x=pre.x+dir[d][0];
tmp.y=pre.y+dir[d][1];
tmp.pre=d;
std::vector<move_log> next_p2=p1;
if(tmp.x>=0 && tmp.x<N && tmp.y>=0 && tmp.y<N && (maze[tmp.x+N*tmp.y]==0)){
next_p2.push_back(tmp);
return search(maze,p2,d2,next_p2,d,cnt+1);
break;
}
}
return false;
}
int main(void){
//初期化
move_log a;
a.x=0;
a.y=0;
a.pre=-1;
move_log b;
b.x=N-1;
b.y=N-1;
b.pre=-1;
int cnt=0;
std::vector<move_log> p1_move;
std::vector<move_log> p2_move;
p1_move.push_back(a);
p2_move.push_back(b);
int g=0;
//迷路をbitsetで表現
rep(i,pow(2,S)){
bitset<S> map(i);
if(!map[0] && !map[S-1]){
g++;
if(search(map,p1_move,3,p2_move,1,0)){
cnt++;
}
}
}
std::cout << "ans:"<<cnt << std::endl;
}
実行結果
問題2
Q65:面倒なキャッチボール
解答2
ソースコード
注意:処理時間がかなりかかります
#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
std::vector<int> start;
std::vector<int> goal;
int SIZE=10;
int DEPTH;
//条件に合う投げ方ができるかどうかを調べる
bool throwable(std::vector<int> balls,int pre,int depth){
if(balls==goal){
std::cout << "ans"<<depth << std::endl;
return true;
}
if(depth>DEPTH){
return false;
}
//受け手の位置を取得
std::vector<int>::iterator iter=std::find(all(balls),0);
int recipient=std::distance(balls.begin(),iter);
//枝刈り
if((recipient%(SIZE/2))+1>=DEPTH-depth ){
return false;
}
//受け手の正面を計算
int front=(recipient+(SIZE/2))%(SIZE);
//受け手に投げる
bool flag=false;
repi(i,-1,2){
if(i+front>=0 && i+front<SIZE && (front+i)/(SIZE/2)==front/(SIZE/2)){
if(i+front!=pre){//枝刈り
balls[recipient]=balls[i+front];
balls[i+front]=0;
if(throwable(balls,recipient,depth+1)){
flag=true;
return true;
}
balls[i+front]=balls[recipient];
balls[recipient]=0;
}
}
}
return flag;
}
int main(void){
//初期化
repi(i,1,SIZE){
start.push_back(i);
}
start.push_back(0);
goal.push_back(0);
repi(i,2,SIZE){
goal.push_back(i);
}
goal.push_back(1);
//反復深化で検索
for (DEPTH = 1; ; DEPTH++) {
if(throwable(start,-1,0))break;
}
}
実行結果
今回の学び
・今回は両方とも,処理時間を縮めることができなかった.時間のある時に,修正して短縮していきたい.
・q64は,単純にマスを移動する方法で考えた.迷路が成り立っているかどうかの判定を入れることで,もう少し短縮させることができると思う.ビット演算の実装については,十分な理解ができなったので,実装をあきらめた.ビット演算のほうが圧倒的に早いと思うので,理解して実装し直したい.
・q65は,最後に紹介されていた「反復深化」を用いて実装を行った.枝刈りの方法として,”投げてきた人に投げ返さない”と”残り回数で条件を満たせない”を行った.もっと効果的な枝刈りの方法を見つけて,時間を短縮したい.
参考文献
「プログラマを鍛える数学パズル」著:増井敏克
この記事が気に入ったらサポートをしてみませんか?