汉诺塔问题的重点是分析移动的规则

汉诺塔问题的重点是分析移动的规则，找到规律和边界条件。

若需要将n个盘子从A移动到C就需要（1）将n-1个盘子从A移动到B；（2）将你第n个从A移动到C；（3）将n-1个盘子再从B 移动到C，这样就可以完成了。如果n!=1，则需要递归调用函数，将A上的其他盘子按照以上的三步继续移动，直到达到边界条件n=1为止。

思路清楚了，程序就好理解了。程序中的关键是分析好每次调用移动函数时具体的参数和对应的A、B、C塔的对应的关系。下面来以实际的例子对照程序进行说明。

①move(int n,int x,int y,int z)

②{

③if (n==1)

④printf("%c-->%c\n",x,z);

⑤else

⑥{

⑦move(n-1,x,z,y);

⑧printf("%c-->%c\n",x,z);

⑨{getchar();}//此句有必要用吗？感觉可以去掉的吧

⑩move(n-1,y,x,z);

}

}

比如有4个盘子，现在全部放在A塔上。盘子根据编号为1、2、3、4依次半径曾大。现在要将4个盘子移动到C上，并且是按原顺序罗列。首先我们考虑如何才可以将4号移动到C呢？就要以B为中介，首先将上面的三个移动到B。此步的操作也就是程序中的①开始调入move函数（首次调用记为一），当然现在的n=4，然后判断即③n！=1所以不执行④而是到⑤再次调用move函数（记为二）考虑如何将3个盘移动到B的方法。此处是递归的调用所以又一次回到①开始调入move函数，不过对应的参数发生了变化，因为这次要考虑的不是从A移动4个盘到C，而是要考虑从A如何移动移动3个盘到B。因为n=3，故不可以直接移动要借助C做中介，先考虑将两个移动到C的方法，故再一次到⑤再一次递归调用move函数（记为三）。同理两个盘还是不可以直接从A移动到C所以要以B为中介考虑将1个移动到B的过程。这次是以B为中介，移动到C为目的的。接下来再一次递归调用move函数（记为四），就是移动到B一个，可以直接进行。程序执行③④句，程序跳出最内一次的调用（即跳出第四次的调用）返回上一次（第三次），并且从第三次的调用move 函数处继续向下进行即⑧，即将2号移动到了C，然后继续向下进行到

⑩，再将已经移到B上的哪一个移回C，这样返回第二次递归（以C 为中介将3个盘移动到B的那次）。执行⑧，将第三个盘从A移动到B，然后进入⑩，这次的调用时因为是将C上的两个盘移到B以A

为中介，所以还要再一次的递归调用，对应的参数传递要分析清楚，谁是原塔谁是目标塔，谁是中介塔。过程类似于上面的分析，这里不再重复论述了。

《递归算法与递归程序》教学设计

递归算法与递归程序 岳西中学：崔世义一、教学目标 1知识与技能 (1) ?认识递归现象。 (2) ?使用递归算法解决冋题往往能使算法的描述乘法而易于表达 (3) ?理解递归三要素：每次递归调用都要缩小规模；前次递归调用为后次作准备：递归调用必须有条件进行。 (4) ?认识递归算法往往不是咼效的算法。 (5) ? 了解递归现象的规律。 (6) ?能够设计递归程序解决适用于递归解决的问题。 (7) ?能够根据算法写出递归程序。 (8) ? 了解生活中的递归现象，领悟递归现象的既有重复，又有变化的特点，并且从中学习解决问题的一种方法。 2、方法与过程 本节让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习(2) 和练习(3)这两道题目的形式相差很远，但方法和答案却是完全相同的练习，体会其中的奥妙，加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。 3、情感态度和价值观 结合高中生想象具有较强的随意性、更富于现实性的身心发展特点，综合反映出递归算法的特点，以及递归算法解答某些实践问题通常得很简洁，从而激发学生对程序设计的追求和向往。 二、重点难点 1、教学重点 (1) 了解递归现象和递归算法的特点。 (2) 能够根据问题设计出恰当的递归程序。 2、教学难点 (1) 递归过程思路的建立。 (2) 判断冋题是否适于递归解法。 (3) 正确写出递归程序。 三、教学环境 1、教材处理 教材选自《浙江省普通高中信息技术选修：算法与程序设计》第五章，原教材的编排是以本节以斐波那契的兔子问题引人，导出递归算法，从而自 定义了一个以递归方式解决的函数过程。然后利用子过程解决汉诺塔的经典问题。 教材经处理后，让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习⑵ 和练习

汉诺塔问题的三种实现

// test_project.cpp : 定义控制台应用程序的入口点。//汉诺塔问题的 // //递归实现 /*#include "stdafx.h" #include using namespace std; int count=0;//记录移动到了多少步 void Move(int n,char From,char To); void Hannoi(int n,char From, char Pass ,char To); //把圆盘从From，经过pass,移动到To int main() { int n_count=0; cout<<"请输入圆盘个数:"; cin>>n_count; Hannoi(n_count,'A','B','C'); } void Move(int n,char From,char To)

{ count++; cout<<"第"<

/*后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放A B C； 若n为奇数，按顺时针方向依次摆放A C B。 （）按顺时针方向把圆盘从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘在柱子A，则把它移动到B；若圆盘在柱子B，则把它移动到C；若圆盘在柱子C，则把它移动到A。 （）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。 （）反复进行（）（）操作，最后就能按规定完成汉诺塔的移动。 所以结果非常简单，就是按照移动规则向一个方向移动金片： 如阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C 汉诺塔问题也是程序设计中的经典递归问题，下面我们将给出递归和非递归的不同实现源代码。*/ /*#include "stdafx.h" #include #include

汉诺塔问题与递归思想教学设计

一、教学思想（包括教学背景、教学目标） 1、教学背景 本课程“递归算法”，属于《数据结构与算法》课程中“栈和队列”章节的重点和难点。数据结构与算法已经广泛应用于各行各业的数据存储和信息处理中，与人们的社会生活密不可分。该课程是计算机类相关专业核心骨干课程，处于计算机学科的核心地位，具有承上启下的作用。不仅成为全国高校计算机类硕士研究生入学的统考科目，还是各企业招聘信息类员工入职笔试的必考科目。数据结构与算法课程面向计算机科学与技术、软件工程等计算机类学生，属于专业基础课。 2、教学大纲 通过本课程的学习，主要培养学生以下几个方面的能力： 1）理解递归的算法； 2）掌握递归算法的实现要素； 3）掌握数值与非数值型递归的实现方法。 根据学生在学习基础和能力方面的差异性，将整个课程教学目标分成三个水平：合格水平（符合课标的最低要求），中等以上水平（符合课标的基本要求），优秀水平（符合或超出课标提出的最高要求）。具体如下表：

二、课程设计思路（包括教学方法、手段） “递归算法”课程以故事引入、案例驱动法、示范模仿、启发式等多元化教学方法，设计课程内容。具体的课堂内容如下所示：

1 1 2 3 3 7 4 15 5 31 count = 2n-1 思考：若移动速度为1个/秒，则需要 (264-1)/365/24/3600 >= 5849亿年。 四、总结和思考 总结： 对于阶乘这类数值型问题，可以表达成数学公式，然后从相应的公式入手推导，解决这类问题的递归定义，同时确定这个问题的边界条件，找到结束递归的条件。 对于汉诺塔这类非数值型问题，虽然很难找到数学公式表达，但可将问题进行分解，问题规模逐渐缩小，直至最小规模有直接解。 思考： 数值型问题：斐波那契数列的递归设计。 非数值型问题：八皇后问题的递归设计。阐述总结知识拓展 三、教学特色（总结教学特色和效果） 递归算法课程主要讨论递归设计的思想和实现。从阶乘实例入手，由浅入深，层层深入介绍了递归的设计要点和算法的实现。从汉诺塔问题，通过“边提问，边思考”的方式逐层深入地给出算法的分析和设计过程。通过故事引入、案例导入、实例演示、PPT展示、实现效果等“多元化教学方式”，努力扩展课堂教学主战场。加上逐步引导、问题驱动，启发学生对算法的理解，并用实例演示展示算法的分析过程，在编译环境下实现该算法，加深对算法实现过程的认识。 1、知识点的引入使用故事诱导法讲授 通过“老和尚讲故事”引入函数的递归调用，并通过“世界末日问题” 故事引入非数值型问题的递归分析，激发学习积极性，挖掘学生潜能。

关于制定移动业务专属服务经理在线

改套餐业务是当前服务经理在线受理的一项主要业务，为做好改套餐业务受理服务过程记录，为用户提供便利服务避免投诉纠纷，特制定专属服务经理在线受理用户改套餐规范，具体内容如下： 一、适用范围 2G、3G专属服务经理在线受理用户改套餐业务。 二、操作规范 1、专属服务经理受理用户改套餐需求时，先审核用户是否 符合改套餐条件，对符合改套餐的用户，引导用户发短信申请（同时要向用户说明改套餐赠款清零问题）。2、用户短信申请改套餐工作流如下： 步骤1：服务经理给用户下发引导短信。 2G用户申请改套餐短信内容：尊敬的用户，您好！办理改套餐须凭短信办理，请您编辑gtc+套餐名称（根据用户申请需求适时调整，如66A）发送到10010752申请办理。更改套餐后，您帐户上未使用完的赠款余额将清零。改套餐业务在每月的1-23日申请可当月更改次月生效，25-31日申请将在次月更改第三个月生效。您的服务经理***。（发送端口：10010022） 3G用户申请改套餐短信内容：尊敬的用户，您好！办理改套

餐须凭短信办理，请您编辑gtc+套餐名称（根据用户申请需求适时调整，如66A）发送到10010752申请办理。更改套餐后，您帐户上未使用完的赠款余额将清零。改套餐业务在每月的1-27日申请可当月更改次月生效，27-31日申请将在次月更改第三个月生效。您的服务经理***。（发送端口：10010022） 步骤2：用户发短信至10010752申请改套餐。 短信内容：gtc+套餐名称（套餐名称为当前2G、3G在用套餐，如66A，视用户改套餐需求而变动）。 步骤3：10010752端口自动下行给用户回复一条短信。 第一次申请下行短信内容：尊敬的用户：您申请改套餐需求已登记，我们将在2个工作日内为您受理，成功改套餐后将会有短信告知，请您留意。特别向您说明，改套餐后您帐户上未使用完的赠款余额将清零。惠州联通。 如同一号码同一个月内申请2次或以上，第二次申请下行短信内容：为：尊敬的用户，您本月已申请过改套餐业务，如您有需求，请您下月再申请。谢谢！惠州联通 步骤4：两个专属团队每天安排专人提取用户短信申请改套餐数据，安排专人受理改套餐操作。（节假日除外） 步骤5：成功改套餐后，BSS系统将自动触发业务成功办理短信。

汉诺塔非递归算法C语言实现

汉诺塔非递归算法C语言实现 #include #include #define CSZL 10 #define FPZL 10 typedef struct hanoi { int n; char x,y,z; }hanoi; typedef struct Stack { hanoi *base,*top; int stacksize; }Stack; int InitStack(Stack *S) { S->base=(hanoi *)malloc(CSZL*sizeof(hanoi)); if(!S->base) return 0; S->top=S->base; S->stacksize=CSZL; return 1; } int PushStack(Stack *S,int n,char x,char y,char z) { if(S->top-S->base==S->stacksize) { S->base=(hanoi *)realloc(S->base,(S->stacksize+FPZL)*sizeof(hanoi)); if(!S->base) return 0; S->top=S->base+S->stacksize; S->stacksize+=FPZL; } S->top->n=n; S->top->x=x; S->top->y=y; S->top->z=z; S->top++; return 1; } int PopStack(Stack *S,int *n,char *x,char *y,char *z) { if(S->top==S->base)

汉诺塔问题

实验二知识表示方法 梵塔问题实验 1．实验目的 （1）了解知识表示相关技术； （2）掌握问题规约法或者状态空间法的分析方法。 2．实验内容（2个实验内容可以选择1个实现） （1）梵塔问题实验。熟悉和掌握问题规约法的原理、实质和规约过程；理解规约图的表示方法； （2）状态空间法实验。从前有一条河，河的左岸有m个传教士、m个野人和一艘最多可乘n人的小船。约定左岸，右岸和船上或者没有传教士，或者野人数量少于传教士，否则野人会把传教士吃掉。搜索一条可使所有的野人和传教士安全渡到右岸的方案。 3．实验报告要求 （1）简述实验原理及方法，并请给出程序设计流程图。 我们可以这样分析： （1）第一个和尚命令第二个和尚将63个盘子从A座移动到B座； （2）自己将底下最大的盘子从A移动到C； （3）再命令第二个和尚将63个盘子从B座移动到C；（4）第二个和尚命令第三个和尚重复（1）（2）（3）；以此类推便可以实现。这明显是个递归的算法科技解决的问

题。 （2）源程序清单： #include #include using namespace std; void main() { void hanoi(int n,char x,char y,char z);

int n; printf("input the number of diskes\n"); scanf("%d",&n); hanoi(n,'A','B','C'); } void hanoi(int n,char p1,char p2,char p3) { if(1==n) cout<<"盘子从"<

汉诺塔问题实验报告

1.实验目的： 通过本实验，掌握复杂性问题的分析方法，了解汉诺塔游戏的时间复杂性和空间复杂性。 2.问题描述： 汉诺塔问题来自一个古老的传说：在世界刚被创建的时候有一座钻石宝塔（塔A),其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A 上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。 3.算法设计思想： 对于汉诺塔问题的求解，可以通过以下三个步骤实现： (1)将塔A上的n-1个碟子借助塔C先移到塔B上。 (2)把塔A上剩下的一个碟子移到塔C上。 (3)将n-1个碟子从塔B借助于塔A移到塔C上。 4.实验步骤： 1.用c++ 或c语言设计实现汉诺塔游戏； 2.让盘子数从2 开始到7进行实验，记录程序运行时间和递 归调用次数； 3.画出盘子数n和运行时间t 、递归调用次数m的关系图， 并进行分析。 5.代码设计： Hanio.cpp #include"stdafx.h" #include #include #include void hanoi(int n,char x,char y,char z) { if(n==1) { printf("从%c->搬到%c\n",x,z); } else { hanoi(n-1,x,z,y); printf("从%c->%c搬到\n",x,z); hanoi(n-1,y,x,z); }

汉诺塔问题的重点是分析移动的规则

汉诺塔问题的重点是分析移动的规则，找到规律和边界条件。 若需要将n个盘子从A移动到C就需要（1）将n-1个盘子从A移动到B；（2）将你第n个从A移动到C；（3）将n-1个盘子再从B 移动到C，这样就可以完成了。如果n!=1，则需要递归调用函数，将A上的其他盘子按照以上的三步继续移动，直到达到边界条件n=1为止。 思路清楚了，程序就好理解了。程序中的关键是分析好每次调用移动函数时具体的参数和对应的A、B、C塔的对应的关系。下面来以实际的例子对照程序进行说明。 ①move(int n,int x,int y,int z) ②{ ③if (n==1) ④printf("%c-->%c\n",x,z); ⑤else ⑥{ ⑦move(n-1,x,z,y); ⑧printf("%c-->%c\n",x,z); ⑨{getchar();}//此句有必要用吗？感觉可以去掉的吧 ⑩move(n-1,y,x,z); } }

比如有4个盘子，现在全部放在A塔上。盘子根据编号为1、2、3、4依次半径曾大。现在要将4个盘子移动到C上，并且是按原顺序罗列。首先我们考虑如何才可以将4号移动到C呢？就要以B为中介，首先将上面的三个移动到B。此步的操作也就是程序中的①开始调入move函数（首次调用记为一），当然现在的n=4，然后判断即③n！=1所以不执行④而是到⑤再次调用move函数（记为二）考虑如何将3个盘移动到B的方法。此处是递归的调用所以又一次回到①开始调入move函数，不过对应的参数发生了变化，因为这次要考虑的不是从A移动4个盘到C，而是要考虑从A如何移动移动3个盘到B。因为n=3，故不可以直接移动要借助C做中介，先考虑将两个移动到C的方法，故再一次到⑤再一次递归调用move函数（记为三）。同理两个盘还是不可以直接从A移动到C所以要以B为中介考虑将1个移动到B的过程。这次是以B为中介，移动到C为目的的。接下来再一次递归调用move函数（记为四），就是移动到B一个，可以直接进行。程序执行③④句，程序跳出最内一次的调用（即跳出第四次的调用）返回上一次（第三次），并且从第三次的调用move 函数处继续向下进行即⑧，即将2号移动到了C，然后继续向下进行到 ⑩，再将已经移到B上的哪一个移回C，这样返回第二次递归（以C 为中介将3个盘移动到B的那次）。执行⑧，将第三个盘从A移动到B，然后进入⑩，这次的调用时因为是将C上的两个盘移到B以A

汉诺塔问题的非递归算法分析

汉诺塔递归与非递归算法研究 作者1，作者2，作者33 (陕西师范大学计算机科学学院，陕西西安 710062) 摘要: 摘要内容(包括目的、方法、结果和结论四要素) 摘要又称概要,内容提要.摘要是以提供文献内容梗概为目的,不加评论和补充解释,简明,确切地记述文献重要内容的短文.其基本要素包括研究目的,方法,结果和结论.具体地讲就是研究工作的主要对象和范围,采用的手段和方法,得出的结果和重要的结论,有时也包括具有情报价值的其它重要的信息.摘要应具有独立性和自明性,并且拥有与文献同等量的主要信息,即不阅读全文,就能获得必要的信息. 关键词:关键词1; 关键词2；关键词3；……（一般可选3~8个关键词，用中文表示，不用英文 Title 如：XIN Ming-ming , XIN Ming (1.Dept. of ****, University, City Province Zip C ode, China；2.Dept. of ****, University, City Province Zip C ode, China；3.Dept. of ****, University, City Province Zip C ode, China) Abstract: abstract（第三人称叙述，尽量使用简单句；介绍作者工作（目的、方法、结果）用过去时，简述作者结论用一般现在时） Key words: keyword1;keyword2; keyword3;……（与中文关键词对应，字母小写(缩略词除外)）； 正文部分用小5号宋体字，分两栏排，其中图表宽度不超过8cm.。设置为A4页面 1 引言（一级标题四号黑体加粗） 这个问题当时老和尚和众僧们，经过计算后，预言当所有的盘子都从基柱A移到基座B上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。其实，不管这个传说的可信度有多大，如果考虑把64个盘子，由一个塔柱上移到另一根塔柱上，并且始终保持上小下大的顺序。假设有n个盘子，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7,且f(k+1)=2*f(k)+1。此后不难证明f(n)=2n-1。n=64时， f(64)= 2^64-1=18446744073709551615 假如每秒钟一次，共需多长时间呢？一年大约有 31536926 秒，计算表明移完这些金片需要5800多亿年，比地球寿命还要长，事实上，世界、梵塔、庙宇和众生都早已经灰飞烟灭。 对传统的汉诺塔问题，目前还有不少的学者继续研究它的非递归解法，本文通过对递归算法的研究……. 提示：（1）可以定义问题的规模n,如盘子的数量；（2）塔柱的数量（目前有部分理论可以支撑，不妨用计算机实现）分析规模的变化与算法的复杂度比较。（3）可以对经典的汉诺塔问题条件放松、加宽，如在经典的汉诺塔问题中大盘只能在小盘下面，放松其他条件可以定义相邻两个盘子必须满足大盘只能在小盘下面。其它盘子不作要求。 2 算法设计 2.1 汉诺塔递归算法描述（二级标题小五黑体加粗） 用人类的大脑直接去解3，4或5个盘子的汉诺塔问题还可以，但是随着盘子个数的增多，问题的规模变的越来越大。这样的问题就难以完成，更不用说吧问题抽象成循环的机器操作。所以类似的问题可用递归算法来求解。下面n个盘的汉

买一个手机靓号需要多少钱

随着手机靓号市场交易越来越活越，倾向于使用靓号的人群也随之扩大，这也是很多想要购买人的问题。手机靓号多少钱。之前很多人买手机号码都是直接到营业厅购买，我们知道营业厅号码都是很普通的数字杂乱也不好记。想要选到合适的靓号在营业厅往往是没有的，很多靓号资源往往已经被很多代理商或者个人提前买走了。由于大部分人群都没有在网上购买过手机号码的经历，也不知道哪一个平台值得信任，真的为我们广大爱号者提供服务。这里就给大家推荐一家选号，买号的一个平台------远特喜牛。 远特（北京）通讯技术有限公司坐落于北京朝阳区酒仙桥路10号恒通商务园B，成立于2004年10月，于2014年获得工信部虚拟运营商牌照，喜牛是一款可

以24小时随时随地开卡，选号的平台，百万手机号码随心选择，且流量，资费要比三大运营商便宜很多。 远特喜牛利用互联网优势将传统的地面销售延伸到无国界的空中销售层面，让您的号码走出门口，让全市、乃至全省、全国的网民都有机会搜索到您的号码及增值产品。这种在线的网络营销模式必将打破传统的服务观念，让顾客足不出户即可搜索和采购到心仪的电话号码，一站式体验完成有关电话号码的全程服务。唯有让顾客先找到、了解到、信任到，产品才有机会面临更多的选择和成交机会，增加曝光率提升销售率。现在说的靓号多指由阿拉伯数字组成的连续相同的号码，或含特殊意义的吉祥号码，不同的数字组合在一起就对于每个人来说有着不同的意义。 号码都被赋予着丰富的文化内涵，如九五至尊，六六大顺。号码对不同的人更有着特殊的意义，如生日号码，纪念日号码。现在说的靓号多指由阿拉伯数字组成的连续相同的号码，或含特殊意义的吉祥号码。

课程实践报告_汉诺塔

课程实践报告 题目：汉诺塔 姓名： 学号： 班级： 日期：

一实践目的 1、初步具备根据应用需求选择合理数据结构并进行算法设计的能力； 2、进一步提升C语言的应用能力； 3、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 4、提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 5、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风； 6、提升文档写作能力。 二问题定义及题目分析 汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。这是一个著名的问题，几乎所有的教材上都有这个问题。由于条件是一次只能移动一个盘，且不允许大盘放在小盘上面，所以64个盘的移动次数是：18，446，744，073，709，551，615 这是一个天文数字，若每一微秒可能计算(并不输出)一次移动，那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔，但很难用计算机解决64层的汉诺塔。后来，这个传说就演变为汉诺塔游戏: 1.有三根杆子A，B，C。A杆上有若干圆盘。2.每次移动一块圆盘，小的只能叠在大的上面。3.把所有圆盘从A杆全部移到C杆上。经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动圆盘：如3阶汉诺塔的移动：A→C，A→B，C→B，A→C，B→A，B→C，A→C。 程序所能达到的功能： 用户只需要输入所需的层数即可，程序会自动计算出最终需要的步骤，并同时给出中间移动的过程。 三概要设计 1、设计思想 如果盘子为1，则将这个盘子从塔座A移动到塔座C；如果不为1，则采用递归思想。将塔座A的前n-1个盘子借助C盘（即目的盘）移到塔座B，移后，此时C为空座，那我们就可以将塔座A的第n个盘子移到塔座C了。接下来就将塔座B的n-1个盘子借助A移到塔座C，从而完成盘子的移动。 2、数据类型 结构体：用来存放盘子的栈。同时，在函数的参数中还用到了结构体类型的引用。 其他类型：基本的数据类型，包括整形，字符型。用来存放临时变量。 3、主要模块

汉诺塔问题非递归算法详解

Make By Mr.Cai 思路介绍： 首先，可证明，当盘子的个数为n 时，移动的次数应等于2^n - 1。 然后，把三根桩子按一定顺序排成品字型（如：C ..B .A ），再把所有的圆盘按至上而下是从小到大的顺序放在桩子A 上。 接着，根据圆盘的数量确定桩子的排放顺序： 若n 为偶数，按顺时针方向依次摆放C ..B .A ； 若n 为奇数，按顺时针方向依次摆放B ..C .A 。 最后，进行以下步骤即可： （1）首先，按顺时针方向把圆盘1从现在的桩子移动到下一根桩子，即当n 为偶数时，若圆盘1在桩子A ，则把它移动到B ；若圆盘1在桩子B ，则把它移动到C ；若圆盘1在桩子C ，则把它移动到A 。 （2）接着，把另外两根桩子上可以移动的圆盘移动到新的桩子上。 即把非空桩子上的圆盘移动到空桩子上，当两根桩子都非空时，移动较小的圆盘。 （3）重复（1）、（2）操作直至移动次数为2^n - 1。 #include #include using namespace std; #define Cap 64 class Stake //表示每桩子上的情况 { public: Stake(int name,int n) { this->name=name; top=0; s[top]=n+1;/*假设桩子最底部有第n+1个盘子，即s[0]=n+1，这样方便下面进行操作*/ } int Top()//获取栈顶元素 { return s[top];//栈顶 } int Pop()//出栈 { return s[top--];

} void Push(int top)//进栈 { s[++this->top]=top; } void setNext(Stake *p) { next=p; } Stake *getNext()//获取下一个对象的地址 { return next; } int getName()//获取当前桩子的编号 { return name; } private: int s[Cap+1];//表示每根桩子放盘子的最大容量 int top,name; Stake *next; }; void main() { int n; void hanoi(int,int,int,int); cout<<"请输入盘子的数量："; cin>>n; if(n<1) cout<<"输入的盘子数量错误!!!"<

汉诺塔的递归求解分析

汉诺塔的递归求解分析 学完函数，就马上出了道经典的汉诺塔来，书里说是把递归提前拿来研究学习了，这题目实在是把我弄晕了。几天都在时时想这个题目。 递归是数学归纳法的逆过程。 递归函数是直接或通过另一个函数间接调用自己的函数。C语言的特点就是允许函数的递归调用。 如果一个问题要用递归解决，得符合以下的条件： 1，该问题要能转换成一个新问题，而新问题的解决方法要和原来的问题相同，只是复杂度有所减少而已。既是要有一定的规律。如求n！。 2、这个问题当简单到一定程度就可以解决，而不用再继续简化。（即需要一个结束递归的条件。否则无限的递归下去，最终会导致系统资源枯竭系统崩溃）。 3、问题用其他方法解决非常困难或不如用递归解决来的简单，（所有递归能解决的问题都能用迭代{非递归}来解决）这个条件是非必要的，但人总需要简单。 ? 要用递归解决问题，我们必须分析下列问题： 1、递归的参数，用递归解决的问题通常都比较复杂，规模比较大，要找出决定递归复杂度，规模的参数，比如n！，决定的递归复杂度、规模的就是n。 2、找出递归结束的标志，没有递归结束的条件，将无限循环。造成的后果是严重的。 3、找出递归的通式，才可以进一步简化问题。（通常这是比较困难的）（比如：n！的通式就是n*（n-1）！，而且是可以不断简化直到到达结束递归的边界值） ? ? ? 一般的格式是： ? if 结束条件1 表达式1（赋予边界值1） else if 结束条件2 表达式2（赋予边界值2） . . . else 递归的解决问题的通式。 ? ? 汉诺塔的问题； 这个问题对于我这个初学者来说，确实棘手，对于执行的步骤很不理解，虽然递归不用去了解执行的步骤的。但是，不用去了解不等同于不了解。 一个庙里有三个柱子，第一个有64个盘子，从上往下盘子越来越大。要求庙里的老和尚把这64个盘子全部移动到第三个柱子上。移动的时候始终只能小盘子压着大盘子。 1、此时老和尚（后面我们叫他第一个和尚）觉得很难，所以他想：要是有一个人能把前

汉诺塔C递归算法详细解答

汉诺塔C递归算法详细解答 程序如下： void move(char x,char y){ printf("%c-->%c\n",x,y); } void hanoi(intn,charone,chartwo,char three){ /*将n个盘从one座借助two座，移到three座*/ if(n==1) move(one,three); else{ hanoi(n-1,one,three,two); move(one,three); hanoi(n-1,two,one,three); } } main(){ int n; printf("input the number of diskes:"); scanf("%d",&n); printf("The step to moving %3d diskes:\n",n); hanoi(n,'A','B','C'); } Hanoi塔问题, 算法分析如下，设A上有n个盘子。 如果n=1，则将圆盘从A直接移动到C。 如果n=2，则： （1）将A上的n-1（等于1）个圆盘移到B上； （2）再将A上的一个圆盘移到C上； （3）最后将B上的n-1（等于1）个圆盘移到C上。 如果n=3，则： A）将A上的n-1（等于2，令其为n`）个圆盘移到B（借助于C），步骤如下：（1）将A上的n`-1（等于1）个圆盘移到C上。 （2）将A上的一个圆盘移到B。 （3）将C上的n`-1（等于1）个圆盘移到B。 B）将A上的一个圆盘移到C。 C）将B上的n-1（等于2，令其为n`）个圆盘移到C（借助A），步骤如下：（1）将B上的n`-1（等于1）个圆盘移到A。 （2）将B上的一个盘子移到C。 （3）将A上的n`-1（等于1）个圆盘移到C。到此，完成了三个圆盘的移动过程。

栈结构实现汉诺塔实验报告

数据结构 实 验 报 告 学院软件学院 年级2009级 班级班 学号 姓名 2010 年 3 月24 日

目录 一、实验内容 (1) 二、实验过程……………………………………….X 三、实验结果……………………………………….X

一、实验内容： 1、实验题目：栈结构实现汉诺塔 2、实验要求：有三个柱子A、B、C，A柱子上叠放有n个盘子，每个盘子都比它下面的盘自己小一点，要求借助柱子B，将柱子A上的所有盘子移动到柱子C上。要求一次只能移动一个盘子，且移动过程中大盘子不能放在小盘子的上面，只能小盘子放在大盘子的上面。 3、实验目标：了解并掌握栈的结构原理和基本操作，并用利用栈结构实现汉诺塔。了解递归的工作过程。

二、实验过程： 1、任务分配 2、设计思想 （1）将A柱子上n-1个盘子借助C柱子移到B柱子上，把A上剩下的一个盘子移到C上，将B上的n-1个盘子借助A移到C上 （2）建立三个栈作为汉诺塔，利用栈结构“先进后出”的特点，先进栈的盘子要后出来 3、需求分析 (1) 输入的形式和输入值的范围：输入盘子的个数n (2) 输出的形式：盘子的移动过程及最终的移动总次数 (3) 程序所能达到的功能：将A上的n个盘子借助B移到C上 (4) 测试数据： 4、概要设计 1).抽象数据类型 2).算法 a.栈模块：用来作为汉诺塔存入和去除圆盘，先进栈的圆盘后出来 b.汉诺塔模块：建立汉诺塔模型（将A上的n个盘子借助B移到C上）其中move函数用于实现圆盘的移动 c.主函数模块：接收处理命令（初始化数据） 5、详细设计 程序代码（含注释） 6、调试分析 （1）调试中的问题分析： a.在定义汉诺塔函数的数据类型时，开始使用的是void，但是与后面 main函数中定义的i类型不相符，且void函数无法返值，最后改为int 型 （2）算法的时空分析： a.时间复杂度：程序所花的时间正比于所输出的信息行数目，而信息行

汉诺塔问题 递归

题目描述Description 汉诺塔问题（又称为河内塔问题），是一个大家熟知的问题。在A，B，C 三根柱子上，有n个不同大小的圆盘（假设半径分别为1-n吧），一开始他们都叠在我A上（如图所示），你的目标是在最少的合法移动步数内将所有盘子从A塔移动到C塔。 游戏中的每一步规则如下： 1. 每一步只允许移动一个盘子（从一根柱子最上方到另一个柱子的最上方） 2. 移动的过程中，你必须保证大的盘子不能在小的盘子上方（小的可以放在大的上面，最大盘子下面不能有任何其他大小的盘子） 如对于n=3的情况，一个合法的移动序列式： 1 from A to C 2 from A to B 1 from C to B 3 from A to C 1 from B to A 2 from B to C 1 from A to C 给出一个数n，求出最少步数的移动序列

输入描述Input Description 一个整数n 输出描述Output Description 第一行一个整数k，代表是最少的移动步数。 接下来k行，每行一句话，N from X to Y，表示把N号盘从X柱移动到Y 柱。X,Y属于{A,B,C} 样例输入Sample Input 3 样例输出Sample Output 7 1 from A to C 2 from A to B 1 from C to B 3 from A to C 1 from B to A 2 from B to C 1 from A to C 数据范围及提示Data Size & Hint n<=10

#include #include //a为起始柱，b为临时住，c为终点柱 void hannuo(int n,char a,char b,char c) { if(n==1) printf("%d from %c to %c\n",n,a,c);//单独处理n=1，移向终点柱 else { hannuo(n-1,a,c,b);//将上方n-1个移向临时柱 printf("%d from %c to %c\n",n,a,c); //将第n个柱子移向终点柱 hannuo(n-1,b,a,c); //将n-1个柱子移向终点柱 } } int main() { int n; scanf("%d",&n); printf("%d\n",(int)pow(2,n)-1);//步数为2的n次方-1 hannuo(n,'A','B','C'); return 0; }

销售业务[2016]6号附件3：靓号最低消费规则示例

靓号最低消费规则示例 一、靓号最低消费为用户选择靓号后需执行的每月最低消费，有效时间均为长期。保留目前系统内最低消费按套餐应收的匹配规则：合约赠款可计算入靓号最低消费中，如：用户受理乐享4G-99 合约套餐，合约期内每月可获赠费40 元，并办理保底89 元的靓号；虽然用户实际月消费59 元，但因受理的套餐价值99 元，故不追加保底费用。二、主卡消费可抵扣副卡靓号最低消费。如：用户副卡选择保底49 元的靓号，主卡选择保底89 元的靓号，只要用户主卡套餐价值大于138 元，不需另行追收靓号保底费用。为避免规则上线后对收入的影响，结合程序改造完成时间，确定2016年4 月1 日后入网的副卡用户纳入主卡消费抵扣范围内，老副卡用户按原规则处理。 三、融合关联套餐消费可抵扣关联套餐内靓号最低消费。若号码对应紧融合套餐，紧融合套餐内号码的消费可直接计入靓号保底；若号码对应松散融合套餐，松散融合套餐相关联号码消费也可计入靓号最低消费中。如现有1290 礼包，套餐价值的169 元实际为手机乐享4G-99 元、宽带58 元、叠加包12 元的松散融合，系统中宽带58 元通过叠加包12 元与手机号码形成关联，故在叠加包内的主卡、副卡靓号保底合计在169 元内均不另外追收靓号保底；同时，超出套餐外的费用也均可抵扣主副卡号码保底。该规则适用于关联销售品内有2016 年4 月1日后入网的用户，若关联销售品内都是老用户，按原非关联抵 扣规则执行。 四、靓号最低消费打折规则。靓号最低消费有效时间均为长期，为做

好存量用户维系工作，处理靓号投诉争议，对靓号保底提供打折：对在网满两年的号码，靓号保底可打7 折；满四年及以上的号码，靓号保底可打5 折。

汉诺塔

汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

和汉诺塔故事相似的，还有另外一个印度传说：舍罕王打算奖赏国际象棋的发明人──宰相西萨·班·达依尔。国王问他想要什么，他对国王说：“陛下，请您在这张棋盘的第1个小格里赏给我一粒麦子，在第2个小格里给2粒，第3个小格给4粒，以后每一小格都比前一小格加一倍。请您把这样摆满棋盘上所有64格的麦粒，都赏给您的仆人吧！”国王觉得这个要求太容易满足了，就命令给他这些麦粒。当人们把一袋一袋的麦子搬来开始计数时，国王才发现：就是把全印度甚至全世界的麦粒全拿来，也满足不了那位宰相的要求。 那么，宰相要求得到的麦粒到底有多少呢？总数为 1+2+2^2 + … +2^63=2^64-1 等于移完汉诺塔的步骤数。我们已经知道这个数字有多么大了。人们估计，全世界两千年也难以生产这么多麦子！ 经典题目 有三根相邻的柱子，标号为A,B,C，A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，要把所有盘子一个一个移动到柱子B上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方，请问至少需要多少次移动，设移动次数为H(n）。 首先我们肯定是把上面n-1个盘子移动到柱子C上，然后把最大的一块放在B上，最后把C上的所有盘子移动到B上，由此我们得出表达式： H⑴ = 1 H(n) = 2*H(n-1）+1 (n>1） 那么我们很快就能得到H(n）的一般式： H(n) = 2^n - 1 (n>0) 并且这种方法的确是最少次数的，证明非常简单，可以尝试从2个盘子的移动开始证，你可以试试。 进一步加深问题（解法原创*_*）： 假如现在每种大小的盘子都有两个，并且是相邻的，设盘子个数为2n，问：⑴假如不考虑相同大小盘子的上下要多少次移动，设移动次数为J(n）；⑵只要保证到最后B上的相同大小盘子顺序与A上时相同，需要多少次移动，设移动次数为K(n）。 ⑴中的移动相当于是把前一个问题中的每个盘子多移动一次，也就是：

汉诺塔程序实验报告

竭诚为您提供优质文档/双击可除汉诺塔程序实验报告 篇一：汉诺塔程序实验报告 实验题目： hanoi塔问题 一、问题描述： 假设有三个分别命名为A，b和c的塔座，在塔座b上插有n个直径大小各不相同、从小到大编号为1，2，…，n 的圆盘。现要求将塔座b上的n个圆盘移至塔座A上并仍按同样顺序叠排，圆盘移动时必须遵守以下规则： （1）每次只能移动一个圆盘； （2）圆盘可以插在A，b和c中任一塔上； （3）任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。 要求：用程序模拟上述问题解决办法，并输出移动的总次数，圆盘的个数从键盘输入；并想办法计算出程序运行的时间。 二、算法思路：

1、建立数学模型： 这个问题可用递归法解决，并用数学归纳法又个别得出普遍解法： 假设塔座b上有3个圆盘移动到塔座A上： （1）"将塔座b上2个圆盘借助塔座A移动到塔座c上； （2）"将塔座b上1个圆盘移动到塔座A上； （3）"将塔座c上2个圆盘借助塔座b移动到塔座A上。 其中第2步可以直接实现。第1步又可用递归方法分解为： 1.1"将塔座b上1个圆盘从塔座x移动到塔座A； 1.2"将塔座b上1个圆盘从塔座x移动到塔座c； 1.3"将塔座A上1个圆盘从塔座Z移动到塔座c。 第3步可以分解为： 3.1将塔座c上1个圆盘从塔座Y移动到塔座b； 3.2将塔座c上1个圆盘从塔座Y移动到塔座A； 3.3将塔座b上1个圆盘从塔座x移动到塔座A。 综上所述：可得到移动3个圆盘的步骤为 b->A,b->c,A->c,b->A,c->b,c->A,b->A, 2、算法设计： 将n个圆盘由b依次移到A，c作为辅助塔座。当n=1时，可以直接完成。否则，将塔座b顶上的n-1个圆盘借助塔座A移动到塔座c上；然后将圆盘b上第n个圆盘移到塔

vb汉诺塔的递归算法与解析

汉诺塔的递归算法与解析 从左到右 A B C 柱大盘子 在下, 小盘子在上, 借助B柱将 所有盘子从A柱移动到C柱, 期 间只有一个原则: 大盘子只能 在小盘子的下面. 如果有3个盘子, 大中小号, 越小的越在上面, 从上面给盘子按顺序编号1(小),2(中),3(大), 后面的原理解析引用这里的编号. 小时候玩过这个游戏, 基本上玩到第7个,第8个就很没有耐心玩了,并且操作的动作都几乎相同觉得无聊. 后来学习编程, 认识到递归, 用递归解决汉诺塔的算法也是我除了简单的排序算法后学习到的第一种算法. 至于递归,简单来说就是方法内部自己调用自己, 同时也一定有一个结束点. 如果对方法调用栈了解的话,其实是很容易理解方法的调用过程的, 就是从主线程开始调用方法进行不停的压栈和出栈操作. 方法的调入就是将方法压入栈中, 方法的结束就是方法出栈的过程, 这样保证了方法调用的顺序流. 如果跟踪递归的调用情况会发现也是如此, 到最后一定是这个方法最后从栈中弹出回到主线程, 并且结束.

栈的特点:先进后出。比如一个方法 A 自己调用自己, 我用编号区分一下进栈过程:A -> A(1) -> A(2) -> A(3) 在A(3)时满足某种条件得以退出, 回到A(2), A(2)结束回到A(1), 再回到A, 出栈过程:A(3) -> A(2) -> A(1) -> A 对于递归,还有一个形象的认识,就是我小时候家里有一个柜子, 柜子两端都是玻璃, 头伸进柜子看一面镜子,会看到镜子里还有镜子, 然后镜子里还有镜子, 但和递归的特点不同的是这镜子的反射是没有尽头的, 只要眼睛一直能看到底的话. 了解完递归后, 再回头来看如何用递归的方式解决汉诺塔的问题. 案例 1 - 假设只有一个盘子的时候, 盘子数量N=1 只有一个步骤将第1个盘子从A移动到C, 为了对比方便我这样来描述这个步骤： 步骤盘子编号从柱子移动移动到柱子 1 1 A C 案例 2 - 如果有两个盘子, 盘子数量N = 2 步骤盘子编号从柱子移动移动到柱子 1 1 A B 2 2 A C 3 1 B C 案例 3 - 如果有三个盘子, 盘子数量N = 3 步骤盘子编号从柱子移动移动到柱子 1 1 A C