求解问题... - 编程论坛

#2

cnfarer2010-04-19 09:16

几乎是算法问题！提供一个解题思路！
可以用递归来解决：写一个函数返回N的所包含的最大X的阶乘（如7是3！+1），然后以N-X!作为函数的参数，继续求解，依此类推，直到最后一个数正好是某数的阶乘为止！

#3

mywaylgh2010-04-19 10:57

程序代码：

#include <stdio.h>
#include <stdlib.h>
#define MAX 10000000

int factorial(int *fa)
{
    int i=1;
    int p=1;
    while(1)
    {
        p = p*i;
        if (p>MAX) break;
        fa[i++]=p;
    }
    return i-1;
}

int lit_n(int *pn,int *fa, int s)
{
    int i;
    for (i=1;i<s ;i++ )
        if (*pn>=fa[i] && *pn<fa[i+1])
        {
            *pn = *pn-fa[i];
            return i;
        }
    return -1;
}

int main()
{
    int fa[100];
    int pr[100];
    int s = factorial(fa);
    int n,cons_n,i=0,j;

    scanf("%d",&n);
    cons_n = n;

    pr[0]=lit_n(&n,fa, s);
    while(n>0)
    {
        i++;
        pr[i]=lit_n(&n,fa, pr[i-1]);
        if (pr[i]==-1)
            break;
    }
    if (n==0)
    {
        printf("%d = %d!",cons_n,pr[0]);
        for (j=1;j<=i ;j++ )
            printf(" + %d!",pr[j]);
        printf("\n");
    }
    else
        printf("Can not decompose %d\n",cons_n);

    return 0;
}

楼上算法，不过不是递归，做了小小的改进
晕，我发现我快成IT民工了

#4

mylzy1592010-04-21 16:20

提供思路就行了...忘记说了..不好意思..

#5

mylzy1592010-04-21 16:49

#include <iostream>
using namespace std;
void fun(int x,int sum)
{
    int i,a,result=1;
    for(i=1;i<=x;i++)
    {
        for(a=1;a<=i;a++)
            result*=a;
        if((x-result)==0)//判断整数的最后一个阶层
        {
            sum+=i;
            cout<<sum;
            exit(0);
        }
        if((x-result)<result)//判断是否是最大阶层
        {
            sum+=i;
            fun(x-result,sum);
        }
        result=1;
    }
}
main()
{
    int sum=0,n;
    cin>>n;
    fun(n,sum);
}
貌似能行/..