Korean, Edit

C 言語のハノイ タワー

上位カテゴリ : [C 言語] C 言語インデックス

1. 概要

2. 最小手数

3. C コード

a. GitHub


1.概要

⑴ 定義

ハノイの塔は、1883 年にフランスの数学者ルーカスによって導入された問題です。この問題には、n 枚のディスクを移動するのに必要な最小移動数を決定することが含まれます。

⑵ 凡例

インドのベナレス寺院には、世界の中心を表す大きなドームがあります。ドームの内側には、青銅のプレートに 3 本のダイヤモンドの針が刻まれています。針の高さは1キュビト、太さは星の胴体ほどに過ぎません。針の 1 つは 64 個の黄金のディスクで飾られています。最大のディスクが一番下に配置され、残りのディスクが上に向かってどんどん小さく積み重ねられます。これは聖なるブラフマーの塔です。ブラフマーの指示に従い、僧侶たちは昼も夜も祭壇に登り、規則に従って円盤を1つずつ別の針に移動させました。この任務が完了すると塔は崩壊し、世界は滅亡すると言われている。



2.最小移動数

⑴ 概要

たとえば、ディスクが 2 つしかなく、柱 A から柱 C に移動したい場合、次のように移動できます: A → B、A → C、B **→ ** C. 数学者はこの問題を解決するためにさまざまな試みを行い、最小の手数は 2n-1 であることを発見しました。

⑵ 再帰的関係

①漸化式: an+1 = 2an + 1

②再帰式を理解するための図


<中央> 描画 </center> <中央> 描画 </center> <中央> 描画 </center> <中央> drawing </center>

## **3. Cコード**
「」c #include #include /* これはハノイタワー問題を解決するアルゴリズムです */ // ステップ 1. (n-1) 階のピラミッドを他のブランク (A または B) に転送します // ステップ 2. 最大のディスクを C に転送します // ステップ 3. ステップ 1 とステップ 2 を繰り返します (n は小さくなります) void ハノイ(int n, char A, char B, char C){ if(n == 1) printf("%c → %c\n", A, C); それ以外{ ハノイ(n-1、A、C、B); printf("%c → %c\n", A, C); ハノイ(n-1、B、A、C); } } int main(int argc, char *argv[]) { int n; scanf("%d", &n); ハノイ(n, 'A', 'B', 'C'); 0を返します。 } 「」 ---
*入力: 2016.02.08 19:39* *修正:2022.09.08 13:24*

results matching ""

    No results matching ""