新汉诺塔问题 汉诺塔问题c

假设有不同大小的光碟标签ñ从1到n按照它们的大小的升序排列。在初始状态是随机的N光盘上三极堆积,现在你必须要了解最少的动作把初始状态的目标。

该举措的要求为以下几种:

1)你只能一次移动一个圆盘;

2)较大的光盘是不允许在一个较小的一栈

current和target分别表示开始状态的结束状态。

这个问题和Hanoi问题相似,可以这样做

1找到最大的需要移动的盘k

2将小于此盘的1...k-1摞成一堆

3腾出目标位置,移动k

4再次找到需要移动的k,重复3直到k=1

对于步骤2实现起来比较难,可以将2再次看成一个问题,用分治算法来做

make_tower(k,current)//将1...k落到k在的位置

if k=1then return

ifk=2

ifcurrent[k]≠current[k-1]

then将k移到k+1上

return

ifk,k-1,k-2分别位于不同位置

thenmake_tower(k-2,current)

将k-1移到k上

Hanoi(current,k-2,current[k-2],current[k-1],current[k])

return

make_tower(k-1,current)

ifk和k-1不在同一个位置

thentemp←除k和k-1的位置

Hanoi(current,k-1,current[k-1],temp,current[k])

这样问题迎刃而解了

代码

#include<stdio.h>
int count=0;
int pick_top(char c[],char a)
{
int i=1;
while(c[i]!=a)
i++;
return i;
}
void Hanoi(char current[],int k,char a,char b,char c)
{
int i;
if(k==1)
{
i=pick_top(current,a);
printf("%c-->%cn",a,c);
count++;
current[i]=c;
return;
}

Hanoi(current,k-1,a,c,b);

printf("%c-->%cn",current[k],c);
count++;
current[k]=c;

Hanoi(current,k-1,b,a,c);
}
void make_tower(char c[],int n)
{
char temp;
if(n==1)
return;
新汉诺塔问题 汉诺塔问题c
if(n==2)
{
if(c[1]!=c[2])
{
printf("%c-->%cn",c[1],c[2]);
count++;
c[1]=c[2];
}
return;
}
if(c[n]!=c[n-1]&&c[n]&&c[n-2]&&c[n-1]!=c[n-2]){//n,n-1,n-2都不在同一个盘子上
make_tower(c,n-2);
//将n-1移到n上
printf("%c-->%cn",c[n-1],c[n]);
count++;
temp=c[n-1];
c[n-1]=c[n];
Hanoi(c,n-2,c[n-2],temp,c[n]);
return;
}

make_tower(c,n-1);
if(c[n-1]!=c[n])
{
temp='A'+'B'+'C'-c[n]-c[n-1];
Hanoi(c,n-1,c[n-1],temp,c[n]);
}
}
int main()
{
char current[6]={0,'C','C','C','B','B'};
char target[6]={0,'C','A','B','B','B'};
int k=6;
char temp;
while(current[k]!=target[k]&&k>0)//找到第一个最大的不符合要求的盘子
k--;
if(k>2)//如果k>2,把1...k-1移到k-1上
make_tower(current,k-1);
while(k>1)
{
if(current[k]!=target[k])
{
if(current[k]==current[k-1])
{
temp='A'+'B'+'C'-current[k]-target[k];
Hanoi(current,k-1,current[k-1],target[k],temp);
}
elseif(current[k-1]==target[k])
{
temp='A'+'B'+'C'-current[k]-target[k];
Hanoi(current,k-1,current[k-1],current[k],temp);
}

printf("%c-->%cn",current[k],target[k]);
count++;
current[k]=target[k];

}
k--;
}
if(current[1]!=target[1])
{
printf("%c-->%cn",current[1],target[1]);
count++;
current[1]=target[1];
}
printf("%dn",count);

}

  

爱华网本文地址 » http://www.413yy.cn/a/25101011/103703.html

更多阅读

解决水晶报表重线丢线问题 c 水晶报表

解决水晶报表页中间重线页尾丢线问题一正常的方式会出现页中间重线页尾丢线  如果“详细资料”节中有多行内容,而且字段可能扩展多行,则字段扩展之后可能其后的横线出现多次,甚至页尾的横线丢失。这里以“详细资料”节有两行内容

新汉诺塔问题 汉诺塔问题c

假设有不同大小的光碟标签&#241;从1到n按照它们的大小的升序排列。在初始状态是随机的N光盘上三极堆积,现在你必须要了解最少的动作把初始状态的目标。该举措的要求为以下几种:1)你只能一次移动一个圆盘;2)较大的光盘是不允许在一个较小

“7.22”京珠高速车祸“7.23高铁追尾” 丰田新汉兰达车祸追尾

“7.22”京珠高速车祸“7.23高铁追尾” 7月22日凌晨4点左右,一辆由山东威海开往湖南长沙的严重超载(核载35人,实载47人)双层大客车,在京珠高速由北向南938公里又700米处突发大火燃烧,造成41人死亡,6人受伤,其中一人重伤。这辆由北向南开的

声明:《新汉诺塔问题 汉诺塔问题c》为网友回忆太细分享!如侵犯到您的合法权益请联系我们删除