poj1958-汉诺四塔问题（三种方法）

链接：http://poj.org/problem?id=1958

大意：汉诺塔升级版，四根柱子，n个盘子，求最少移动次数；

两种方法递推or递归（当然还有思路3——打表）

思路1：递推（或者DP?)

把四塔转换为三塔进行思考

假设当前要移动n个盘子，那么就不如分为以下几步

先将上面的i个盘子移到第2或3个塔上；(四塔移动)

再把剩下的（n-i）个盘子移到最后一个塔上（三塔移动）；

最后把在那i个盘子移到最后一个塔上（注意：是四塔移动，i个盘子一定比后来的（n-i）个盘子小)

得到方程：f[n]=min{2*f[i]+d[n-i]}；

注：f[i]为四塔移动的最小步数，d[i]为三塔移动的最小步数（此处不再多说，都知道是2^i-1了,由于题面要求12，打表就行，由于两次四塔移动，一次三塔移动，所以F[N]*2）

核心代码：

for(int i=1;i<=n;i++)

	{

		f[n]=min(f[n],2*f[i]+d[n-i]);

	}

AC代码

#include<cstdio>

#include<iostream>

#include<cctype>

#include<algorithm>

using namespace std;

inline int read()

{

	int ans=0,f=1;

	char chr=getchar();

	while(!isdigit(chr)) {if(chr='-') f=-1; chr=getchar();}

	while(isdigit(chr)) {ans=ans*10+chr-'0'; chr=getchar();}

	return ans*f;

}//没有读入，依然要坚持加上/笑哭

int f[20]={0};

int d[]={0,1,3,7,15,31,63,127,255,511,1023,2047,4095};

int main()

{

	int n=1;

	f[1]=1;

	f[2]=3;

	for(n;n<=12;n++)

	{

		if(f[n])

		{

			printf("%d\n",f[n]);

			continue;

		}

		f[n]=0x3f3f3f3f;

		for(int i=1;i<=n;i++)

		{

			f[n]=min(f[n],2*f[i]+d[n-i]);

		}

		printf("%d\n",f[n]);

	}

	return 0;

}

思路2：递归

总体思路一模一样，实现有区别而已；

#include<cstdio>

#include<iostream>

#include<cctype>

#include<cstring>

#include<algorithm>

using namespace std;

inline int read()

{

	int ans=0,f=1;

	char chr=getchar();

	while(!isdigit(chr)) {if(chr='-') f=-1; chr=getchar();}

	while(isdigit(chr)) {ans=ans*10+chr-'0'; chr=getchar();}

	return ans*f;

}

int f[20];

int d[]={0,1,3,7,15,31,63,127,255,511,1023,2047,4095};

int hanoi(int x)

{

	if(f[x])

		return f[x];//记忆化（这个算吗/晕）

	if(x==0)

		return 0;

	if(x==1)

		return f[1]=1;

	f[x]=0x3f3f3f3f;

	for(int i=1;i<x;i++)

		f[x]=min(f[x],2*hanoi(i)+d[x-i]);//方程；

	return f[x];

}

int main()

{

	memset(f,0,sizeof(f));

	hanoi(12);

	for(int i=1;i<=12;i++)

		printf("%d\n",f[i]);

	return 0;

}

思路3:打表(hmmmm)

可以说是最快的思路了

#include<cstdio>

#include<iostream>

#include<cctype>

#include<algorithm>

using namespace std;

inline int read()

{

	int ans=0,f=1;

	char chr=getchar();

	while(!isdigit(chr)) {if(chr='-') f=-1; chr=getchar();}

	while(isdigit(chr)) {ans=ans*10+chr-'0'; chr=getchar();}

	return ans*f;

}

int f[]={0,1,3,5,9,13,17,25,33,41,49,65,81};

int main()

{

	for(int i=1;i<=12;i++)

		printf("%d\n",f[i]);

	return 0;

}

巴特西

poj1958-汉诺四塔问题（三种方法）

两种方法递推or递归（当然还有思路3——打表）

思路1：递推（或者DP?)

得到方程：f[n]=min{2*f[i]+d[n-i]}；

思路2：递归

思路3:打表(hmmmm)

最新文章

热门文章

巴特西

poj1958-汉诺四塔问题（三种方法）

两种方法 递推or递归（当然还有思路3——打表）

思路1：递推（或者DP?)

得到方程：f[n]=min{2*f[i]+d[n-i]}；

思路2：递归

思路3:打表(hmmmm)

最新文章

热门文章

两种方法递推or递归（当然还有思路3——打表）