| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4808 人关注过本帖, 1 人收藏
标题:整数的划分问题
只看楼主 加入收藏
kmj_IT
Rank: 2
等 级:论坛游民
帖 子:17
专家分:10
注 册:2012-3-17
结帖率:33.33%
收藏(1)
已结贴  问题点数:10 回复次数:5 
整数的划分问题

整数的划分问题。
如,对于正整数n=6,可以分划为:
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+1
现在的问题是,对于给定的正整数n,编写算法打印所有划分。
用户从键盘输入 n (范围1~10)
程序输出该整数的所有划分。

请帮忙分析一下下面的函数,不是很懂

void divide(char *s,int first,int other)  
//该函数输出所有的划分的式子
{  
    int i;   
    static char t[50];//保存上一次的输出结果  
    char temp[50],str[3]={0};  
   if(other==0){  
         if(s[0]==t[0])  
            printf(",%s",s);  
        else  
             printf("%s",s);   
         strcpy(t,s);  
   }  
   for(i=other;i>=1;i--){  
       if(i>first)  
            continue;  
        strcpy(temp,s);  
       str[0]='+';  
        str[1]=i+'0';  
        strcat(s,str);  
        divide(s,i,other-i);  
        strcpy(s,temp);  
    }  
}  
搜索更多相关主题的帖子: void 正整数 用户 
2012-03-31 15:19
share32
Rank: 7Rank: 7Rank: 7
等 级:黑侠
帖 子:214
专家分:663
注 册:2011-12-1
收藏
得分:5 
使用递归函数做的, 有一个很复杂的函数推导过程, 我现在的书上有, 你可以百度一下.
2012-03-31 15:51
kmj_IT
Rank: 2
等 级:论坛游民
帖 子:17
专家分:10
注 册:2012-3-17
收藏
得分:0 
回复 2楼 share32
百度什么,不懂
不过下面是完整代码,如果理解的话还是烦劳讲讲,或者给个链接我自己去看
16.#include<stdio.h>  
17.#include<string.h>  
18.  
19.//计算划分种数  
20.int divideNumber(int n,int m)  
21.{  
22.    if(m==1 || n==1)  
23.        return 1;  
24.    if(n<m)  
25.        return divideNumber(n,n);  
26.    else if(n==m)  
27.        return divideNumber(n,m-1)+1;  
28.    else  
29.        return divideNumber(n-m,m)+divideNumber(n,m-1);  
30.}  
31.  
32.//输出划分结果  
33.void divide(char *s,int first,int other)  
34.{  
35.    int i;   
36.    static char t[50];//保存上一次的输出结果  
37.    char temp[50],str[3]={0};  
38.    if(other==0){  
39.         if(s[0]==t[0])  
40.            printf(",%s",s);  
41.         else  
42.             printf("%s",s);   
43.         strcpy(t,s);  
44.    }  
45.    for(i=other;i>=1;i--){  
46.        if(i>first)  
47.            continue;  
48.        strcpy(temp,s);  
49.        str[0]='+';  
50.        str[1]=i+'0';  
51.        strcat(s,str);  
52.        divide(s,i,other-i);  
53.        strcpy(s,temp);  
54.    }  
55.}  
56.  
57.void main()  
58.{  
59.    int i;  
60.    int n;  
61.    char s[50]={0};  
62.    char str[3]={0};  
63.    scanf("%d",&n);  
64.    printf("划分种数:%d\n",divideNumber(n,n));  
65.    for(i=n;i>=1;i--){  
66.        if(i==n)  
67.            printf("%d",n);  
68.        else{  
69.            s[0]=0;  
70.            str[0]='0'+i;  
71.            strcat(s,str);  
72.            divide(s,i,n-i);     
73.        }  
74.        puts("");      
75.    }  
76.}  
2012-04-02 21:41
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:5 
划分种数时数学问题,学过递推数组之类的可以试着自己推

求划分则是递归的应用,你还是自己用手一步一步模拟函数过程,复杂点的递归旁人真的很难解释清楚的,自己理解最好
2012-04-02 23:23
kmj_IT
Rank: 2
等 级:论坛游民
帖 子:17
专家分:10
注 册:2012-3-17
收藏
得分:0 
哦,好吧
2012-04-12 12:52
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
收藏
得分:0 
把这个题AC了  你那个问题还是问题吗
http://acm.hit.
整数划分是一个经典的问题。希望这道题会对你的组合数学的解题能力有所帮助。

Input

每组输入是两个整数n和k。(1 <= n <= 50, 1 <= k <= n)

Output

对于每组输入,请输出六行。

第一行: 将n划分成若干正整数之和的划分数。
第二行: 将n划分成k个正整数之和的划分数。
第三行: 将n划分成最大数不超过k的划分数。
第四行: 将n划分成若干奇正整数之和的划分数。
第五行: 将n划分成若干不同整数之和的划分数。
第六行: 打印一个空行。

Sample Input

5 2Sample Output
7
2
3
3
3Hint:将5划分成若干正整数之和的划分为: 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1
将5划分成2个正整数之和的划分为: 3+2, 4+1
将5划分成最大数不超过2的划分为: 1+1+1+1+1, 1+1+1+2, 1+2+2
将5划分成若干奇正整数之和的划分为: 5, 1+1+3, 1+1+1+1+1
将5划分成若干不同整数之和的划分为: 5, 1+4, 2+3
程序代码:
#include <stdio.h>
#include <string.h>
int answer[7];
bool foot[50];

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);
}

void dfs2(int n,int k,int depth,int front)
{
        if(depth > k)return ;
        if(0 == n)
        {
                if(depth == k)answer[2]++;
                return ;
        }
        int i;
        for(i = n;i;i--)
        {
                if(i<=front)
                {
                        int temp = front;
                        front = i;           
                        dfs2(n-i,k,depth+1,front);
                        front = temp;
                }
        }
}


void dfs4(int n,int k,int front)
{
        if(0 == n)
        {
                answer[4]++;
                return ;
        }
        int i;
        for(i = n;i;i--)
        {
                if((i & 0x01) && i<=front)
                {
                        int temp = front;
                        front = i;           
                        dfs4(n-i,k,front);
                        front = temp;
                }
        }
}

void dfs5(int n,int k,int front)
{
        if(0 == n)
        {
                answer[5]++;
                return ;
        }

        int i;
        for(i = n;i;i--)
        {
                if(!foot[i] && i<=front)
                {
                        foot[i] = true;
                        int temp = front;
                        front = i;           
                        dfs5(n-i,k,front);
                        front = temp;
                        foot[i] = false;
                }
        }

}

int main()
{
        int n,k;
        while(EOF != scanf("%d%d",&n,&k))
        {
                memset(answer,0,sizeof(answer));
                memset(foot,0,sizeof(foot));
                dfs2(n,k,0,100);
                dfs4(n,k,100);
                dfs5(n,k,100);

                printf("%d\n",q(n,n));
                printf("%d\n",answer[2]);
                printf("%d\n",q(n,k));
                printf("%d\n",answer[4]);
                printf("%d\n\n",answer[5]);
               
        }
        return 0;
}


                                         
===========深入<----------------->浅出============
2012-04-12 17:17
快速回复:整数的划分问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.041853 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved