ハノイの塔問題に対する再帰方程式の一般化とその厳密解析

スポンサーリンク

概要

論文の詳細を見る
本稿では,ハノイの塔問題より一般化された再帰方程式T(n,α,β)=min_<1≤t≤n{αT(n-t,α,β)+βS(t,3)}(S(t,3)=2^t-1は3本の塔を持つハノイの塔問題に対する最小解)に対する厳密な解析を行い,その一般解を導出する。すなわち,αとβがα≥2なる任意の自然数であるとき,{T(n,α,β)}の階差数列がβ2^iα^j(i,j≥0)なる自然数が昇順に並んだものであることを示す。
2007-11-30

著者

関連論文

もっと見る

スポンサーリンク