`
fehly
  • 浏览: 248699 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

整数划分问题

阅读更多

       将正整数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=n1+n2+…+nk,其中n1≥n2≥…≥nk≥1,k≥1。

    ### 整数划分问题概述 整数划分问题是一种经典的组合数学问题,主要研究如何将一个正整数表示为若干个正整数之和的方式。在本问题中,我们需要找到一个正整数\( n \)的所有可能的划分方式,并计算出这些划分的数量...

    整数划分问题、具体算法实现

    整数划分问题是一个经典的计算机科学问题,主要涉及组合优化和图论领域。在数学上,它指的是给定一个正整数n,寻找所有可能的方法将其分成若干个正整数的和,每个正整数称为一个部分。每个不同的部分组合构成一个...

    hutc-整数划分问题 参考代码

    ### hutc-整数划分问题 参考代码 #### 整数划分问题概述 整数划分问题是一个经典的组合数学问题,其目标是将一个正整数拆分成若干个正整数之和的不同方式的数量。例如,整数4可以被划分为5种不同的方式:4、3+1、2...

    整数划分问题 回溯法 深度优先遍历

    整数的分划问题 将正整数n表示成一系列正整数之和,n=n1+n2+...+nk,其中n1&gt;n2&gt;...&gt;nk,k&gt;=1。正整数n的不同划分个数称为n的划分数

    整数划分问题(回溯法).mp4

    最近我写了一篇csdn文章:【算法设计与分析】——整数划分问题(回溯法),并且画了一个流程图,为了让大家更加清楚的理解我讲的内容,所以我给大家录了一个讲解视频,希望大家一起进步哦~

    整数划分问题java源码

    整数划分问题是一个经典的计算机科学中的算法问题,它在数学和计算机科学的多个领域都有应用。在这个Java源码中,我们可以看到如何解决这个问题。中国科学技术大学软件学院的《算法设计与分析》课程通过这个实验,...

    java算法分析与设计之整数划分问题源代码

    java算法分析与设计之整数划分问题源代码 算法作为计算机专业学生的必修课,同时也是软件开发过程中必备的编程思想,对学习研究计算机专业意义重大;正因为这门课程难,所以除了相关方面的书籍,网络资源少的可怜,...

    整数划分,并输出结果

    ### 整数划分算法解析与实现 ...该程序实现了对任意正整数`n`的所有可能的划分组合的计算和输出,通过递归的方式解决了整数划分问题。在实际应用中,整数划分问题有广泛的应用场景,如密码学、组合优化等领域。

    整数划分问题参考代码

    ### 整数划分问题解析与实现 #### 一、问题定义 整数划分问题是指将一个正整数\( n \)表示为若干个正整数之和的方式的计数问题,其中这些正整数需要满足一定的顺序关系。具体地,对于正整数\( n \),我们寻找所有...

    整数划分代码实现

    当N大于1时,我们可以选择是否包含某个数字i(1≤i≤N),然后递归地处理剩余的整数划分问题。以下是一个简单的递归实现: ```c #include void integerPartition(int n, int current) { if (n == 0) { printf(...

    中科大算法导论课程实验 整数划分 代码

    **整数划分问题** 整数划分是组合优化领域的一个经典问题,源于数学和计算机科学。在整数划分问题中,我们需要找到一个非负整数序列(可以为空),使得这些整数之和等于给定的正整数S,且序列中的每个元素都不相同...

    C语言之整数划分问题(递归法)实例代码

    整数划分问题是一个经典的计算机科学问题,特别是在算法和递归法的应用中经常被提及。问题的核心是找到将一个正整数n分解为若干个正整数之和的所有可能方式,而这些正整数的和必须等于n本身。整数划分问题可以采用...

    整数划分方法2及代码(有注释)

    整数划分问题的基本思想是找到所有可能的方式,将一个整数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的基本步骤: 1. **基本情况**:当总和为0时,表示...

Global site tag (gtag.js) - Google Analytics