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

概要

翔泳社から出版されている「プログラマ脳を鍛える数学パズル」のプログラミング問題を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回の時とでそこで計算が終了する点は同じだが、結果が異なることに注意する。

参考文献

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

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問