UVa 10017 The Never Ending Towers of Honoi

想法：
　　河內塔問題可先簡化成只有一個，那麼只要將它從A移到C，而如果有兩個的話，那就把上面那個移到B，再把下面那個移到C，B再移到C即完成，因此如果有n個，先把上面(n-1)個從A移到B，再把下面那個移到C，最後把(n-1)個從B移到C。

• Honoi(n,a,b,c) 表示將"n"個從A移到C(從第二個參數移到第四個參數)
• Move(a,c) 表示將最下面一個從A移到C

因此可寫成遞迴式：

Hanoi(n,a,b,c)   //將"n"個從A移到C

{

    if(n==1) Move(a,c);  //只有一個，直接移到C

    else{

        Hanoi(n-1,a,c,b);  // 將"n-1"個從A移到B

        Move(a,c);  //將最底下那個從A移到C

        Hanoi(n-1,b,a,c); //最後將"n-1"個從B移到C

    }

}

注意本題output的要求：

• 如果A=>之後沒有數字必須沒有空格
• 每個問題後面都要有一個換行(包含最後一個問題)

	#include <cstdio>
	#include <iostream>
	#include <vector>
	using namespace std;
	void Hanoi(int,vector<int>&,vector<int>&,vector<int>&,vector<int> **);
	void Move(vector<int>&,vector<int>&,vector<int> **);
	int n,m;
	int num;
	int main()
	{
	for(int i=0;;i++){
	scanf("%d %d",&n,&m);
	if (n==0 && m==0) break;
	num=0;
	printf("Problem #%d\n\n",i+1);
	vector<int> a,b,c;
	vector<int> *manage[3]={&a,&b,&c}; //指向A,B,C(因為在函數裡面ABC順序會亂掉)
	printf("A=> ");
	for(int j=n;j>0;j--) {a.push_back(j); printf(" %d",j);}
	printf("\nB=>\nC=>\n");
	Hanoi(n,a,b,c,manage);
	printf("\n");
	}
	return 0;
	}
	void Hanoi(int n,vector<int> &a,vector<int> &b,vector<int> &c,vector<int> *manage[])
	{
	if (n==1 && num<m) Move(a,c,manage);
	else if(num<m){
	Hanoi(n-1,a,c,b,manage);
	if (num>=m) return;
	Move(a,c,manage);
	if (num>=m) return;
	Hanoi(n-1,b,a,c,manage);
	}
	}
	void Move(vector<int> &a,vector<int> &c,vector<int> *manage[])
	{
	c.push_back(a.back());
	a.pop_back();
	printf("\n");
	printf("A=>"); if(manage[0]->size()) printf(" ");
	for(int i=0;i<manage[0]->size();i++) printf(" %d",(*manage[0])[i]); printf("\n");
	printf("B=>"); if(manage[1]->size()) printf(" ");
	for(int i=0;i<manage[1]->size();i++) printf(" %d",(*manage[1])[i]); printf("\n");
	printf("C=>"); if(manage[2]->size()) printf(" ");
	for(int i=0;i<manage[2]->size();i++) printf(" %d",(*manage[2])[i]); printf("\n");
	num++;
	}

view raw UVa 10017.cpp hosted with ❤ by GitHub