ブラックジャックで大儲け?
カジノの定番、ブラックジャック。 ゲームを1回行うには、最低1枚コインが必要です。 勝てば2枚のコインを得られますが、負けると掛けたコインが没収されます。 最初に1枚だけコインを持っており、1枚ずつ掛けていったとき、ゲームを4回 行って手元にコインが残るような枚数の変化は6通り 1(勝)→2(勝)→3(勝)→4(勝)→5 1(勝)→2(勝)→3(勝)→4(負)→3 1(勝)→2(勝)→3(負)→2(勝)→3 1(勝)→2(勝)→3(負)→2(負)→1 1(勝)→2(負)→1(勝)→2(勝)→3 1(勝)→2(負)→1(勝)→2(負)→1 最初に10枚のコインを持っていたとき、ゲームを24回行って 手元にコインが残るような枚数の変化が何通りあるかを求めて下さい。
#!/usr/bin/perl use strict; use warnings; my %memo; print game(10,24) . "\n"; sub game{ my ($coin,$depth) = @_; if(exists $memo{$coin,$depth}){ return $memo{$coin,$depth}; } if($coin == 0){ return 0; } if($depth == 0){ return 1; } my $win = game($coin + 1,$depth - 1); my $lose = game($coin - 1,$depth - 1); $memo{$coin,$depth} = $win + $lose; }
最初awkで書いたんだけど正しい答えが出なかったのでperlで書いてみた。
その後、色々考えてawk版作成
#!/usr/bin/awk -f BEGIN{ print game(10, 24); } function game(coin,depth,win,lose){ if(memo[coin,depth]){ return memo[coin,depth]; } if(coin == 0){ return 0; } if(depth == 0){ return 1; } win = game(coin + 1, depth - 1); #買ったとき lose = game(coin - 1, depth - 1); # 負けたとき return memo[coin,depth] = win + lose; }
出来なかった原因はperlはサブルーチンの最後にreturn省略可能だけど、awkはreturn 省略不可。
最後の return memo[coin,depth] = win + lose;のreturn が抜けていた。
あと、気づきにくい点として、引数にローカル変数のwinとloseも必要です。
awk -f q23.awk 16051010