ハノータアルゴリズム

ハノタアルゴリズムの核心は再帰である.3つのキューがあると仮定すると、c 1,c 2,c 3の初期:c 1(n,n-1,n-2,...,2,1),c 2(),c 3()は、c 1に数字があり、下から上へ:n,n-1,n-2,...,2,1.c 2とc 3は空です
ターゲット:c 3を使用して、c 1上のすべての数字をc 2に搬送
アルゴリズム:1.c 2を介して、c 1上の(n-1,n-2,...,2,1)のn-1個のデータをc 3 2に搬送.そしてc 1上のnをc 2 3に搬送.c 1を介して、c 3上の(n−1,n−1,...,2,1)をc 2上に搬送する.終わります.第1ステップと第3部は,このアルゴリズム自体の再帰呼び出しである.

#include "stdafx.h"
#include "string.h"

#define  uint32 unsigned int
#define  uint16 unsigned short
#define  uint8 unsigned char

#define BASE 5

uint32 s_c1[BASE]={0};
uint32 s_c2[BASE]={0};
uint32 s_c3[BASE]={0};

void print(){
    int max=0,i;
    for(i=BASE-1;i>=0;i--){
        if(s_c1[i] || s_c2[i] || s_c3[i]){
            max=i;
            break;
        }
    }

    for(i=max;i>=0;i--){
        printf("%d %d %d
",s_c1[i],s_c2[i],s_c3[i]);
    }
    printf("----------
");
}
//  c3， num c1       c2 
void hanota(uint32* c1,uint32 num,uint32 *c2, uint32 *c3){
    if(num==1){
        *c2=*c1;
        *c1=0;
        print();
    }else{
        //  c2，  num-1   ， c1   c3 
        hanota(c1+1,num-1,c3,c2);
        //   num   c1   c2
        *c2=c1[0];
        c1[0]=0;
        print();
        //  ，  c1， num-1    c3   c2
        hanota(c3,num-1,c2+1,c1);
    }
}

int main(int argc, char* argv[])
{
    int i;
    for(i=0;ireturn 0;
}