分治アルゴリズム再帰——ハノータ問題

分治アルゴリズムの精髄は分治即ち分治であり、一つの問題の規模が大きすぎて直接解決しにくく、多くの小さな問題に分けることができ、これらの小さな問題を解決し、小さな問題の解を大きな問題の解に統合することができる.
再帰の真髄は,問題の重複部分を見つけ,その重複部分を解決し,問題の規模を小さくするが解決の方法は変わらず,関数で自身を呼び出すことである.大きくて小さくなって、小さくなった.1つの問題が「F(n)=F(n−1)のような関数」として表すことができれば,再帰を用いることができる.
ハノタ問題の説明:
A,B,Cの3本の柱があって、A柱の上でn個の円盤が上から下へ円盤が順次大きく並んで、今A柱の円盤を元の順序でC盤に移動したいと思って、その上中間のいかなる過程の小さい円盤はすべて大きい円盤の上でなければならなくて、毎回1つのディスクしか運ぶことができません(つまり毎回一番上のディスクしか運ぶことができません).
ハノタ問題の分析:
この問題の重複を解決する部分を見つけるには、まず簡単な状況から分析し、徐々に複雑になって法則を見つける必要があります.
1)n=1の場合,A>CのAディスク上の皿を直接Cディスクに移すだけでよい.
2)n=2の場合、B柱を借りて「一時保存領域」として小皿を一時保存し、A柱の大皿がC柱に移動した後、B柱の小皿をC柱に移動し、A>B、A>C、B>Cに移動する必要がある.
3)n=3の場合、円盤の順序を変えることができないため、最初にC柱にあるのは必ず最大のディスクである.A盤の最大のディスクを運ぶには、上の2つのディスクを先に運んで、しかもB柱にしか運ばない.どうやってこの2つの円盤を順番にB盤に移すのか.このときn=2の場合に戻り、このときCカラムを「一時領域」として実現し、最後にAカラム上の最大ディスクをCカラムに移動し、次にn=2の場合にAカラムを「一時領域」としてBカラム上のディスクをCカラムに移動すればよい.
(A>B),A>C,(B>C),()はn=2の場合のプロセスを表し,3+1+3=7回必要である.
4)n=4のとき,我々はゆっくりと法則を見つけた,(A>B),A>C,(B>C),()はn=3の過程を表し,7+1+7=15回必要である.
5)n>1の場合,(A>B),A>C,(B>C),()はn=n−1のプロセスを表し,2^n−1回必要である一般的な法則を見つけた.
ハノータアルゴリズムの説明:

void Hanoi(int n,char A,char B,char C)
{
    if(n>0)
    {
        Hanoi(n-1,A,C,B);    // A n-1     B，  C
        A > C;                // A       C
        Hanoi(n-1,B,A,C);    // B n-1     C,   A
    }
}