| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1445 人关注过本帖
标题:【求助】高手求解 数的分解问题
只看楼主 加入收藏
K_Tpanda
Rank: 1
等 级:新手上路
帖 子:7
专家分:0
注 册:2011-11-3
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:19 
【求助】高手求解 数的分解问题
现给任意一个数n ,要求分解为任意的  m 个数相乘 有几种不同的算法 ??  
 例如: 输入一个输 6
        要求分解为3个数相乘
        求一共有几种不同的算法 ?
  即 6=1*1*6 6=1*2*3
搜索更多相关主题的帖子: 美国 影响 
2011-11-03 18:55
K_Tpanda
Rank: 1
等 级:新手上路
帖 子:7
专家分:0
注 册:2011-11-3
收藏
得分:0 
各位大侠救命啊  使用C语言编程解决啊   
2011-11-03 18:59
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:0 
学过动态规划吗?
如果没有的话就只能搜索了
2011-11-03 20:54
幻影逍遥
Rank: 2
等 级:论坛游民
帖 子:23
专家分:24
注 册:2011-10-31
收藏
得分:0 
任意M个数相乘?数学知识有限,不知道怎么弄。能给一个确定的值还是能弄出来。
2011-11-03 23:34
liao06550107
Rank: 7Rank: 7Rank: 7
等 级:黑侠
威 望:2
帖 子:111
专家分:696
注 册:2011-10-2
收藏
得分:0 
程序代码:
#include <stdio.h>

void main()
{
    long a, b, c, i=0, n;
    printf("请输入数:\n");
    scanf("%ld", &n);
    for(a=1; a<=n; a++)
        for(b=a; b<=n; b++)
            for(c=b; c<=n; c++)
            {
                if(a*b*c==n)
                {
                    printf("%ld*%ld*%ld=%ld\n",a,b,c,n);
                        i++;
                }
                else continue;
            }
            printf("总共算法有%ld种\n",i);

}

听不同的音乐,看不同的书,游历不同的城市,邂逅不同的人,走的多了,站的高了,自然就看的远了。
2011-11-04 00:35
幻影逍遥
Rank: 2
等 级:论坛游民
帖 子:23
专家分:24
注 册:2011-10-31
收藏
得分:0 
回复 5楼 liao06550107
楼主说的是任意m个数相乘,不一定是3个数。有没有高手出来解答啊。
2011-11-04 11:54
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:0 
动态规划:f[i][j][k]表示将数j分解为i个数相乘,其中最大的数<=k时的数目,则

f[i][j][k]=sum{f[i-1][j/t][t] (满足(t<=k && j%t==0)}

最后的答案=f[m][n][n]

搜索实现的方法类似

[ 本帖最后由 czz5242199 于 2011-11-4 12:10 编辑 ]
2011-11-04 12:09
K_Tpanda
Rank: 1
等 级:新手上路
帖 子:7
专家分:0
注 册:2011-11-3
收藏
得分:0 
一个有点建议的都没有啊啊  
2011-11-04 16:48
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:0 
回复 8楼 K_Tpanda
我被忽略了么。。一定要我写个程序吗..
2011-11-04 18:56
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:0 
#include <stdio.h>
#include <stdlib.h>

int f[21][1001][1001],n,m,i,k,j,t;

int main()
{
    scanf("%d %d",&n,&m);         /*  最大支持n=1000,m=20 */
    memset(f,0,sizeof(f));
    for (j=1; j<=n; j++)
     for (k=1; k<=j; k++) f[1][j][k]=1;
    for (i=2; i<=m; i++)
     for (j=1; j<=n; j++)
      for (k=1; k<=j; k++)
       for (t=1; t<=k; t++)
       if (j%t==0) f[i][j][k]+=f[i-1][j/t][t];
    printf("%d\n",f[m][n][n]);
    system("pause");
}

你可以用数据测试此程序

貌似速度还是有点慢,1000 20得算好几十秒,求高人优化

[ 本帖最后由 czz5242199 于 2011-11-4 19:27 编辑 ]
2011-11-04 19:24
快速回复:【求助】高手求解 数的分解问题
数据加载中...
 
   



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

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