「プログラマ脳を鍛える数学パズル」を解いてみる上級編#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と比べた場合かなり処理時間は短い。
参考文献
「プログラマを鍛える数学パズル」著:増井敏克