松田富民 2015-02-01 16:56 采纳率: 0%
浏览 2125
已采纳

急!各路大神求解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

  • 写回答

3条回答 默认 最新

  • 91program 博客专家认证 2015-02-01 23:35
    关注

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

     //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;
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(2条)

报告相同问题?

问题事件

  • 已采纳回答 2月21日

悬赏问题

  • ¥100 有人会搭建GPT-J-6B框架吗?有偿
  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名