新疆克拉玛依市第九中学 8344003
摘要：课标要求针对简单问题，尝试设计求解算法，并通过程序进行验证。本课中的例题，两个思考都是先用递归的方法找到算法，在现成的程序中进行修改。本文以解密汉诺塔实践， 探究了本课中最后一个拓展练习。
关键词：递归算法；通式；拓展练习
一说起递归，每个人都不陌生。从小就听过的例子：很久以前，有一则古老而有趣的故事，流传至今：从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事，讲什么呢？
从前有座山，山里有座庙，……
那么什么是递归呢？
递归是把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定的程度直到可以直接得出它的解，从而得到原来问题的解。
注意：必须要有一个结束递归的条件，不得无限递归。
遇到递归问题需要分析：
1.问题的边界条件及边界值。
2.解决问题的通式。
下面我们通过具体问题来体验一下递归算法吧
例题：
使用递归算法来计算阶乘
定义函数f(n)=n
，假设n=5，我们来算5
n=5时，f(5)=5*f(5-4)；那么f(n)=n*f(n-1)
所以：计算n的阶乘的递归算法程序实现：
①当n=1时 f(1)=1
②当n>1时 f(n)=n*f(n-1)
用python编写代码：
思考活动1：
“斐波那契数列”，1，1，2，3，5，8，13…… ，
想一想：
1、如果用递归算法打印出“斐波那契数列”中第20个数，写出解决此问题的通式
2、“斐波那契数列”有n个数，则n的取值范围？
3、尝试将图1中的代码进行修改，打印出“斐波那契数列”中第20个数
思考活动2：
假设一只猴子每次可跳1级或者3级台阶，求上到的30级台阶有多少种不同的爬法？
想一想：
1、猴子跳1级台阶有几种方法？2级、3级……10级？从中找出解决问题的通式
2、如果有n级台阶，则n的取值范围？
尝试将图1中的代码进行修改，算出猴子上到的30级台阶时有多少种不同的爬法？
拓展：汉诺塔
如何将将a针中n个的金片最终全部移动到c针,要求一次只移动一片,不管在哪根针上,小片必须在大片上面。
当金片的数量n>2时
第一步：通过c针中转，把a上的1~n-1号金片移到b上
第二步：将a针上的n号金片移到c针上
第三步：通过a针中转，将b针上1~n-1号金片移到c针上
n个金片 a→c,用python写程序
def hnt(n,a,b,c):
if n==1:
print(a,'移到',c)
else:
hnt(n-1,a,c,b)
print(a,'移到',c)
hnt(n-1,b,a,c)
n=int(input('请输入汉诺塔的层数'))
hnt(n,'x','y','z')
拓展思考：
梵天说如果把64个金片从a挪到c那么这个世界就毁灭了，那么到底需要多少次才能把64个金片才能把这些金片从a挪到c呢，计算一下一共需要多少步骤？
客服QQ：30444492琼网文【2021】1550-113号
增值电信业务经营许可证：琼B2-20210322
出版物经营许可证：新出发龙华出字第(2021)009号
广播电视节目制作经营许可证：(琼)字第00779号
版权所有 ©2002-2024 期刊网(www.qikanchina.com) 琼ICP备2021005105号
