(1) 本問を選択

アルゴリズム (1)

本問を選択(Select this problem){ ^する(Yes)^，しない(No) } No.

ハノイの塔の問題を解く再帰的手続きH1(n, A, B, C)を次に与える．3本の杭A, B, C^{がこの順番で一列に並} んでおり，n枚の大きさの異なる円盤がある．円盤の中心に穴があいており，穴を杭に通しながら円盤を積み 上げていく．ただし，大きい円盤の上に小さい円盤を置かなければならない．始めn^{枚の円盤が}A ^に積み上 げられている時，これらの円盤を全てCに積み上げたい．円盤は一度に一枚しか移動できないとする．

We give a recursive procedure H₁(n, A, B, C) for the Towers of Hanoi problem in the following. We have three pegs A, B, C arranged in a row and in this order, and n disks initially stacked in increasing size on peg A. The objective is to transfer the entire tower from pegA to peg C, subjected to the condition that only one disk should be moved at a time and no disk be placed above a smaller.

procedure H₁(n, A, B, C);

if n≥1 then begin H₁(n−1, A, C, B);

“move fromA toC”;

H1(n−1, B, A, C) end

(1) 手続きH1(4, A, B, C)では，円盤を合計何回移動しているか説明しなさい．

Explain how many moves in the procedure H₁(4, A, B, C).

(2) H₁(n, A, B, C)での円盤の移動回数をT₁(n)と書く．ここで，T₁(n)に関する再帰方程式を与えてその解 を求めよ．ただし，T₁(0) = 0とする．

Let T₁(n) be the number of moves in the procedureH₁(n, A, B, C) whereT₁(0) = 0. Give a recursive equation for T₁(n) and solve it.

(3) 問題の条件としてさらに，隣接している杭の間だけで円盤は移動できるものとする．この問題を解く手 続きH₂(n, A, B, C)を与えよ．

We impose the extra condition that a disk must be transferred only between adjacent pegs. Then give a recursive procedureH₂(n, A, B, C) to solve this problem.

(4) H2(n, A, B, C)での円盤の移動回数T2(n)を求めよ．ただし，T2(0) = 0とする．

Give T2(n), i.e., the number of moves in the procedureH2(n, A, B, C) whereT2(0) = 0.

(解答は裏面を使用しても構わない．You can use the reverse side of this paper for your answering.)