【求助】高手求解数的分解问题 - C语言论坛

编程论坛 → 开发语言 → 『 C语言论坛』 → 【求助】高手求解数的分解问题

标题：【求助】高手求解数的分解问题

只看楼主

K_Tpanda

等　级：新手上路
帖　子：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

等　级：新手上路
帖　子：7
专家分：0
注　册：2011-11-3

第 2 楼

得分:0

各位大侠救命啊使用C语言编程解决啊

2011-11-03 18:59

czz5242199

等　级：小飞侠
威　望：4
帖　子：660
专家分：2400
注　册：2011-10-26

第 3 楼

得分:0

学过动态规划吗？
如果没有的话就只能搜索了

2011-11-03 20:54

幻影逍遥

等　级：论坛游民
帖　子：23
专家分：24
注　册：2011-10-31

第 4 楼

得分:0

任意M个数相乘？数学知识有限，不知道怎么弄。能给一个确定的值还是能弄出来。

2011-11-03 23:34

liao06550107

等　级：黑侠
威　望：2
帖　子：111
专家分：696
注　册：2011-10-2

第 5 楼

得分: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

幻影逍遥

等　级：论坛游民
帖　子：23
专家分：24
注　册：2011-10-31

第 6 楼

得分:0

回复 5楼 liao06550107

楼主说的是任意m个数相乘，不一定是3个数。有没有高手出来解答啊。

2011-11-04 11:54

czz5242199

等　级：小飞侠
威　望：4
帖　子：660
专家分：2400
注　册：2011-10-26

第 7 楼

得分: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

等　级：新手上路
帖　子：7
专家分：0
注　册：2011-11-3

第 8 楼

得分:0

一个有点建议的都没有啊啊

2011-11-04 16:48

czz5242199

等　级：小飞侠
威　望：4
帖　子：660
专家分：2400
注　册：2011-10-26

第 9 楼

得分:0

回复 8楼 K_Tpanda

我被忽略了么。。一定要我写个程序吗..

2011-11-04 18:56

czz5242199

等　级：小飞侠
威　望：4
帖　子：660
专家分：2400
注　册：2011-10-26

第 10 楼

得分: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

参与讨论请移步原网站贴子：https://bbs.bccn.net/thread-354190-1-1.html