4

アルゴリズムは次のとおりです。

Algorithm move(k, from, to, spare)
if k >0 then
move(k−1, from, spare, to)
printf (”move top disc from %d to %d\n”,
from, to)
move(k−1, spare, to, from)

k はディスクの数です (http://en.wikipedia.org/wiki/Tower_of_Hanoi)。私は再帰を理解していますが、これがどのように機能するのか理解していません。誰でもこれを理解できますか?

ここでの説明が曖昧で申し訳ありません。何が起こっているのかについての私の理解もかなり曖昧です.printf行が何をしているのか、関数全体にとって極めて重要なようです。

4

1 に答える 1

5

再帰アルゴリズムは、次の 3 つのステップに分けられます。

  1. 1つを除くすべてのディスクを「スペア」ペグに移動します
  2. 最後のディスクを目的のペグに移動します
  3. 1 つを除くすべてのディスク (手順 1 のディスク) をスペア ペグから目的のペグに移動します。

したがって、すべてのディスクが目的のペグに移動されました。

move(k-1, ...)ステップ 1 と 3 は、疑似コード内の 2 つの再帰呼び出しです。ステップ 2 は によってモデル化されますprintf。

ここでのポイントは、ステップ 1 と 3 が へのさらなる呼び出しに再帰し、move各呼び出しが. 何が起こるかというと、このアルゴリズムは、ディスクを移動するために必要な手順を 1 つずつ詳細に出力します。movek > 0prinft

実際、この疑似コードはペグを動かすためのアルゴリズムを実装していません。必要に応じて、人間に指示を与えるためのアルゴリズムです。

于 2011-04-11T18:50:58.693 に答える