博文

关于汉诺塔问题的最终解决(2006-06-16 17:55:00)

摘要:问题的提出:约19世纪末,在欧州的商店中出售一种智力玩具,在一块铜板上有三根杆,最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到右边的杆上,条件是一次只能移动一个盘,且不允许大盘放在小盘的上面。
*问题分析与算法设计
这是一个著名的问题,几乎所有的教材上都有这个问题。由于条件是一次只能移动一个盘,且不允许大盘放在小盘上面,所以64个盘的移动次数是:
18,446,744,073,709,551,615
这是一个天文数字,若每一微秒可能计算(并不输出)一次移动,那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔,但很难用计算机解决64层的汉诺塔。
分析问题,找出移动盘子的正确算法。
首先考虑a杆下面的盘子而非杆上最上面的盘子,于是任务变成了:
*将上面的63个盘子移到b杆上;
*将a杆上剩下的盘子移到c杆上;
*将b杆上的全部盘子移到c杆上。
将这个过程继续下去,就是要先完成移动63个盘子、62个盘子、61个盘子....的工作。
为了更清楚地描述算法,可以定义一个函数movedisc(n,a,b,c)。该函数的功能是:将N个盘子从A杆上借助C杆移动到B杆上。这样移动N个盘子的工作就可以按照以下过程进行:
1) movedisc(n-1,a,c,b);
2) 将一个盘子从a移动到b上;
3) movedisc(n-1,c,b,a);
重复以上过程,直到将全部的盘子移动到位时为止。
*程序与程序注释
#include<stdio.h>
void movedisc(unsigned n,char fromneedle,char toneedle,char usingneedle);
int i=0;
void main()
{
unsigned n;
printf("please enter the number of disc:");
scanf("%d",&n); /*输入N值*/
printf("\tneedle:\ta\t b\t c\n");
movedisc(n,'a','c','b'); /*从A上借助B将N个盘子移动到C......

阅读全文(3481) | 评论:0

二叉排序树与平衡树算法实现及演示(2006-05-11 21:05:00)

摘要:这个程序是我学数据结构时候,老师说让我做个演示程序时候做的一个最初版本程序。当然这不是教给老师的演示程序版本,演示版本的算法是套用书上的,这版本算法是我自己写的,所以我不能保证它没BUG(PS:在删除平衡树节点时候,由于我采用不同于书上的删除策略,所以后面演示程序可能不会象想象中那样旋转)。下面我给出程序中主要的算法及功能模块函数概要说明,最后附上源代码。 算法1:平衡树创建
说明:1,输入数列以整数零结束;2,平衡树HEAD初始化为空树
(1) 从输入数列接收一个DATA
(2) IF DATA!=0 THEN DATA转化成NODE
ELSE 返回
(3) 将NODE插入平衡树HEAD中
(4) 转到(1)继续实行 算法2:平衡树中插入的实现
说明:作左旋转和作右旋转的同时,相关节点的BF均置0。
(1)从调用函数中接收一个节点NODE
(2)IF HEAD=NULL THEN 将NODE节点直接插入平衡树HEAD
转到(6);
(3)IF HEAD>NODE
THEN 将NODE节点插入HEAD->LCHILD平衡树
转到(4);
ELSE IF HEAD<NODE
THEN 将NODE节点插入HEAD->RCHILD平衡树
转到(4);
ELSE 转到(6)
(4) 计算HEAD根节点平衡因子BF0
(5) IF –2<BF0<2 THEN 转到(6)
ELSE IF HEAD根节点BF==2
THEN IF HEAD左子树根节点BF==1 THEN 右旋转
ELSE (说明左子树根节点BF==-1)
做先左后右旋转,修改相关节点BF;
ELSE IF HEAD根节点BF==-2
THEN IF HEAD右子树根节点BF==-1 THEN 左旋转
ELSE (说明右子树根节点BF==1)
作先右后左旋转,修改相关节点BF
(6)返回
功能模块概要说明:
1,创建二叉排序树 Insert(BNODE **head),InitBST(int *p)
2,打印二叉排序数 Pr......

阅读全文(6217) | 评论:5

求逆波兰表达式的值(2006-05-05 19:59:00)

摘要:求逆波兰表达式的值,即得原算术表达式的值,可实现简单四则运算 (为简单起见,设原算术表达式中参加运算的数都只有一个数字)。*/ /*2005-3-10 梁见斌*/ #include #include #include #define MAX 30 int GetStr(char str[]);/*输入算术表达式*/ void Print(char exp[], int len);/*输出表达式*/ int Change(char str[], char exp[]);/*将一般表达式转化为逆波兰表达式*/ float JiSuan(char exp[]); /*求逆波兰表达式的值*/ int main(void) { char str[MAX], *pstr=str;/*存储原算术表达式*/ char exp[MAX], *pexp=exp;/*存储转化成的逆波兰表达式*/ float result; /*存储逆波兰表达式的值*/ int len1, len2;/*len1存储原算术表达式的长度,len2存储转化成的逆波兰表达式的长度*/ len1=GetStr(pstr); printf("原算术表达式: "); Print(pstr, len1); len2=Change(pstr, pexp); printf("逆波兰表达式: "); Print(pexp,len2); result=JiSuan(pexp); printf("The result is: %f", result); system("pause"); return 0; } int GetStr(char str[]) { int i=0; printf("请输入算术表达式: "); do{ scanf("%c", &str[i++]);/*设字符‘#’为表达式的终止符*/ }while(str[i-1] != '#' && i < MAX); return i; } void Print(char exp[], int len) { int i; for(i=0; i= '0' && ch <= '9') //如果是数字,直接存入数组 exp[t++]=ch; else if(ch == '(') //如果是左括号,入栈 stack[++t......

阅读全文(7229) | 评论:1

栈与队列的例程(2006-05-05 19:57:00)

摘要:栈与队列,是很多学习算法的同学遇到第一只拦路虎,很多人从这一章开始坐晕车,一直晕到现在。所以,理解栈与队列,是走向算法高手的一条必由之路。栈与队列的题目涉及面很广,也很灵活。但是也是很实用的呢。 1.用队列来走一个4X4的迷宫,具体严本上有算法,这里只是实现。 #include #define m 4 #define n 4 int mg[m+1][n+1]; struct mgque { int x,y,pre; }mgque[25];/*队列:用来存路径*/ struct zl { int x,y; }zl[5];/*四个方向的增量*/ int outlj(struct mgque mgque[],int rear) { int i; i=rear; do{ printf("(%d,%d)",mgque[i].x,mgque[i].y); i=mgque[i].pre; }while(i!=0); }/*输出用rear反方向输出*/ int mglj() { int x,y,i=1,j=1,d,find;/*d是用来循环的增量*/ int rear=0,front=0; mgque[0].x=1;mgque[0].y=1;mgque[0].pre=-1; mg[1][1]=-1;/*迷宫左上第一个,若为0可通,标志为-1防止重复*/ find=0; while(front<=rear&&!find) { x=mgque[front].x;y=mgque[front].y; for(d=1;d<=4;d++) { i=x+zl[d].x; j=y+zl[d].y; if(mg[i][j]==0) { rear++; mgque[rear].x=i; mgque[rear].y=j; mgque[rear].pre=front; mg[i][j]=-1; } if((i==m)&&(j==n)) { find=1; outlj(mgque,rear); return 1; } }/*如果方向上的值为0表示可以通,入队,保存队列静态下标pre*/ front++; } printf("no way!"); return 0; } int main() { int i,j; /*下面初始化迷宫*/ for(i=1;i<=......

阅读全文(4346) | 评论:0