急!各路大神求解C语言

形如:1/a 的分数称为单位分数。

可以把1分解为若干个互不相同的单位分数之和。
例如:
1 = 1/2 + 1/3 + 1/9 + 1/18
1 = 1/2 + 1/3 + 1/10 + 1/15
1 = 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/15 + 1/35 + 1/45 + 1/231
等等,类似这样的分解无穷无尽。

我们增加一个约束条件:最大的分母必须不超过30

请你求出分解为n项时的所有不同分解法。

数据格式要求:

输入一个整数n,表示要分解为n项(n<12)
输出分解后的单位分数项,中间用一个空格分开。
每种分解法占用一行,行间的顺序按照分母从小到大排序。

例如,
输入:
4
程序应该输出:
1/2 1/3 1/8 1/24
1/2 1/3 1/9 1/18
1/2 1/3 1/10 1/15
1/2 1/4 1/5 1/20
1/2 1/4 1/6 1/12

再例如,
输入:
5
程序应该输出:
1/2 1/3 1/12 1/21 1/28
1/2 1/4 1/6 1/21 1/28
1/2 1/4 1/7 1/14 1/28
1/2 1/4 1/8 1/12 1/24
1/2 1/4 1/9 1/12 1/18
1/2 1/4 1/10 1/12 1/15
1/2 1/5 1/6 1/12 1/20
1/3 1/4 1/5 1/6 1/20

资源约定:
峰值内存消耗 < 256M
CPU消耗 < 2000ms

c

3个回答

首先说明一下,在没有说明 CPU 主频的情况下要求时间,是不合理的,一个 10M 的 CPU,和一个 3.2G 的CPU,它们的 CPU消耗 2000ms 能相同吗?

这样的问题,对于程序来说,最简单的方法是穷举。

 //c++ 要分母小于等于30的话 41行改成"if(a[n]>30)"
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 100

using namespace std;
long long a[MAXN+8],ans[MAXN+8],n;
bool find_ans;
long long gcd(long long a,long long b)
{
    long long t;
    while(b)
    {
        t=a%b;
        a=b;
        b=t;
    }
    return a;
}
bool better()
{
    int i;
    for(i=n;i>=0;i--)
    {
        if(a[i]==ans[i])
            continue;
        return (ans[i]==0||a[i]<ans[i]);
    }
    return 0;
}
void dfs(int cur,int s,long long fz,long long fm)
{
    if(cur==n)
    {
        if(fm%fz)
            return ;
        a[cur]=fm/fz;/*
        if(better())
            memcpy(ans,a,sizeof(long long)*(n+1));*/
        if(a[n]>=30)
            return ;
        for(int i=0;i<n;i++)
            printf("1/%d ",(int)a[i]);
        printf("1/%d\n",(int)a[n]);
        return ;
    }
    s=(int)max(s*1LL,fm/fz+1);
    int i;
    long long A,B,Gcd;
    for(i=s;;i++)
    {
        if((i*fz)>=(fm*(n-cur+1)))
            break;
        a[cur]=i;
        B=fm*i;
        A=fz*i-fm;
        Gcd=gcd(A,B);
        dfs(cur+1,i+1,A/Gcd,B/Gcd);
    }
    return ;
}
int main()
{
    long long a,b;
    //cin>>a>>b;
    a=1,b=1;
    cin>>n;
    n--;
    dfs(0,b/a+1,a,b);
    return 0;
}
SilentHeartDZ
SilentHeartDZ 大神能解释一下dfs函数吗?我看了N久没搞懂,求解啊,不胜感激!!!
5 年多之前 回复

C语言版的,只是稍微改了改

# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# define MAXN 100

int max(int a,int b)
{
    return a>b?a:b;
}

long long a[MAXN+8],ans[MAXN+8],n;
_Bool find_ans;
long long gcd(long long a,long long b)
{
    long long t;
    while(b)
    {
        t=a%b;
        a=b;
        b=t;
    }
    return a;
}
_Bool better()
{
    int i;
    for(i=n;i>=0;i--)
    {
        if(a[i]==ans[i])
            continue;
        return (ans[i]==0||a[i]<ans[i]);
    }
    return 0;
}
void dfs(int cur,int s,long long fz,long long fm)
{
    if(cur==n)
    {
        int i;
        if(fm%fz)
            return ;
        a[cur]=fm/fz;
        if(a[n]>=30)
            return ;
        for(i=0;i<n;i++)
            printf("1/%d ",(int)a[i]);
        printf("1/%d\n",(int)a[n]);
        return ;
    }
    s=(int)max(s*1LL,fm/fz+1);
    int i;
    long long A,B,Gcd;
    for(i=s;;i++)
    {
        if((i*fz)>=(fm*(n-cur+1)))
            break;
        a[cur]=i;
        B=fm*i;
        A=fz*i-fm;
        Gcd=gcd(A,B);
        dfs(cur+1,i+1,A/Gcd,B/Gcd);
    }
    return ;
}
int main()
{
    long long a,b;
    //cin>>a>>b;
    a=1,b=1;
    scanf("%lld", &n);
    n--;
    dfs(0,b/a+1,a,b);
    return 0;
}

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问