把1分解为若干个互不相同的单位分数之和

一时失言乱红尘 2022-08-07 04:59 168阅读 0赞

深度优先搜索，自己尝试写的代码输出总是有点问题，网上找到大神写的代码，研读了2个小时，真的十分精妙，在此加上注释分享

**问题重述：**

形如：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）  
输出分解后的单位分数项，中间用一个空格分开。  
每种分解法占用一行，行间的顺序按照分母从小到大排序。

**问题分析：**

所谓深度优先搜索就是一个一个的试，如果OK就往下执行，遇到不符合的条件判断就return。

对本题来说：将找到分式的分母存入数组（分子都是1，所以在计算时要保证分子分母要用最大公约数求最简形式，以及判断分母是否能被分子整除），

然后对剩下的数进行上述操作，即对剩下的数再进行深度优先遍历（笔者就是在求下一次遍历的数时伤脑筋，网上的代码就十分巧妙）。

理解网上代码后，笔者自己重写一遍，并附上详细注释。

**代码：**

#include <iostream>
    using namespace std;
    int a[31];
    int n;
    int Divisor(int x,int y)//最大公约数
    {
    	int temp;
    	while(y)
    	{
    		temp = x % y;
    		x = y;
    		y = temp;
    	}
    	return x;
    }
    
    void Dfs(int cur,int s,int fz,int fm)
    {
    	if(n == cur)
    	{
    		if(fm%fz) //分母不能被分子整除的话就没有意义了
    			return ;
    		a[n] = fm / fz;
    		if(a[n] > 30)//题目要求分母不能超过30
    			return ;
    		for(int i =1; i < n; i++)//答应结果
    			cout <<"1/"<<a[i]<<" ";
    		cout << "1/"<<a[n]<<endl;
    		return;
    	}
    	s=max(s,fm/fz+1);
    	//但是如果使用max的话会重复打印相同的结果
    	//fz当前分子
    	//fm当前分母
    	//s表示下一个分母的最小值
    	//s= fm/fz + 1;
    	int i;
    	int A;
    	int B;
    	int gcd;
    	for(i=s;;i++)
    	{
    		if((i*fz)>=(fm*(n-cur+1)))
                break;
    		//实际含义是：
    		//fz/fm >= (n-cur+1)/i
    		//fz/fm表示当前剩余的值
    		//i表示下一个分母的最小值也就是整个分式的最大值，
    		//根据不等式原理，容易看出break;条件 
    		//此处需要用>=否则将无法排除分式中出现相同的分数例如：1= 1/2+1/2
    		a[cur]=i;
    		A = fz*i - fm;//剩下分式的分子
    		B = fm * i;//剩下分式的分母
    		
    		//以上两句代码根据当前分式的大小fz/fm 减去已经用掉的分式 1/i得到
    		//通分即为 (fz*i-fm)/fm*i
    		
    		gcd = Divisor(A,B);
    		Dfs (cur + 1,i + 1,A/gcd,B/gcd);
    		//深度优先搜索(递归)，此处分子和分母都需要约分
    	}
    	return ;
    }
    
    
    int main()
    {
    	cin >> n;
    	Dfs(1,2,1,1);
    	return 0;
    }