クイズ大陸



履歴 検索 最新 出題

No. 2≫ No.3 最新レスです
?seki 2007/01/10 21:29
なんでパスカルの三角形からフィボナッチが?
と思って調べたら、なるほどそういう性質があるんですね。
http://ja.wikipedia.org/wiki/%E3%83%91%E3%82%B9%E3%82%AB%E3%83%AB%E3%81%AE%E4%B8%89%E8%A7%92%E5%BD%A2

だとすると、カードの枚数がx枚の時の解をa(x)とすると、
 a(x) = F(x+2)-1
ですよね。F(x)はフィボナッチ数列のx番目の数です。
フィボナッチ数列には
 F(x+2)=F(x+1)+F(x)
の関係がありますから、F(x+2)=a(x)+1を代入して
(^_-) a(x+2)=a(x+1)+a(x)+1
の漸化式が成り立ちます。

ということは、パスカルの三角形を使わずに、最初からダイレクトに
(^_-)の漸化式を導くような別解がありそうですね。

…と、漸化式から逆に考えたところ、別解が分かりました。

a(x+2)の計算を場合分けして

(i) x+2を選ばない場合が、a(x+1)通り
(ii) ややこしいのは、x+2を選ぶ場合。
 この場合は、残りのカードがx+1枚で、その中から、
 n以上のカードをn-1枚選ぶことになる。
 カードの数字を全部1引いて0からxにしてしまえば、
 n-1以上のカードをn-1枚選ぶことになる。
 n>1の時はa(x)通りで、n=1の場合は1通りなので、
 全部でa(x)+1通り

(i)(ii)を足したら、 (^_-)の漸化式が導かれました。
返信 編集