[分享]hannoi塔的"牛"算法--非递归

烟灰缸2

电梯直达

1^#

发表于 2009-11-3 23:54:30 | 只看该作者回帖奖励

|倒序浏览 |阅读模式

一本权威杂志上找的个程序,很牛,大家分享.
非递归:
#include<iostream>
using namespace std;
void shuchu(int m,int n)
{
for(int t=n,y=t&1,c=m;y-1;t=t>>1,y=t&1,c--);
switch((c&1)*3+(t>>1)%3) //c&1ê??????D??￡?t>>1ê?2??Dμ?Dòo??￡
{
case 0:cout<<n<<":A-B\n";break;
case 1:cout<<n<<":B-C\n";break;
case 2:cout<<n<<":C-A\n";break;
case 3:cout<<n<<":A-C\n";break;
case 4:cout<<n<<":C-B\n";break;
case 5:cout<<n<<":B-A\n";break;
}
}
void main()
{
int c=1,m,n=1; //n?aò??ˉ?ì×ó2??èμ?Dòo??￡
cout<<"Input the number of the pale! 0-30"<<endl;
cin>>m;
cout<<"Move"<<m<<"pales:"<<endl;
for(c<<=m;n<c;n++)
shuchu(m,n);
}

列几种情况找规律,研究一下,对自己分析问题的能力及算法能有所提高吧.

收藏0

使用道具举报

████

2^#

发表于 2009-11-3 23:54:32 | 只看该作者

//c&1ê??????D??￡?t>>1ê?2??Dμ?Dòo??￡
//n?aò??ˉ?ì×ó2??èμ?Dòo??￡

回复支持反对

使用道具举报

┗白觀喑﹖

3^#

发表于 2009-11-3 23:54:33 | 只看该作者

我写过的一个非递归的程序,也是非椎栈的,
我在学校时也发过,现在可能还可以在学园网上看到,不过是内部论坛,http://bipt.edu.cn
不过程序还有,而且算法也是这个,是我自己搞出来的.......TOPC

想问下,楼主看过的权威杂志是哪个?
main() /*
hanoi移法,非递归算法;本程序求出移动最少次的游戏方案;*/
{
int step,disk,f,layer,k,times; /*某步,塔高,某层,,第几次移动此层;*/
/*此处允许塔高最高15层,由于(int f,step,k)和移位的限制,与算法无关*/
printf("This program designed by 0T3_ToPc,Email:kingo_cgh@163.com.\n");
printf("disk=");
scanf("%disk",&disk);
k=~(~0<<1); /* 逻辑 1 */
for(f=1;(f>>disk)==0;f++) /* f小于2的disk次方,历遍(2的disk次方-1)的每
一步;*/
{
step=f;
layer=1; /*第一层*/
while(!(step&k)) /*第step步,移动哪层?*/
{
step>>=1;
layer++;/*根据第2的n-1次方步移动第n层算法,推出第step步要移
动得的相应的层layer;*/
printf(" / ");
/*第(2的n+x次方+2的n-1次方)为第x+1次移动第n层*/
}
step>>=1;
step+=1; /*算出step是第layer的第(f>>layer+1)次移
动;*/
times=step%3; /*选定三步周期的哪一步;以下用A,B,C分别指HANOI
的第一,二,三针; */
if(disk%2!=layer%2) times+=3; /*选定移动方向A->C->B->A或A->B->C->A（共三步） */
/*disk,layer分奇奇ACBA，奇偶ABCA，偶奇ABCA，偶偶ACBA;*/
switch(times) /*打印移动步法*/
{
case 0: printf("[s%d-l%d B->A]\n",step,layer);break;/* B->A */
case 1: printf("[s%d-l%d A->C]\n",step,layer);break;/*A->C */
case 2: printf("[s%d-l%d C->B]\n",step,layer);break;/* C->B */
case 3: printf("[s%d-l%d C->A]\n",step,layer);break;/**/
case 4: printf("[s%d-l%d A->B]\n",step,layer);break;/**/
case 5: printf("[s%d-l%d B->C]\n",step,layer);break;/**/
}
}
}
以塔高4曾为例，本程序执行结果：
This program designed by 0T3_ToPc,Email:kingo_cgh@163.com. disk=4
[s1-l1 A->B]第一层
/ [s1-l2 A->C]第二层
[s2-l1 B->C]
/ / [s1-l3 A->B].
[s3-l1 C->A]
/ [s2-l2 C->B]
[s4-l1 A->B]
/ / / [s1-l4 A->C] 第disk层
[s5-l1 B->C]
/ [s3-l2 B->A]
[s6-l1 C->A]
/ / [s2-l3 B->C]
[s7-l1 A->B]
/ [s4-l2 A->C]
[s8-l1 B->C]
"/"很方便得让我们看到，每一层的移动周期,方向;
稍微改动for循环，本程序就可得出指定step步的移动方法;

回复支持反对

使用道具举报

轻松由我

4^#

发表于 2009-11-3 23:54:34 | 只看该作者

我的Q是:27003318,
楼主把你看的杂志名给我发一下,我也看看,

回复支持反对

使用道具举报

		自动登录	找回密码
密码			注册

浏览过的版块