1/a 的分解数

ゝ一世哀愁。 2022-05-28 00:46 159阅读 0赞

可以把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

题目虽然说是不超过30,但是它给的样例却是小于30 的，不过思路就是这样了

#include<cstdio>
    #include<cmath>
    #include<set>
    #include<algorithm>
    using namespace std;
    int num[32],n,vis[32];
    void dfs(int step)
    {
    
        if(step>n)
        {
            double s=0;
            for(int i=1; i<=n; i++)
            {
                s=s+1.0/num[i];
            }
            //printf("%lf ",s);
            if(abs(s-1)<0.000000001)
            {
                set<int> S;
                for(int i=1; i<=n; i++)
                {
                    S.insert(num[i]);
                    printf("1/%d%c",num[i],i!=n?' ':'\n');
                }
            }
            return ;
        }
    
        for(int i=2; i<=30; i++)
        {
            if(!vis[i]&&num[step-1]<i)
            {
                num[step]=i;
                vis[i]=1;
                dfs(step+1);
                vis[i]=0;
            }
        }
    }
    
    int main()
    {
        //printf("%lf\n",1.0/2+1.0/4+1.0/6+1.0/20+1.0/30);
        //printf("%lf\n",1.0/3+1.0/4+1.0/5+1.0/6+1.0/20);
        scanf("%d",&n);
        dfs(1);
        return 0;
    }