C++ハノイタ問題の知識点まとめ

ハノータ問題は心理学の実験研究でよく使われる課題の一つです。もちろん私たちはコンピュータの勉強をしていますので、コンピュータでそれを解いてみます。
例題
openjudge 6261ハノイタ問題
説明
一つの銅板には三本の棒があり、一番左の棒には上から下まで、小さな順にn個の円盤からなる塔が並んでいます。目的は一番左のレバーの上の皿を全部真ん中のレバーに移すことです。条件は一回に一つの皿だけ移動できます。そして大きな皿を小皿の上に置くことができません。これは有名なハノータの問題です。
円盤は小さいときから大きい番号まで1、2、3、…
入力
整数の後と3つの文字列を入力します。
整数は皿の数、後の3文字は3つの棒の番号を表します。
出力
ステップごとに皿を移動するレコードを出力します。一度に一行を移動します。
移動毎の記録は、例えばa－>3->bの形で、つまり番号3の皿をaロッドからbレバーに移動させる。
サンプル入力
2 a b c
サンプル出力
a->1->c
a->2->b
c->1->b
ハノータ問題
ハノータ問題の解決アルゴリズムは古典的な分割アルゴリズムであり、分割アルゴリズムの最も重要な3つのステップ：

分解：Num個の皿を元の柱lから移行柱midを通って目標の柱rに移動するとしたら、上の皿を元の柱lから移行柱midに移動してから番号numのこの皿を目盛柱rに移動して、最後にその皿を移行柱midから目標柱rに移動します。成功しました。

解決：再帰的にそれぞれサブ問題を解決して出力する（境界条件：一皿だけnum==1の場合、直接出力すればいいです。

合併：再帰的には結果です。再結合は必要ありません。

簡単に言えば、num個目の皿を個々に一つの全体として見て、残りの皿を一つの全体として見て、その二つの全体を別々に移動して目標位置に到達させます。
最後に時間の複雑さを計算します。ここはちょっと計算しにくいです。
i個の皿を一本の柱から別の柱に移動するにはステップ（i）ステップが必要とすると仮定する。
単独の塔に対して、プログラムは以下のように行います。

は上の（n−1）個の皿を遷移柱に移動させ、ステップ（n−1）の回数を持つ。

は、n番目の皿を目標の柱に移動し、回数は1である。

は、移行柱上の（n−1）個の皿を目標柱に移動させ、ステップ（n−1）の回数を持つ。

配達式がもらえます。
Step(n)=2*step(n-1)+1
あとはどんどん渡していけば、手に入ります。
Step(n)=2^n*step(0)+2^(n-1)+2(n-2)+……+2^1+2^0
また、0つの皿は全然動かないので、Step(0)=0
だからStep(n)=2^(n-1)+2^(n-2)+…+2^1+2^0
あとは等比数列の公式でStep(n)=2^n^-1
私たちは移動回数が2^n^-1であることを発見しました。実はこれもハノータ問題の一番少ない移動回数です。結果的にハノータ問題を解決するためのアルゴリズム時間の複雑さはO(^^n^)。
コード

# include <cstdio>
# include <iostream> 
# include <cmath>
# include <cstring>
# include <algorithm>

using namespace std;

int n;
char a, b, c;

// hanoi(num, l, mid, r)     num      l    mid     r。
void hanoi(int num, char l, char mid, char r)
{
  if (num == 1) printf("%c->%d->%c
", l, num, r);
  else {
    hanoi(num - 1, l, r, mid);
    printf("%c->%d->%c
", l, num, r);
    hanoi(num - 1, mid, l, r);
  }
}

int main()
{
  scanf("%d", &n);
  cin >> a >> b >> c;
  hanoi(n, a, c, b); //                            ，  a b。
  return 0;
}

小编が整理したすべての知识点です。皆さんの勉强と支持に感谢しています。