这题是用动态规划来做么？ - 编程论坛

#2

林月儿2016-02-19 21:39

应该是

#3

令狐少侠562016-02-19 21:57

回复 2楼林月儿

我看着像因子分解那个题，可是函数写不出来。

#4

拉链2016-02-20 10:21

这就是一个递归因数分解，不需要动态规划。

#5

令狐少侠562016-02-20 12:58

回复 4楼拉链

这个我之前也是这样想的，可代码感觉写不出来。
输出的规律可能不是递归的那种

#6

拉链2016-02-20 21:56

弄了个练手，递归的，请参考提宝贵意见：

程序代码：

#include <stdio.h>
void ff(int a[],int n,int p)
{   //递归显示所有因数分解算式
    int i;
    i=p>0?1:0;  //第一次显示因数1
    for(;i<p;i++)printf("%d * ",a[i]);
    printf("%d * %d\n",a[i],n);   //显示算式
    if(a[p]*a[p]>n)return;
    for(i=2;i*i<=n;i++)
    {
        if(!(n%i))
        {
            a[++p]=i;     //存储因数
            ff(a,n/i,p);  //递归调用
            p--;          //回溯，剪枝
        }
    }
}
void main()
{
    int n,a[100];
    scanf("%d",&n);
    a[0]=1;
    ff(a,n,0);
}

#7

令狐少侠562016-02-21 11:25

回复 6楼拉链

对回溯剪枝不了解啊，能说明一下吗？
我正在看代码怎么运行的

#8

拉链2016-02-21 12:13

道理很简单：我用一个数组存储组成算式的因子，随着递归深度加深，因子增多，p值增大，直到出现重复分解退出递归，递归退出后进入for循环尝试下一个因子，此时必须恢复p递归前的值，放弃旧因子分支，进入下一个因子分支。

[此贴子已经被作者于2016-2-21 12:14编辑过]

#9

令狐少侠562016-02-21 16:35

回复 8楼拉链

我把你的代码运行过程大致在纸上画了一下，然后我觉得i=p>0?1:0;  这条语句挺难想到的。
    i=p>0?1:0;  //第一次显示因数1
    for(;i<p;i++)printf("%d * ",a[i]);
    printf("%d * %d\n",a[i],n);   //显示算式

你写出代码用了多长时间啊

#10

令狐少侠562016-02-21 17:01

回复 8楼拉链

你有画图什么的辅助分析么？？

#11

拉链2016-02-21 21:42

这么个小东西哪要画图辅助分析。
昨天中午看到帖子，感觉就是个递归因数分解的题，类似于找零钱组合，下午打麻将，晚饭后被老婆替下，玩游戏、看论坛，看到你回帖，就边玩游戏边构思，9：30开写，再花10分钟调试成功，估计带构思一起不到一小时吧。

#12

令狐少侠562016-02-21 22:27

回复 11楼拉链

大叔好，都结婚了。。。。
我还单身。。。cry

#13

Alar302016-02-22 09:25

看不懂啊
什么题

#14

令狐少侠562016-02-23 10:14

回复 13楼 Alar30

看输入输出就知道了

#15

拉链2016-03-01 12:04

今天看到c论坛里的埃及分数题目，感觉可以用这个算法来做，才发现我在6楼的算法有错误，数据大了后就出现了重复(如540：【5,6,18】;【6,5,18】是重复），因此修改如下即可：

程序代码：

#include <stdio.h>
void ff(int a[],int n,int p)
{   //递归显示所有因数分解算式
    int i;
    i=p>0?1:0;  //第一次显示因数1
    for(;i<p;i++)printf("%d * ",a[i]);
    printf("%d * %d\n",a[i],n);   //显示算式
    if(a[p]*a[p]>n)return;
    for(i=p>0?a[p]:2;i*i<=n;i++)
    {
        if(!(n%i))
        {
            a[++p]=i;     //存储因数
            ff(a,n/i,p);  //递归调用
            p--;          //回溯，剪枝
        }
    }
}
void main()
{
    int n,a[100];
    scanf("%d",&n);
    a[0]=1;
    ff(a,n,0);
}