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

深度优先搜索，自己尝试写的代码输出总是有点问题，网上找到大神写的代码，研读了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，所以在计算时要保证分子分母要用最大公约数求最简形式，以及判断分母是否能被分子整除），

然后对剩下的数进行上述操作，即对剩下的数再进行深度优先遍历（笔者就是在求下一次遍历的数时伤脑筋࿰

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！