Python程序设计实践 教案 实验19 趣味算法

《Python程序设计实践教程》课程教案课题趣味算法教学目的

1.对于计算机科学而言，算法Algorithm是一个非常重要的概念它是程序设计的灵魂，是将实际问题与解决该问题的计算机程序建立联系的桥梁我们在编写任何一个计算机程序时无论使用什么编程语言，都不可避免地要进行算法设计2,本实验选取几个典型的趣味算法编程实例，讲解如何通过程序设计解决一些有趣的数学问题，使读者提高通过编程解决实际问题的能力课型新授课课时本章安排2个课时教学重点重点通过几个典型的趣味算法编程实例，讲解如何通过程序设计解决一些有趣的数学问题，提高通过编程解决实际问题的能力教学难点难点教学难点在于帮助学生清晰理解鞍点、猴子选猴王、汉诺塔问题中复杂的逻辑关系与递归原理，从而构建出高效且准确的算法模型，并能灵活应用于实际场景的问题求解教学过程

1.教学形式讲授课，教学组织采用课堂整体讲授和分组演示

2.教学媒体采用启发式教学、案例教学等教学方法教学手段采用多媒体课件、视频等媒体技术本课标题趣味算法课次

0.5课时安排2授课方式理论课口讨论课口习题课口其他口学分共2分授课对象普通高等院校学生任课教师教材及参考资料

1.《Python程序设计实践教程》

2.本教材配套视频教程及学习检查等资源

3.与本课程相关的其他资源板书设计:教学基本内容教学方法及教学手段课程引入参考以下形式生活中充满了各种需要巧妙解决的问题，这背后往往离不开趣L衔接导入味算法的支持假设你在玩一款策略游戏，战场上的形势瞬息万变，

2.悬念导入若能找到一个特殊位置，既在所在行数值最大，又在所在列数值最

3.情景导入小，就如同占据了关键〃鞍点〃，掌控全局再比如，古老传说里

4.激疑导入一群猴子选猴王，它们围成一圈按特定规则报数，最终剩下的那只

5.演示导入猴子就是猴王，这其实也隐藏着算法逻辑还有神秘的汉诺塔问题，

6.实例导入几根柱子上大小不一的圆盘，要按规则移到指定位置，看似简单，

7.其他形式实则蕴含着递归的智慧接下来，让我们深入探索鞍点、猴子选猴王、汉诺塔这些趣味算法，学会用巧妙思路解决复杂问题，开启算法世界的奇妙之旅实验19趣味算法实例19-1鞍点

1.教学以学生学习教材的基

1.题目描述本内容为主，系统全面地了解如果矩阵/中存在元素4力5,力川h是第/行中最大的元素，又是第/趣味算法列中最小的元素，则称元素4讥月为该矩阵的一个鞍点

2.整个教学过程中，各教学点本题要求编写程序，求一个给定的〃阶矩阵的鞍点可根据实际情况，进行拓展知

2.算法设计识的讲解先将矩阵转化为列表中嵌套列表的形式，代码形式如下for i in rangen:s二input a.append[int nfor nin s.split]求出列表中每一行的最大值，再将这个位置的数字与该列的其他数字进行比较，若其为最小值，则这个值就是鞍点

3.程序代码#sll9-l.pyn=int input a二口count=0count1=0for i in rangen:s二inputa.append[int nfor nin s.split!for jin rangen:if countl二二n andcount=二n:breakfor k in rangen:for klin rangen:if a[j][k]=a[j][kl]:count+=1if count二二n:for jlin rangen:if a[j][k]=a[jl][k]:count1+二1if count1二二n:print〃{}{}〃・format j,k breakcount1二0count=0if count1!=n andcount!=n:print NONE

4.运行结果输入样例如下41741483616120789输出样例如下

215.思考与讨论设计算法时要考虑时间复杂度、空间复杂度，应尽量找到最好的算法下面的方法将行或列中的所有数进行比较，用max函数和min函数求最大值与最小值，请阅读下面的程序n=intinputO;lis=[];lis_l=[];s=0for iin rangen:lis.append listmap int,input.split[:n]for yin rangen:x=lis[y].indexmax1is[y]for jin rangen:lis_l.appendlis[j][x]if j=n-1:if minlis_l=maxlis[y]:print y,x s+=llis1二口if s1:print NONE实例19-2猴子选猴王

1.题目描述一群猴子要选新猴王新猴王的选择方法是〃只候选猴子围成一圈，从某位置起顺序编号为1人〜从1号开始报数，每轮从1报到3,报到3的猴子退出圈子，接着从紧邻的下一只猴子开始报数如此循环，最后剩下的一只猴子就是新猴王请问是原来的几号猴子当选新猴王？要求在一行中输入一个正整数〃〃W1000,在另一行中输出新猴王的编号

2.题目分析该题是典型的约瑟夫问题，解决本题的关键是表示出每次淘汰的猴子的序号，并用循环语句淘汰至只有一只猴子可以先借助特殊例子，即举出一个具体的排成一圈，对每个淘汰的数进行分析中心思想以列表为载体，通过队列模拟报数过程1输入猴子的总数，并创建［1,2,3,…］的列表2建立一个while循环结构，用列表长度模拟剩余的猴子数3模拟猴子选举的规则，通过队列实现这样的规则是简洁且有效的，用[1,2,3]的列表循环模拟一次报数过程报到1或2时、将猴子放到队列的末尾，继续参与报数；报到3时，退出报数4最后剩下的猴子当选新猴王

3.算法设计首先，创建一个列表储存〃个数，并将这〃个数编号，用指针标记每个元素，再用while循环依次将每个要淘汰的数的指针找出，删除这些数当剩下最后一个数时，就可得出新猴王的指针编写程序时,先设置变量index、n、list、iindex是要找的数字的位置，n是猴子的总数，list是列表，i是循环变量；再对变量赋值并设置循环结束条件，在循环中补充关键的控制语句，最后检验是否有误

4.程序代码#sll9-

2.pyn=int inputIs二口for iin rangen:

15.append i+1index=0while lenls1:index二index+2%lenIsIs.pop indexprintIsEO]

5.运行结果1输入样例1262输出样例1173输入样例2114输出样例

276.思考与讨论该问题还有以下解法

①方法一x=eval inputhou=[i for iin range1,x+1]count=0while lenhou!=1:for iin hou[::]:count+=lif count==3:hou.removeicount=0if i==hou[-l]:break for iinhou:printi

②方法二n=int inputmonkey二口timer=0count=0ifn0and n=1000:for iin range1,n+1:monkey,appendi whilelenmonkey1:timer+=l count+=lifcountlenmonkey:count=lif timer=3:timer=0monkey,pop count-1count-=1printmonkey

[0]

③方法三n=int inputsl=listrange1,n+1s2=listcount=0while lensi-lens2=2:for iin si:if inot ins2:count=count+1if count==3:

52.appendi count=O printsumsl-sums2

④方法四n=intinput s=[k forkin range1,n+1]i=lwhile lens1:i+=2i=i-l%lens+l dels[i-l]print s

[0]

7.问题拓展对题目进行修改，将报的数改为变量，输出出局的顺序，应如何修改程序？〃个人围成一圈，从第一个开始报数，第勿个出局，然后下一个人重新报数，如77=

6、ZZF5O初始座位:

1、

2、

3、

4、

5、6o第一轮从左往右数，5出局，序列重置为

1、

2、

3、

4、第二轮从6开始数，4出局，序列重置为6o

1、

2、

3、6第三轮从6开始数，6出局，序列重置为

1、

2、3如此循环直到剩下最后一个，则出局O O的顺序是

5、

4、

6、

2、

3、Io可以用下面的方法编写程序方法一在列表中删除每一轮的出局者，后面元素的索引值会向前缩减方法二给初始列表中的每一个值添加标志位，出局时给其赋值False,只有标志位为True时才进行报数下面是方法二的参考程序nums=int inputcall=int inputpeoples=[True for_in rangenums]result=[]num=1whileany peoples:for index,people inenumerate peoples:if people:if num=call:peoples[index]=Falseresult,append index+1num=1else:num+=1print f，\n总数为{nums},报数为{call}print f约瑟夫序列为\n{result}\n，输入样例如下413运行结果如下总数为41,报数为3约瑟夫序列为[3,6,9,12,15,18,21,24,27,30,33,36,39,1,5,10,14,19,23,28,32,37,41,7,13,20,26,34,40,8,17,29,38,11,25,2,22,4,35,16,31]实例19-3汉诺塔问题

1.题目描述汉诺塔问题是一个经典问题汉诺塔Tower ofHanoi又称为河内塔，源于印度的一个古老传说大梵天创造世界时做了三根金刚石柱子，一根柱子上按照大小顺序摞着64片黄金圆盘大梵天命令婆罗门把圆盘按大小顺序重新摆放在另一根柱子上并且规定任何时候小圆盘上都不能放大圆盘，且一次只能移动一个圆盘，应该如何操作？题目可以描述为有三个圆柱A、B、C,初始时A上有〃个圆盘〃由用户输入，最终移动到圆柱C上请编写代码，输出移动步骤

2.题目分析假设第一个柱子上共有〃个从小到大依次堆放的圆盘，可以把该问题分成以下三步第一步先将第一个柱子上的/7-1个圆盘借助第三个柱子转移到第二个柱子上，并从小到大堆放好第二步将第一个柱子的最后一个圆盘直接移到第三个柱子上第三步将第二个柱子上的/7-1个圆盘借助第一个柱子逐次转移到第三个柱子上

3.算法分析编写两个函数来求解，一个是递归函数hanoi n,a,b,c,其功能是将a上的圆盘借助b移到c上；另一个是普通函数moven,x,y,其功能是将第n个圆盘从x移到y上若将〃个圆盘从A移至C,算法设计可分为以下三步

①把A上的n-l个圆盘借助C移至Bhan ion-l,a,c,b

②把第〃个圆盘从A移至Cmoven,a,co

③把B上的77-1个圆盘借助A移至Chanion-l,b,a,c如果A上只剩下第n个圆盘，则直接将这个圆盘从A移至C即可:move n,a,c,从而结束递归过程先定义计数器count,用于记录运行到了第几步假设第一个柱子上有3个圆盘，递归过程如图19-1所示ABC ABCABMC1I1图19-177=3时的递归过程

4.程序代码#sll9-

3.pycount=0def move n,x,y:print f第｛count｝步｛n｝号盘｛x｝-｛y｝def hanio n,a,b,c:global countif n1:hanion-l,a,c,bcount+=1move n,a,c hanion-1,b,a,celif n二二1:count+=1moven,a,cif_name_二二_main_:print***求解汉诺塔问题***n=intinput请输入圆盘数目print f将｛n｝只圆盘从A移到C的步骤如下’hanion,A,B,C

5.运行结果第圆盘数目第圆盘只从移到的步骤如下:步号步号盘请步号盘将步号盘第步号盘第步号盘第步号第盘第输盘

6.问题拓展运用递归算法求解汉诺塔问题是非常典型的方法，但在运行时会存储运算结果的全部变量，运行结束后才会完全释放，这就表明运用递归算法会占用大量储存空间，对计算机的运行效率有所影响在A、B、C、D四座塔中，求出将所有圆盘从A移动到D所需的最小移动次数1^77^12,参考程序如下d=

[1]*13for iin range2,13:d[i]=1+2*d[iT]d

[0]=0f=[floatinf]*13f

[0]=0f[l]=1foriin range1,13:for jinrange1,i+1:f[i]=minf[i],f[j]*2+d[i-j]foriinrange1,13:printf{i}个盘,移动次数为{f[i]}运行结果如下1个盘，移动次数为12个盘，移动次数为33个盘，移动次数为54个盘，移动次数为95个盘，移动次数为136个盘，移动次数为177个盘，移动次数为258个盘，移动次数为339个盘，移动次数为4110个盘，移动次数为4911个盘，移动次数为6512个盘，移动次数为81实验内容

1.验证四方定理四方定理是数论中的重要定理，它可以叙述为任意一个正整数都可以分解为不超过四个整数的平方和请编写一个程序验证四方定理

1、

3、

5、

7、…

3.数字游戏求解有这样一个算式ABCDX______EDCBAA、B、C、D、E代表的数字各不相同请编写一个程序，计算出A、B、C、D、E各代表什么数字

4.爱因斯坦曾出过这样一道有趣的数学题（爱因斯坦的阶梯问题）有一个长阶梯，若每步上2阶，最后剩1阶；若每步上3阶，最后剩2阶；若每步上5阶，最后剩4阶；若每步上6阶，最后剩5阶；只有每步上7阶，才一阶也不剩请问该阶梯至少有多少阶？请编写一个程序解决该问题

5.国王要赏赐一个大臣30枚金币，但其中有一枚是假币国王提出要求只能用一个天平作为测量工具，并用尽量少的比较次数找出这枚假币，那么余下的29枚金币就赏赐给这个大臣；否则这个大臣将得不到赏赐（已知假币比真币略轻）聪明的大臣思考片刻，很快用天平找出了这枚假币，于是得到了剩下的29枚金币你知道这位大臣是如何找到假币的吗？请编写一个程序模拟找假币的过程，注意用尽量少的比较次数找出这枚假币

6.现有21根火柴，两人轮流取走，每人每次可以取走14根，不〜可多取，也不能不取，谁取最后一根火柴谁输请编写一个程序进行人机对弈，要求人先取，计算机后取

7.17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事15个教徒和15个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难于是他们想了一个办法将30个人围成一个圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环直到仅剩15个人问怎样排列才能使每次投入大海的都是非教徒？章节小结本章在“趣味算法”实验中，我们探究了鞍点、猴子选猴王、汉诺塔问题，收获颇丰通过分析鞍点特性，学会定位矩阵中特殊元素；借助模拟猴子报数过程，掌握循环与条件判断的运用；面对汉诺塔难题，深入理解递归思想，将复杂任务拆解为简单子问题这些算法不仅锻炼了逻辑思维，更让我们领略到算法的简洁高效之美经过实践，我们积累了算法设计经验，提升了解决实际问题的能力，为今后学习更复杂算法筑牢根基，开启了探索算法世界的新征程。