| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 943 人关注过本帖
标题:[分享]hannoi塔的"牛"算法--非递归
只看楼主 加入收藏
俗狼
Rank: 1
等 级:新手上路
帖 子:13
专家分:0
注 册:2006-5-9
收藏
 问题点数:0 回复次数:3 
[分享]hannoi塔的"牛"算法--非递归

一本权威杂志上找的个程序,很牛,大家分享.
非递归:
#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ÊÇÆæżÅжϣ¬t>>1ÊDzãÖеÄÐòºÅ¡£
{
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ΪÒƶ¯ÅÌ×Ó²½ÖèµÄÐòºÅ¡£
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);
}

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

搜索更多相关主题的帖子: amp 递归 hannoi 算法 ETH 
2006-05-23 21:21
ww1985
Rank: 1
等 级:新手上路
帖 子:30
专家分:0
注 册:2005-10-11
收藏
得分:0 
//c&1ÊÇÆæżÅжϣ¬t>>1ÊDzãÖеÄÐòºÅ¡£
//nΪÒƶ¯ÅÌ×Ó²½ÖèµÄÐòºÅ¡£


我相信爱情,相信所有的人性,所以我努力地挣钱、爱钱。我只是不希望我的爱情和人性受到别人的金钱的考验罢了。爱你到永远!
2006-06-03 19:05
topc
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2006-9-13
收藏
得分:0 

我写过的一个非递归的程序,也是非椎栈的,
我在学校时也发过,现在可能还可以在学园网上看到,不过是内部论坛,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步的移动方法;

2006-09-13 18:34
topc
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2006-9-13
收藏
得分:0 

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

2006-09-13 18:39
快速回复:[分享]hannoi塔的"牛"算法--非递归
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017560 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved