首页 > 其他 > 详细

整数的拆分

时间:2017-03-10 12:30:01      阅读:226      评论:0      收藏:0      [点我收藏+]

引自:http://www.cnblogs.com/DwyaneTalk/p/4617057.html

华师大oj 1009

问题描述:

  将正整数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<=10)。

输出:

  输出每组测试数据有多少种分法。

分析:

  对于整数划分,相当于把正整数n写成下面形式:

    n=n1+n2+…+nk (其中n≥n1≥n2≥…≥nk≥1,k≥1),则{n1, n2, ……,nk}为n的一个划分。

  现假设n1 <= m,即:{n1, n2, ……,nk}中最大的数不超过m,则称{n1, n2, ……,nk}是n的一个m上限划分。记n的m上限划分为f(n,m)。因此,此题的解便是f(n,n)。对于f(n,m),分析可得下面的递推关系式:

  1、当n = 1时,f(n,m)=1。即1只有{1}这一种划分。

  2、当m = 1时,f(n,m)=1。即此时只有{1, 1,……,1}(共n个1)这一种划分。

  3、当m = n时,f(n,m) = f(n,n) = f(n, n-1) + 1。其中"+1"对应的就是{n}这种划分,其他的划分中,必定所有数都小于n。

  4、当m > n时, f(n,m) = f(n,n),因为n的划分中不可能存在大于n的数。

  5、当m < n时, f(n,m) = f(n-m, m) + f(n, m-1)。其中f(n-m,m)表示包含m的划分,f(n,m-1)表示不包含m的划分。

代码:

  根据上面的递推式,同样可以写出递归和递推的代码。

  递归代码仍然存在重复计算,时间代价大。

  递推代码就是计算f(1,1)到f(n,n)的过程,所以时间和空间复杂度都是O(n^2),而且由于f(n,m)是和f(n-m,m)、f(n,m-1),所以不太适合进行空间复杂度的优化。

 

 1 #include <stdio.h>
 2 #include <string.h>
 3 int fun(int n, int m)
 4 {
 5     if(n == 1 || m == 1) return 1;
 6     else if(n < m) return fun(n, n);
 7     else if(n == m) return (1 + fun(n, m - 1));
 8     else return (fun(n, m - 1) + fun(n - m, m));
 9 }
10 int main(){
11   int n;
12     while(~scanf("%d", &n))
13     {
14         printf("%d\n", fun(n, n));
15     }
16   return 0;
17 }//超时

 

//超时改进,在计算的过程中记录一些已经算过的值,避免重复的计算

#include <stdio.h>
#include <string.h>
int dp[105][105];//把计算过的fun(n,m)存下来
bool flag[105][105];
int fun(int n, int m)
{   if(flag[n][m]==1) return dp[n][m];
    if(n == 1 || m == 1) return 1;
    else if(n < m) {
        int tmp=fun(n,n);
        dp[n][n]=tmp;
        flag[n][n]=1;
        return tmp;
    }
    else if(n == m) {
        int tmp=1 + fun(n, m - 1);
        dp[n][m]=tmp;
        flag[n][m]=1;
        return tmp;
    }
    else{
        int tmp1=fun(n,m-1);
        int tmp2=fun(n-m,m);
        int tmp=tmp1+tmp2;
        dp[n][m-1]=tmp1;
        flag[n][m-1]=1;
        dp[n-m][m]=tmp2;
        flag[n-m][m]=1;
        dp[n][m]=tmp;
        flag[n][m]=1;
        return tmp;
    }
}
int main(){
  int n;
  int i,j;
  for(i=1;i<=100;i++){
      for(j=1;j<=100;j++){
          flag[i][j]=0;
          if(i==1) {
              dp[i][j]=1;
              flag[i][j]=1;
          }
          else if(j==1) {
              dp[i][j]=1;
              flag[i][j]=1;
          }
      }
  }
  for(i=1;i<=100;i++){
      dp[i][i]=fun(i,i);
      flag[i][i]=1;
  }

    while(scanf("%d", &n)!=EOF)
    {
        printf("%d\n", fun(n,n));
    }
  return 0;
}

 

整数的拆分

原文:http://www.cnblogs.com/yexinyu/p/6529763.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!