C语言必学：汉诺塔递归算法详解

C语言初学者必学经典算法与逻辑基础1、 塔在河内2、 河内塔问题是由法国人M.克劳斯也就是被称作卢卡斯的那位提出的它是一道堪称经典的具有递归性质的数学方面的难题。3、 有史以来有一座被众口称道为神塔的建筑它是由三根石柱稳稳当当支撑着的在初始的时候神在第一根柱子上依照大小顺序把六十四个金盘一个一个叠放开来其中大小最大的那个金盘放置在最底下而大小最小的那个金盘则放置在最顶端有一群僧侣必须把所有这些金盘转移到第三根柱子上去在进行移动金盘这个动作的时候务必得始终保持大盘处于下方、小盘处于上方这个状态并且每一天仅仅能够移动一个盘子当所有金盘都成功实现转移的那一日神塔就会崩塌整个世界也将会迎来终结。4、 解法5、 若柱子被标记成A、B、C那就需要从A移到C。要是只有一个盘子那就直接移到C要是有两个盘子那就借助B当作辅助柱来完成转移。6、 当盘子的数量超出两个的时候能够把第三个还有其余后面的盘子暂且进行遮盖处理只是针对前段处于前面位置的两个盘子展开处理。每一回执行从A这个位置到B这个位置、从A这个位置到C这个位置、从B这个位置到C这个位置这三步操作那被遮盖住的部分就借助递归的方式在程序的内部自行进行处理进而简化了整个的过程。7、 设有n个盘子完成移动所需次数是2的n次方减1 盘子数量为64时总次数为2的64次方减1 也就是18446744073709551615次 这个数字极其庞大 约相当于5000个世纪 若每秒移动一个盘子 大约需5850亿年才能完成整个过程 足见耗时之久。8、 编写代码实现9、 创立一个被称作 hanoi 的函数该函数含有四个参数借助这四个参数来达成汉诺塔问题的递归处理流程。10、 {11、 将第n张表从A移动到C输出移动步骤信息。12、 }13、 将n-1个盘子从B借助A移动到C。14、 }15、 }16、 为什么会采用if - else语句是由于它适用于处于两种情形的状况要是仅仅存在一种情况会怎么样要是有三种或者更多的情况又会如何包含这些方面这些问题是值得我们深入地去思考以及探讨的。17、 主函数入口接收命令行参数数量与参数数组程序执行起点。18、 {19、 请输入要输入的盘数20、 调用那个被称作hanoi的自定义函数它要传入参数n还有三个字符A、B、C之后执行与之相应的操作。21、 }22、 费氏数列属于递推数列范畴其首项是0第二项是1从第三项起每一项都是它前面两项的和。23、 欧洲13世纪时有个名为斐波那契较有名气的数学家他的著作里首先系统地介绍了斐波那契数列。24、 起初存在孤零零一只兔子一个月过后一下子变成两只兔子两个月之后便有了三只兔子三个月之后居然出现五只兔子这会儿新生的兔子开始具备生育能力一只兔子每月会诞下一只小兔子而降生的小兔子在出生一个月之后也开启了繁殖的进程数量依照这样的规律持续不断地增长。25、 要是对这个例子存有困惑借助图示就能清晰呈现需要留意新诞的小兔子要经历一个月的成长才可繁衍后代植物生长也依照类似的规律来进行这一规律名为斐波那契数列通常称作费氏数列它的数列为 1、1、2、3、5、8、13、21、34、55、89……每一项都是前两项的总和在自然界中普遍存在。26、 解法:27、 第一费氏数列存在这样一种定义第二当n大于1这个条件达成的时候fn的取值等于前两项之和第三当n为0或者1的情况出现时fn的值等于n本身。28、 编写程序代码29、 {30、 请输入斐波那契数列的长度。31、 初始化斐波那契数列数组首项设为0。32、 对数组展开遍历操作同时更新其中元素的值每一项要等于处在前面的两项的数值相加之和以此来达成斐波那契数列的那种计算功能。33、 遍历数组输出重新赋值后的Fib数值。34、 }35、 帕斯卡三角形36、 此程序的结构相当复杂它包含了多个知识要点。能够通过把一到十按照次序代入进去以手动方式模拟执行的进程一步步地剖析每一步的运行情形进而深入领会程序的逻辑以及工作机制。37、 编写程序代码38、 拿当前的值去乘上n减去i再加上一之后又拿这结果去除以i通过循环迭代的方式来达到组合数计算的目的。39、 }40、 {41、 于n等于1之际循环变量r自0至1逐个取值。要是r值为0那就输出11个空格设若r值并非0那就先搞出一个空格咧接着去调用combi(1,1)函数并且输出结果1。这整个过程凭借操控空格数量以及组合数计算达成特定格式的打印成效咧。42、 {43、 设置排版参数初始化变量i。44、 {45、 }46、 }47、 排版设置到此结束48、 }49、 }50、 }51、 三色棋算法趣谈巧妙排列红白蓝三色棋子52、 说明53、 将数组按三种不同值作分类的问题最初是由荷兰计算机科学家E.W. Dijkstra提出的因他的国籍背景他把这个问题称作荷兰国旗问题不过后来大多数学者采用三色旗这一更为常用的名称来描述这一经典算法问题因为该问题跟旗帜的颜色分区在形象上是有类比关系的。54、 有一条挂着红、白、蓝三种颜色旗子的绳子其初始排列没有顺序。需要把旗子依照蓝、白、红的顺序来排列并且每次仅仅能够交换相邻的两个旗子。目的是借助最少的交换次数达成排序整个过程仅仅能在绳子上开展不可以增加或者移除旗子也不可以进行跳跃式的移动。55、 编写代码实现56、 于一条绳子之上进行移动在程序里就好比单单使用一个数组而并不借助其他的辅助数组。其解法相当直观去想象移动旗帜从绳子的一端起始碰到蓝色旗子便向前移动白色的留在中间位置红色的则向后移动依照次序调整位置最终达成排序。57、 要实现最少移动次数需掌握一定技巧。58、 若图中W处为白色则将未处理部分移入白色组并令W加1。59、 在W所处位置以蓝色呈现之际把B跟W所对应的元素予以交换并且让B和W各自加上1这意味着两个组别皆增添了一个元素。要是W所在的位置是红色那就将W与R对应的元素进行互换与此同时R减去1这代表着未处理的区域减少了一个元素。整个这样的过程借助指针的移动达成分类当W碰到蓝色时B和W都向后移动一位当W碰到红色时与R交换并且使R向前移动一位。60、 留意一下B、W、R并非是用来表示三种颜色旗子具体数量的仅仅是被用于指示移动位置的索引罢了。移动于何时结束呢刚开始的时候R是指向未处理部分末尾的也就是旗子总数对应的位置。随着处理的持续进行当R的索引值比W的索引值小时这表明所有剩余未处理的旗子都是红色的排序已然完成在这个时候就能够终止操作了。也就是当r小于w时所有旗子都已成为红色过程便结束了。61、 三色棋算法问题巧妙排列红白蓝三色棋子。62、 说明63、 三色旗问题最初是由荷兰计算机科学家E.W. Dijkstra提出来的因为其具有的国籍背景所以他把它称作荷兰国旗问题。由于这个问题有将数组按照三种不同的值来进行划分的情况形象地跟旗帜的三色排列作类比多数后续的研究者更倾向于采用三色旗这个名称来对该算法问题进行描述。64、 存在一条挂着红、白、蓝三种颜色旗子的绳子其最初排排列没有秩序 要求借由交换操作把旗子依照蓝、白、红的顺序去排列 每次仅能交换两个旗子的位置 并且所有操作都得在绳子上达成 怎样去安排交换顺序 才可以让移动次数最少呢65、 解法66、 在一条绳子之上进行移动这等同于在编程期间仅仅启用一个数组而并非借助其他的辅助数组。其解法是极为直观的去想象移动旗帜的情景自绳子的一端起始当遭遇蓝色旗子之时便向前进行移动白色旗子维持在居中的状态红色旗子则向后移动依照这样的规则逐步地去调整位置如此便能够完成排序了。67、 要使移动次数最少需掌握一定技巧。68、 若图中W处为白色则将W加1把未处理区域归入白色组。69、 要是W区域呈现蓝色那就交换B与W两个地域的元素并且把两者的索引都增加1这意味着两组各自增添一个元素要是W所在位置是红色那么就交换W与R的元素与此同时R索引减少1这表明未处理区域削减一个元素。70、 B、W、R并非代表各颜色旗子的数量而是用于指示移动位置的指针。初始的时候R指向最后的位置。随着操作不断进行当R的索引小于W的索引时这表明所有非红色旗子已处理完毕后续全都是红色旗子此时便可以停止移动整个过程随之就结束了。71、 定义红色为字符r仅是普通字符常量无特殊含义。72、 交换两个变量x和y的值使其内容互换。73、 {74、 {75、 当写指针没有超过读指针的时候循环去执行要是是白色的话那么写指针就增加一要是是蓝色的话那就和白色进行交换并且同时推进蓝色指针与白色指针要是是红色的话那就和红色交换红色指针向前移动。一旦红色指针处于白色指针之前的时候这就表明所有的元素已经按照红、白、蓝的顺序排列好了排序就结束了。76、 {77、 当红旗数量少于白旗时所有旗帜均为红色此时结束。78、 红色关系中w小于r时r的红色属性减一。79、 }80、 }81、 }