C++學習檔案 < 河內塔 (1.FOR迴圈)+(2.遞迴) >

C++學習檔案 < 河內塔 (1.FOR迴圈)+(2.遞迴) >

1. 河內塔 for迴圈寫法
(包含實體位置)(單陣列從零開始)

當三個的時候
陣列位置

2 | 5 | 8
1 | 4 | 7
0 | 3 | 6
---------
1 | 2 | 3 (塔)
---------
以此類推 (每行最後兩個)

心得:
物品123
柱子ABC
河內塔最簡單的原理就是
1->2->3->1->2->3.... 一直巡迴
每一次都判斷柱子a->b->c->a.....
(請看程式碼，有點亂= =)

#include <iomanip>

#include <iostream>

using namespace std;

int main() {

int b,n,t=0,p=1,j=0,n2,n3,sum=0;

cin >> n;

int *a = new int[n*3] ;



b=1;

for(int i=(n*3-1);i>=0;i--){

if(i<n)

a[i]=b++;



else

a[i]=0;

}

while(1){

n2=j%(n*3);

n3=t%(n*3);

//cout <<p <<n2<<a[n2]<<n3<<a[n3]<<endl;

if(p==a[n2]){

for(int k=0;k<n;k++){//判斷上面是否有東西

if(n2%n==k){

if(a[(j+1)%(n*3)] !=0){

//cout<<"b";

t=j;

p==n?p=1:p++;

}

}

}

}

if(p==a[n2]){

t=j;//暫存

//cout <<p <<endl;

// cout <<n2<<endl;

}

if((a[n3]==p &&a[n2]==0 && n2%n==0)||(a[n3]==p &&a[n2]==0 && n2%n!=0 && a[(j-1)%(n*3)] > p )){//移動+判斷

a[n2]=p;

a[n3]=0;

cout<<"item:"<<setw(3)<<p <<" from:"<<setw(3)<< n3/n+1<<" to:"<<setw(3)<<n2/n+1<<setw(5)<< n3<<setw(3)<<n2<<endl;

sum++;

}



if(n2 ==(t-1)%(n*3) ){

p==n?p=1:p++;//j=0;



}

j++;

if(a[(n*2-1)]==1 || a[(n*3-1)]==1)

break;

}

cout << "sum:" <<sum<<endl;

system("pause");



}

====================================
2. 河內塔 遞迴寫法

不包含位置

#include <iostream>

using namespace std;

void hanoi(int,char*,char*,char*);

int main()

{

cout << "input a number:";

int number;

cin >> number;

char p1[]="A";

char p2[]="B";

char p3[]="C";

hanoi(number,p1,p2,p3);

system("pause");

return 0;

}

void hanoi(int n,char* p1,char* p2,char* p3)

{

if(n==1){

cout << "no." << n << " from " << p1 << " to " << p3 << endl;

}else{

hanoi(n-1,p1,p3,p2);

cout << "no." << n << " from " << p1 << " to " << p3 << endl;

hanoi(n-1,p2,p1,p3);

}

}

=======END======