《用递归法解决问题课件》高中信息技术教科课标版算法与程序设计课件39405.pptVIP

* 益阳市第六中学 吴飞 不管有多少层塔，我们都先把它看成两层的塔 A层（1---N-1层）；B层即第N层 问题变简单：A，B，A即Sn=Sn-1+1+Sn-1 递归的核心思想是分解。把一个很复杂的问题使用同一个策略将其分解为较简单的问题，如果这个的问题仍然不能解决则再次分解，直到问题能被直接处理为止。 并不是所有的递归都是可以实现的，或者说有意义的。如果在分解的过程中，问题最终不能分解到一个可以直接解决的问题，则这个过程是没有意义，也就是无限的循环。 第二节课 回顾高僧的处理方法再次提出递归思维。 提出新的问题1“上楼梯问题” 10级楼梯，一步可以上一级也可以上两级，有多少上法？ 1级楼梯 1 1 2级楼梯 1+1，2 2 3级楼梯 1+1+1，1+2，2+1 3 …… 10级楼梯 1+1+1+1+1+1+1+1+1+1，…… 2+2+2+2+2 ？ 给出递归思维的处理方法。 N级楼梯上的方法可分为两类： A、第一步上一级（还剩下N-1级）； B、第一步上两级（还剩下N-2级）。 问题变简单——SN= SN-1 + SN-2 1级楼梯 1 1 2级楼梯 1+1，2 2 3级楼梯 1+1+1，1+2，2+1 3 4级楼梯 2+3=5 5级楼梯 3+5=8 6级楼梯 5+8=13 7级楼梯 8+13=21 8级楼梯 13+21=34 9级楼梯 21+34=55 10级楼梯 34+55=89 提出新的问题2 “互发名信片问题” 圣诞节4位同学（数学试卷中原题是求5位同学）互发名信片，要求：每位同学发出一张名信片且每位同学收到一张名信片，不能自己发给自己。求有多少种发的方法？ 提示： 2位同学 1种 3位同学 2种 4位同学 ？ 5位同学 ？ 6位同学 ？ 学生分析4位同学的情况 给出递归思维的处理方法。 N（N3）位同学的方法可分为两类： A、在N-1位同学的基础上加一位同学（N-1的任一种方法上任取一封信，收信人改为第N人，再第N人的信发到原收信的对像）； B、在N-1位同学中任选一位同学与第N位同学互换名信片。 问题变简单——SN= （N-1 ） × （ SN-1 + SN-2 ） （通过对数学中复杂的排列组合问题的递归思维分析，渐渐打开学生思维窗口，使复杂问题逐步变简单，提升学生分析问题、解决问题的能力。） *