著者

松浦 昭洋

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2007, no.119, pp.57-64, 2007-11-30

---

本稿では,ハノイの塔問題より一般化された再帰方程式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)なる自然数が昇順に並んだものであることを示す。In this paper, we make exact analysis of the recurrence relations generalized from the Tower of Hanoi problem of the form $T(n, \alpha, \beta) = \min_{\small{1\le t \le n}}\bigl\{ \alpha \, T(n-t, \alpha, \beta) + \beta \, S(t,3) \bigr\}$, where $S(t,3) = 2^t - 1$ is the optimal solution for the 3-peg Tower of Hanoi problem. It is shown that when $\alpha$ and $\beta$ are natural numbers and $\alpha \ge 2$, the sequence of differences of $T(n, \alpha, \beta)$'s, i.e., $T(n, \alpha, \beta) - T(n-1, \alpha, \beta) $, consists of numbers of the form $\beta 2^i \alpha^j \, (i, \, j \ge 0)$ lined in the increasing order.