2020-06-23 12:12
辽宁工程技术大学 Java BiscuitBoy:作者的解释有点苍白。 递归的核心是递进和回归,递进就是要逐渐减小问题规模,回归要保证有出口(或称base case)。如何减小问题规模呢?m个苹果放进n个盘子,求不同放法的种数,可以分为两类情况:1.让每个盘子都有苹果放着。2.至少有一个盘子空着。有且仅有这两种情况,两种情况没有交集。7个苹果放进3个盘子,共有8种不同放法,可以用此实例加深以上理解。现在,用f(m,n)表示将m个苹果放进n个盘子不同放法的种数。第一种情况相当于给每个盘子先发1个苹果,再将m-n个苹果放进n个盘子里,不同放法种数为f(m-n,n)。第二种情况相当于摒弃掉空着的那个盘子,将m个苹果放进n-1个盘子里,不同放法种数为f(m,n-1)。因此,f(m,n) = f(m-n,n)+f(m,n-1)。至此,问题规模已经减小了,再结合递归出口,就可以完成求解了。
0 点赞 评论 收藏
分享
2020-05-30 23:05
辽宁工程技术大学 Java 0 点赞 评论 收藏
分享
关注他的用户也关注了: