体験を伝える―『ガジェット通信』の考え方

面白いものを探しにいこう 本物を体験し体感しよう 会いたい人に会いに行こう 見たことのないものを見に行こう そしてそれをやわらかくみんなに伝えよう [→ガジェ通についてもっと詳しく] [→ガジェット通信フロアについて]

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

問題のおさらい

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 の間の数字です。

1 2次のページ
CodeIQ MAGAZINEの記事一覧をみる
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。
GetNews girl / GetNews boy

オスカー2018年晴れ着撮影会