递归---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 } 
时间: 10-28

递归---NYOJ-90整数划分(一)的相关文章

NYOJ 90 —— 求n划分为若干个正整数的划分个数

整数划分 时间限制:3000 ms  |  内存限制:65535 KB 描述 将正整数n表示成一系列正整数之和:n=n1+n2+…+nk, 其中n1≥n2≥…≥nk≥1,k≥1. 正整数n的这种表示称为正整数n的划分.求正整数n的不 同划分个数. 例如正整数6有如下11种不同的划分: 6: 5+1: 4+2,4+1+1: 3+3,3+2+1,3+1+1+1: 2+2+2,2+2+1+1,2+1+1+1+1: 1+1+1+1+1+1.  输入 第一行是测试数据的数目M(1<=M<=10).以下每

整数划分递归模板

/* 整数划分问题是算法中的一个经典命题之一,有关这个问题的讲述在讲解到递归时基本都将涉及. 所谓整数划分,是指把一个正整数n写成如下形式: n=m1+m2+...+mi; (其中mi为正整数,并且1 <= mi <= n),则{m1,m2,...,mi}为n的一个划分. 如果{m1,m2,...,mi}中的最大值不超过m,即max(m1,m2,...,mi)<=m,则称它属于n的一个m划分.这里我们记n的m划分的个数为f(n,m); 例如但n=4时,他有5个划分,{4},{3,1},{

NYOJ 整数划分(三)

整数划分(三) 时间限制:1000 ms  |  内存限制:65535 KB 难度:5 描述 整数划分是一个经典的问题.请写一个程序,完成以下要求. 输入 每组输入是两个整数n和k.(1 <= n <= 50, 1 <= k <= n) 输出 对于输入的 n,k; 第一行: 将n划分成若干正整数之和的划分数. 第二行: 将n划分成k个正整数之和的划分数. 第三行: 将n划分成最大数不超过k的划分数. 第四行: 将n划分成若干个 奇正整数之和的划分数. 第五行: 将n划分成若干不同整

整数划分类型题目

整数划分 --- 一个老生长谈的问题: 1) 练练组合数学能力. 2) 练练递归思想 3) 练练DP 总之是一道经典的不能再经典的题目: 这道好题求: 1. 将n划分成若干正整数之和的划分数. 2. 将n划分成k个正整数之和的划分数. 3. 将n划分成最大数不超过k的划分数. 4. 将n划分成若干奇正整数之和的划分数. 5. 将n划分成若干不同整数之和的划分数. 1.将n划分成不大于m的划分法:  1).若是划分多个整数可以存在相同的:  dp[n][m]= dp[n][m-1]+ dp[n-m

NYOJ-571 整数划分(三)

此题是个非常经典的题目,这个题目包含了整数划分(一)和整数划分(二)的所有情形,而且还增加了其它的情形,主要是用递归或者说是递推式来解,只要找到了递推式剩下的任务就是找边界条件了,我觉得边界也是非常重要的一步,如果找不准边界,这个题也很难做出来,当时我就是找边界找了好长时间,边界得琢磨琢磨.递推步骤如下: 第一行:将n划分成若干正整数之和的划分数.状态转移方程:dp[i][j]:和为i.最大数不超过j的拆分数dp[i][j]可以分为两种情况:1.拆分项至少有一个j 2.拆分项一个j也没有dp[i

算法笔记——整数划分3

题目来源:POJ1664-放苹果 和POJ3014 问题描述: 把m个同样的苹果放在n个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法. 输入: 第一行是测试数据的数目t(0 <= t <= 20).以下每行均包含二个整数m和n,以空格分开.1<=m,n<=10. 输出: 对输入的每组数据m和n,用一行输出相应的K. 分析: 问题描述转换成整数划分形式:把一个正整数m分成至多n个正整数的和,有多少种分法? 假设用f(m,

hdu 1028 Ignatius and the Princess III 【整数划分】

Ignatius and the Princess III                                                                                       Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 15730    Accepted Submission(

算法笔记——整数划分2

题目来源:NYOJ176 问题描述: 把一个正整数m分成n个正整数的和,有多少种分法? 例:把5分成3个正正数的和,有两种分法: 1 1 3 1 2 2 输入: 第一行是一个整数T表示共有T组测试数据(T<=50) 每组测试数据都是两个正整数m,n,其中(1<=n<=m<=100),分别表示要拆分的正数和拆分的正整数的个数. 输出: 输出每组拆分的方法的数目. 分析: 题目可以换种等价描述:把m个同样的苹果放在n个同样的盘子里,不允许有的盘子空着不放,问共有多少种不同的分法,其中n

算法笔记——整数划分1

题目来源:NYOJ90 问题描述: 将正整数n表示成一系列正整数之和:n=n1+n2+…+nk, 其中n1≥n2≥…≥nk≥1,k≥1. 正整数n的这种表示称为正整数n的划分.求正整数n的不 同划分个数.  例如正整数6有如下11种不同的划分:  6:  5+1:  4+2,4+1+1:  3+3,3+2+1,3+1+1+1:  2+2+2,2+2+1+1,2+1+1+1+1:  1+1+1+1+1+1. 输入: 第一行是测试数据的数目M(1<=M<=10).以下每行均包含一个整数n(1<

整数划分

整数划分问题是算法中的一个经典命题之一,有关这个问题的讲述在讲解到递归时基本都将涉及.所谓整数划分,是指把一个正整数n写成如下形式: n=m1+m2+...+mi; (其中mi为正整数,并且1 <= mi <= n),则{m1,m2,...,mi}为n的一个划分. 如果{m1,m2,...,mi}中的最大值不超过m,即max(m1,m2,...,mi)<=m,则称它属于n的一个m划分.这里我们记n的m划分的个数为f(n,m); 例如但n=4时,他有5个划分,{4},{3,1},{2,2}