11088 整数区分问题ITeye - 威尼斯人

11088 整数区分问题ITeye

2019-01-13 06:32:33 | 作者: 笑柳 | 标签: 区分,问题,整数 | 浏览: 507

时刻约束:1000MS  内存约束:65535K
提交次数:0 经过次数:0

题型: 编程题   言语: C++;C;VC;JAVA

Description
下面有整数区分问题扩展出的多个题例:
(1)正整数n区分为若干正整数之和,最大加数不超越m的区分数
(2)正整数n区分为不超越m个正整数之和的区分数
(3)正整数n区分为若干正奇整数之和的区分数
(4)正整数n区分为互不相同正整数之和的区分数
整数区分无次序,比如对7区分,以为2 2 3和3 2 2和2 3 2为同一种区分。



两个数n和m,中心空格相连。n和m都不超越100。
如输入7 3
则:最大加数不超越3的区分为:(3 3 1)(3 2 2)(3 2 1 1)(3 1 1 1 1)(2 2 2 1)(2 2 1 1 1)(2 1 1 1 1 1)(1 1 1 1 1 1 1),共8种。
不超越3个正整数的区分为:(7)(6 1)(5 2)(5 1 1)(4 3)(4 2 1)(3 3 1)(3 2 2),共8种。
若干正奇数的区分为:(7)(5 1 1)(3 3 1)(3 1 1 1 1)(1 1 1 1 1 1 1),共5种。
互不相同正整数的区分为:(7)(6 1)(5 2)(4 3)(4 2 1),共5种。


四个数,中心空格相连,分别为上面四个题例的成果。其间m参数只和题例(1)和(2)有关,与(3)(4)无关。


输入样例
7 3


输出样例
8 8 5 5


提示

 

整数区分问题是算法中的一个经典出题之一,有关这个问题的叙述在解说到递归时根本都将触及。所谓整数区分,是指把一个正整数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},{2,1,1},{1,1,1,1};

       留意4=1+3 和 4=3+1被以为是同一个区分。

       该问题是求出n的一切区分个数,即f(n, n)。下面咱们考虑求f(n,m)的办法;

 

        ---------------------------------------------------------------------

                                           (一)

        ---------------------------------------------------------------------

       依据n和m的联系,考虑以下几种状况: 

       (1)当 n = 1 时,不管m的值为多少(m 0 ),只要一种区分即 { 1 };

        (2)  当 m = 1 时,不管n的值为多少,只要一种区分即 n 个 1,{ 1, 1, 1, ..., 1 };

        (3)  当 n = m 时,依据区分中是否包括 n,能够分为两种状况:

              (a). 区分中包括n的状况,只要一个即 { n };

              (b). 区分中不包括n的状况,这时区分中最大的数字也必定比 n 小,即 n 的一切 ( n - 1 ) 区分。

              因而 f(n, n) = 1 + f(n, n-1);

        (4) 当 n m 时,由于区分中不或许呈现负数,因而就相当于 f(n, n);

        (5) 但 n m 时,依据区分中是否包括最大值 m,能够分为两种状况:

               (a). 区分中包括 m 的状况,即 { m, { x1, x2, ..., xi } }, 其间 { x1, x2, ..., xi } 的和为 n - m,或许再次呈现 m,因而是(n - m)的 m 区分,因而这种区分

                     个数为 f(n-m, m);

               (b). 区分中不包括 m 的状况,则区分中一切值都比 m 小,即 n 的 ( m - 1 ) 区分,个数为 f(n, m - 1);

              因而 f(n, m) = f(n - m, m) + f(n, m - 1);

 

         归纳以上状况,咱们能够看出,上面的定论具有递归界说特征,其间(1)和(2)归于回归条件,(3)和(4)归于特殊状况,将会转换为状况(5)。而状况(5)为通用状况,归于递推的办法,其本质主要是经过减小m以到达回归条件,然后解决问题。其递推表达式如下:

         f(n, m) =      1;                                        ( n = 1 or m = 1 )

                            f(n, n);                                 ( n m )

                            1+ f(n, m - 1);                      ( n = m )

                            f(n - m, m) + f(n, m - 1);       ( n m )

        ---------------------------------------------------------------------

                                           (二)

        ---------------------------------------------------------------------

思维: 转化为子集和问题: 调集{1,2,…,n},选择若干正整数,使之和为n,这也是一个背包装物品问题。 设F(I,J): 表明选择调集前I个,使之和为J的方法数。 递推联系: F(I,J) = F(I-1,J) + F(I-1,J-I), 第I个不挑的方法数 + 挑第I个的方法数 递推鸿沟: F(1,1)=1, F(1,k)=0(k 1), F(I,k)=0(k 0), F(I,0)=1(I 0) #include iostream using namespace std; int m,n; int f1(int n,int m)     if(n 1||m 1) //不为负数         return 0;     if(m==1||n==1)  //1的m区分 或 n的1区分 都是 1         return 1;     if(n==m)  // 含n是 1 不含的是 n 的 n-1 区分         return 1+f1(n,n-1);     if(n m)  // 最大也是n 即 n 的 n 区分         return f1(n,n);     // 含 m 的是 n-m 的 m 区分 由于 n-m中或许再次呈现m     // 不含 m 的是 n 的 m-1 区分         return f1(n-m,m)+f1(n,m-1); int f2(int n,int m)     if(m==0) //F(I,0)=1(I 0)         return 1;     if(m 0) //F(I,k)=0(k 0)         return 0;     if(n==1 m==1) //F(1,1)=1         return 1;     if(n==1 m 1)  //F(1,k)=0(k 1)         return 0; //设F(I,J): 表明选择调集前I个,使之和为J的方法数。 // F(I,J) = F(I-1,J) + F(I-1,J-I), 第I个不挑的方法数 + 挑第I个的方法数     return f2(n-1,m)+f2(n-1,m-n); int main()     cin n m;     cout f1(n,m) " " f1(n,m) " ";     cout f2(n,n) " " f2(n,n) endl; //m参数与(3)(4)无关     return 0;

 #include iostream

 

using namespace std;

int m,n;

int f1(int n,int m)

{

    if(n 1||m 1) //不为负数

        return 0;

    if(m==1||n==1)  //1的m区分 或 n的1区分 都是 1

        return 1;

    if(n==m)  // 含n是 1 不含的是 n 的 n-1 区分

        return 1+f1(n,n-1);

    if(n m)  // 最大也是n 即 n 的 n 区分

        return f1(n,n);

    // 含 m 的是 n-m 的 m 区分 由于 n-m中或许再次呈现m

    // 不含 m 的是 n 的 m-1 区分

        return f1(n-m,m)+f1(n,m-1);

}

 

int f2(int n,int m)

{

    if(m==0) //F(I,0)=1(I 0)

        return 1;

    if(m 0) //F(I,k)=0(k 0)

        return 0;

    if(n==1 m==1) //F(1,1)=1

        return 1;

    if(n==1 m 1)  //F(1,k)=0(k 1)

        return 0;

 

//设F(I,J): 表明选择调集前I个,使之和为J的方法数。

// F(I,J) = F(I-1,J) + F(I-1,J-I), 第I个不挑的方法数 + 挑第I个的方法数

    return f2(n-1,m)+f2(n-1,m-n);

}

int main()

{

    cin n m;

 

    cout f1(n,m) " " f1(n,m) " ";

    cout f2(n,n) " " f2(n,n) endl; //m参数与(3)(4)无关

    return 0;

}

 

版权声明
本文来源于网络,版权归原作者所有,其内容与观点不代表威尼斯人立场。转载文章仅为传播更有价值的信息,如采编人员采编有误或者版权原因,请与我们联系,我们核实后立即修改或删除。

猜您喜欢的文章

阅读排行

  • 1

    MongoDB与Java(2)ITeye

    办法,咱们,代码
  • 2
  • 3

    Java多线程编程ITeye

    线程,音讯,出产
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

    FileDowloadITeye

    途径,获取,绝对