「プログラマ脳を鍛える数学パズル」を解いてみる初級編#５【アルゴリズム学習】
概要
翔泳社から出版されている「プログラマ脳を鍛える数学パズル」のプログラミング問題をC++で解きます。
この本ではRuby,JavaScript,Cでの解答はありますが、C++は載っていないため練習として解いてみようと思います。
記事、コード共にまだまだな部分も多いので、何かお気づきの点があれば、コメントお願いいたします。
ぜひ、いいねと思ったらスキお願いいたします！！！
見出し画像は京都の四条の「ホルモン千葉」での写真です。すごくおいしかったので、おすすめです。ただし、ニンニクの量がすごいです…
【今回のキーワード】
・動的計画法
・メモ化
・深さ優先探索
問題１
Q22：絡まない糸電話
解答１
ソースコード
これはRubyのコードと同じ感じでいけました
#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 main(void){
int n=16;
std::vector<int> pair(n/2+1);
pair[0]=1;
//交差しない=偶数人ずつのエリアに分けてその中で糸電話をする
repi(i,1,n/2+1){
pair[i]=0;
rep(j,i){
pair[i]+=pair[j]*pair[i-j-1];
}
}
std::cout << pair[n/2] <<"通り"<< std::endl;
}実行結果
問題２
Q23：ブラックジャックで大儲け
解答２
ソースコード
memo配列に入っているかの判定を-1で初期化することで実装しました
#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
const int c=10;
const int d=24;
ll int memo[c+d+1][d+1];
//深さ優先探索で何通りあるか求める
//coinは残りのコイン枚数,depthは残りのゲーム可能回数を示す
ll int blackjack(int coin,int depth){
if(memo[coin][depth] != -1){
return memo[coin][depth];
}
//コインがゼロの時はゲーム"できない"ので0を返す
if(coin==0){
return 0;
}
//回数がゼロの時は持っているコイン枚数でゲーム"終了"のため1を返す
if(depth==0){
return 1;
}
ll int win=blackjack(coin+1,depth-1);//勝ったときはコインの枚数を増やして再帰
ll int lose=blackjack(coin-1,depth-1);//負けたときはコインの枚数を減らして再帰
memo[coin][depth]=win+lose;
return memo[coin][depth];
}
int main(void){
//初期化
rep(i,c+d+1){
rep(j,d+1){
memo[i][j]=-1;
}
}
std::cout << blackjack(c,d) <<"通り"<< std::endl;
}実行結果
今回の学び
・メモ化、動的計画法、深さ優先探索は頻出パターンなので、問題文を早く理解して時間を意識して実装する
・問題の状況を具体的に考えて、正確に実装する。具体的には、q23はコインが0枚の時と、ゲーム回数が0回の時とでそこで計算が終了する点は同じだが、結果が異なることに注意する。
参考文献
「プログラマを鍛える数学パズル」著:増井敏克