ガジェット通信 GetNews

見たことのないものを見に行こう

数学の問題をプログラミングで解こう!「ウッド・キーパー」問題解説

DATE:
  • ガジェット通信 GetNewsを≫

問題のおさらい

n 本の丸太があります。これらの向きと端をそろえ、地面に積みます。

積む際には次のルールに従います。
地面には好きな本数の丸太を置けます。隣り合う丸太は接して置きます。
左右に隣り合う 2 本の丸太の上に、新たな丸太を 1 本置けます。
全ての丸太は一つながりになっていないといけません。

n=11 のときの置き方をいくつか示します。
横から見た図です。上の 2 つは正しい置き方ですが、下の 3 つは正しくない置き方です。

数学の問題をプログラミングで解こう!「ウッド・キーパー」問題解説

n 本の丸太の可能な置き方の総数を F(n) と定義します。

例えば F(5)=5 です。可能な置き方を以下に示します。

数学の問題をプログラミングで解こう!「ウッド・キーパー」問題解説

同様に、F(1)=1, F(3)=2, F(4)=3, F(11)=135 となることが確かめられます。

標準入力から、自然数 n (1 ≦ n ≦ 60)が与えられます。
標準出力に F(n) の値を出力するプログラムを書いてください。

方針:視線を斜めに!

丸太をルールにしたがって並べる問題です。n の値が 6 や 7 ぐらいまでなら、ノートに全てのパターンを描き切れますが、それより大きな n になると途端にパターン数が多くなり、手で描き切ることは不可能になります。

さて、本問では、これまでにたびたび登場した「一つ手前の状態を考える」というアプローチが有効です(数学の問題をプログラミングで解こう!「プラス・マイナス・ゼロ」問題解説)。ただ、本問では一筋縄ではうまくいきません。率直には、図を横方向に見て、一つ下の段に k 個の丸太があるとして、その上の積み方を考えたくなるわけですが・・・、実際考えてみると分かりますが、最終的に漸化式の形に落とし込むことはむずかしいです。

そこで発想の転換が必要です。図を横方向に見るのでなく、斜め方向に見ましょう。下図のように、各点線上の丸太の本数を書き並べてみます。すると、自然数の列ができ上がります。

数学の問題をプログラミングで解こう!「ウッド・キーパー」問題解説

題意を満たす丸太の積み方と、この数列には、どのような関係があるでしょうか。それはいたってシンプルです。左端の数字はかならず 1 であること。そして、ある数字は、その左隣りの数字より 2 以上大きくなってはいけません。

数学の問題をプログラミングで解こう!「ウッド・キーパー」問題解説

要するに、F(n) とは、「和が n となる自然数を、左端が 1 で、かつ、どの数字もその左隣りより 2 以上大きくならないように並べる場合の数」に他ならないということです。

これを求めるために次の関数を定義しましょう。ある数字 d の右側に、和が m となる自然数を並べる場合の数を G(m, d) と定義します。

数学の問題をプログラミングで解こう!「ウッド・キーパー」問題解説

G(m, d) はシンプルな漸化式で表すことができます。左端の数字に注目して場合分けしましょう。これの一つ左の数字は d です。左端の数字はこれより 2 以上大きくなってはいけません。したがって、左端に来ることができる数字は、1 から d+1 の間の数字です。

また、左端の数字が k であるとき、残りの並べ方は G(m-k, k) 通りとなります。以上から、G(m, d) の漸化式は次のようになります。

数学の問題をプログラミングで解こう!「ウッド・キーパー」問題解説

そして求めるべき F(n) とは、G(n, 0) のことです。G(m, d) を求める実装を考えましょう。

実装

ここまでくれば、実装は比較的シンプルです。再帰をつかって漸化式を繰り返し呼ぶコードを書きましょう。ただ単純な再帰だと、計算量がネズミ算式に増えてしまいます。いちど計算した引数の組 (m, d) については、結果をキャッシュとして覚えておいて、同じ組の結果が必要になったときには、再計算せずにキャッシュの値を再利用します。(「メモ化再帰」というテクニックです。)

このように、「一つ手前の状態を考える」→「漸化式を立てる」→「メモ化再帰のコードを書く」というのは一連のパターンです。ぜひ慣れておきましょう。

コード例(Python)は以下です。

def g(m, d):
if m == 0: return 1
if m < 0: return 0
if dic.has_key((m, d)): return dic[(m, d)]
a = 0
for k in range(1, d+2):
a += g(m-k, k)
dic[(m, d)] = a
return a

dic = dict()
n = input()
print g(n, 0)

みんなのコード

本問の挑戦者で、コードを公開して頂いた方のコードを Togetter でまとめました。(随時追加していきます。)こちらもぜひチェックして下さい。

CodeIQ「ウッド・キーパー」問題 みんなのコード

CodeIQ運営事務局より

Kawazoeさん、ありがとうございました!
現在、Kawazoeさんの最新問題が出題中です。
ぜひ挑戦してみてくださいね!

カテゴリー : デジタル・IT タグ :
CodeIQ MAGAZINEの記事一覧をみる ▶
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。