上一节动脑:NOIP爬台阶问题求解【上】我们学会了如何使用递归来解决这个问题,现在我们来进一步优化(简单的说就是让计算机使用更短的时间与最小的计算量来完成),如果上一节的递归程序实现部分你没理解,没关系,并不影响本节的学习。这个题目有一定难度建议12岁以上的孩子学习,如果条件允许的话,希望家长能够先理解然后给予孩子以指导和帮助。

  题目:有一座高度是10级台阶的楼梯,从下往上走,每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。

用SCRATCH做NIOP题--爬台阶问题优化求解【下】

用SCRATCH做NIOP题--爬台阶问题优化求解【下】

  观察上图,颜色相同的都是被重复计算的。

用SCRATCH做NIOP题--爬台阶问题优化求解【下】

用SCRATCH做NIOP题--爬台阶问题优化求解【下】

用SCRATCH做NIOP题--爬台阶问题优化求解【下】用SCRATCH做NIOP题--爬台阶问题优化求解【下】用SCRATCH做NIOP题--爬台阶问题优化求解【下】用SCRATCH做NIOP题--爬台阶问题优化求解【下】用SCRATCH做NIOP题--爬台阶问题优化求解【下】用SCRATCH做NIOP题--爬台阶问题优化求解【下】用SCRATCH做NIOP题--爬台阶问题优化求解【下】用SCRATCH做NIOP题--爬台阶问题优化求解【下】用SCRATCH做NIOP题--爬台阶问题优化求解【下】用SCRATCH做NIOP题--爬台阶问题优化求解【下】用SCRATCH做NIOP题--爬台阶问题优化求解【下】用SCRATCH做NIOP题--爬台阶问题优化求解【下】用SCRATCH做NIOP题--爬台阶问题优化求解【下】用SCRATCH做NIOP题--爬台阶问题优化求解【下】用SCRATCH做NIOP题--爬台阶问题优化求解【下】

  分两种情况,台阶数小于3,如果是1级,那么只有一种走法,如果是2级那么有2种走法,当大于2级,就用到我们上面总结的规律重复的往后推算。第n级F(n)=F(n-1)+F(n-2)

用SCRATCH做NIOP题--爬台阶问题优化求解【下】

  这个代码看起来是不是比递归容易理解多了,而且还提高了效率呢。

用SCRATCH做NIOP题--爬台阶问题优化求解【下】

  如果你坚持看到这里,并且理解了这个解题的思路(对scratch程序没理解,没关系,这不是重点),那么恭喜你,你在不知不觉中学到了一个高大上的新技能——动态规划。

用SCRATCH做NIOP题--爬台阶问题优化求解【下】用SCRATCH做NIOP题--爬台阶问题优化求解【下】用SCRATCH做NIOP题--爬台阶问题优化求解【下】用SCRATCH做NIOP题--爬台阶问题优化求解【下】

  怎么样?看完有没有收获呢?

   少儿编程网scratch中文素材在线生成