将正整数n表示成一系列正整数之和,n=n∨1+n∨2+...+n∨k,其中n∨1>=n∨2>=...>=n∨k>=1,k>=1.
正整数n的这种表示称为正整数n的划分。正整数n的不同的划分个数称为正整数n的划分数,作为p(n)。
例如,正整数6有如下11种不同的划分,所有p(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.
在正整数n的所有不同的划分中,将最大加数n∨1不大于m的划分个数记作q(n,m).可以建立q(n,m)的如下递归关系。
(1)q(n,1)=1,n>=1.
当最大加数n∨1不大于1时,任何正整数n只有一种划分形式,即n=1+1+...+1。
(2)q(n,m)=q(n,n),m>=n
最大加数n∨1实际上不能大于n.因此,q(1,m)=1.
(3)q(n,n)=1+q(n,n-1).
正整数n的划分由n∨1=n的划分和n∨1<=n-1的划分组成。
(4)q(n,m)=q(n,m-1)+q(n-m,m),n>m>1.
正整数n的最大加数n∨1不大于m的划分由n∨1=m的划分和n∨1<=m-1的划分组成。
以上的关系实际上给出了计算q(n,m)的递归方式如下:
1 n=1,m=1
q(n,m)= q(n,n) n<m
1+q(n,n-1) n=m
q(n,m-1)+q(n-m,m) n>m>1
据此,可设计计算q(n,m)的递归算法如下。其中,正整数n的划分数p(n)=q(n,n)。
public class Integer_hua_fen
{
public static int q(int n,int m)
{
if((n<1)||(m<1)) return 0;
if((n==1)||(m==1)) return 1;
if(n<m) return q(n,n);
if(n==m) return q(n,m-1)+1;
return q(n,m-1)+q(n-m,m);
}
public static void main(String[] args)
{
System.out.println("6的划分为"+q(6,6));
}
}
打印输出11
分享到:
相关推荐
整数划分问题的实现代码 整数划分问题是将一个正整数 n 拆成一组数连加并等于 n 的形式,且这组数中的最大加数不大于 n。这是一种经典的组合数学问题,具有重要的理论价值和实践应用价值。 在解决整数划分问题时,...
### 整数划分问题概述 整数划分问题是一种经典的组合数学问题,主要研究如何将一个正整数表示为若干个正整数之和的方式。在本问题中,我们需要找到一个正整数\( n \)的所有可能的划分方式,并计算出这些划分的数量...
整数划分问题是一个经典的计算机科学问题,主要涉及组合优化和图论领域。在数学上,它指的是给定一个正整数n,寻找所有可能的方法将其分成若干个正整数的和,每个正整数称为一个部分。每个不同的部分组合构成一个...
### hutc-整数划分问题 参考代码 #### 整数划分问题概述 整数划分问题是一个经典的组合数学问题,其目标是将一个正整数拆分成若干个正整数之和的不同方式的数量。例如,整数4可以被划分为5种不同的方式:4、3+1、2...
整数的分划问题 将正整数n表示成一系列正整数之和,n=n1+n2+...+nk,其中n1>n2>...>nk,k>=1。正整数n的不同划分个数称为n的划分数
最近我写了一篇csdn文章:【算法设计与分析】——整数划分问题(回溯法),并且画了一个流程图,为了让大家更加清楚的理解我讲的内容,所以我给大家录了一个讲解视频,希望大家一起进步哦~
整数划分问题是一个经典的计算机科学中的算法问题,它在数学和计算机科学的多个领域都有应用。在这个Java源码中,我们可以看到如何解决这个问题。中国科学技术大学软件学院的《算法设计与分析》课程通过这个实验,...
java算法分析与设计之整数划分问题源代码 算法作为计算机专业学生的必修课,同时也是软件开发过程中必备的编程思想,对学习研究计算机专业意义重大;正因为这门课程难,所以除了相关方面的书籍,网络资源少的可怜,...
### 整数划分算法解析与实现 ...该程序实现了对任意正整数`n`的所有可能的划分组合的计算和输出,通过递归的方式解决了整数划分问题。在实际应用中,整数划分问题有广泛的应用场景,如密码学、组合优化等领域。
### 整数划分问题解析与实现 #### 一、问题定义 整数划分问题是指将一个正整数\( n \)表示为若干个正整数之和的方式的计数问题,其中这些正整数需要满足一定的顺序关系。具体地,对于正整数\( n \),我们寻找所有...
当N大于1时,我们可以选择是否包含某个数字i(1≤i≤N),然后递归地处理剩余的整数划分问题。以下是一个简单的递归实现: ```c #include void integerPartition(int n, int current) { if (n == 0) { printf(...
**整数划分问题** 整数划分是组合优化领域的一个经典问题,源于数学和计算机科学。在整数划分问题中,我们需要找到一个非负整数序列(可以为空),使得这些整数之和等于给定的正整数S,且序列中的每个元素都不相同...
整数划分问题是一个经典的计算机科学问题,特别是在算法和递归法的应用中经常被提及。问题的核心是找到将一个正整数n分解为若干个正整数之和的所有可能方式,而这些正整数的和必须等于n本身。整数划分问题可以采用...
整数划分问题的基本思想是找到所有可能的方式,将一个整数N分解为一个或多个正整数的和。例如,对于N=5,可能的划分有:5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1。每一种方式都代表了一种不同的组合。 整数...
在整数划分问题中,递归通常从最大的正整数开始,然后尝试减少这个数并增加下一个较小的数,以保持总和不变,直到所有可能的划分都被考虑。 以下是整数划分方法1的基本步骤: 1. **基本情况**:当总和为0时,表示...