首页 > 代码库 > 递归---NYOJ-90整数划分(一)
递归---NYOJ-90整数划分(一)
这个题理解了好大会才理解,看了网上的代码,不太理解,但是后来看了好几个人的, 大同小异吧,慢慢的就理解了。
思路:
递归函数的意思是, 将 n 划分为最大数为 m 的划分数, 可以分几种情况
1. 当n = 1 的时候, 这时候就是将1划分, 也就是递归的出口, 1 肯定只能划分为 1, 所以返回1
2. 当m = 1的时候, 最大的数为1, 所以只能全划分为1才行, 所以就一种,return 1;
3. 当n < m的时候, 一个数肯定不能划分为比他要大的数, 最大只能划分到它本身,所以只需要将m变成n就行了,所以func(n, n);
4.当 n > m的时候, 它的划分数为func(n, m - 1) + func(n - m, m); 这个可以这么理解,就比如6可以划分到4和2, 这时n = 6, m = 4, 它的划分数又等于6划分到3的,然后再加上本身2的划分数, 所以它的式子就可以写成上式就是func(6, 4) + func(2, 4), 当递归到func(2, 4)的时候, 也就是2的划分有多少个,由于n < m的时候加了m = n; 所以执行func(2, 2);
5. 当n = m的时候, 它的划分数就是它的上一个的划分数加上1,
大体思路就是这样,不理解的话可以尝试着代入数据试试,理解理解大体概念,下面是代码的实现:
1 #include <stdio.h> 2 3 4 int func(int n, int m)//func(n, m) 是将 n 划分为最大数不超过m的划分 5 { 6 if(n == 1 || m == 1) 7 return 1; 8 if(n < m)//因为不可能将n划分成比n还大的数,所以,直接m = n就行了 9 return func(n, n);10 else if(n > m)/*当将n划分为比它小的数时,11 一个是继续往下再找一个,还有一个就是剩下的那个*/12 return func(n, m - 1) + func(n - m, m);13 else if(n == m)//n = m的时候, 也就是它的上一个的划分加上1 14 return 1 + func(n, m - 1);15 }16 int main()17 {18 int m;19 scanf("%d", &m);20 for(int i = 0; i < m; i++)21 {22 int n;23 scanf("%d", &n);24 printf("%d\n", func(n, n));25 }26 return 0;27 }
递归---NYOJ-90整数划分(一)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。