形如：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++ 要分母小于等于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;
}
首先说明一下，在没有说明 CPU 主频的情况下要求时间，是不合理的，一个 10M 的 CPU，和一个 3.2G 的CPU，它们的 CPU消耗 2000ms 能相同吗？
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;
}