Notebook
Search…
埃及分数

描述:

每一个分数都可以表达为多个不同的单元分数的和,
单元分数: 分子为1且分母为正整数

举例:

2/3 --> 1/2 + 1/6
6/14 --> 1/3 + 1/11 + 1/231
12/13 --> 1/2 + 1/3 + 1/12 + 1/156

输入:

a,b (a为输入分数的分子, b为输入分数的分母, 假定分母大于等于分子

输出:

对应单元分数的分母序列
Input : 2,3
Output : [2,6]
Solution is below !

思路

(分子 a, 分母 b):
  1. 1.
    如果 b 能整除 a,直接返回 b/a
  2. 2.
    如果 b 不能整除 a,则采用贪心算法的思想,每次求出最接近 a/b 的单元分数(假定为c),再使用递归的方法求得余下部分 a/b - c 的单元分数

实现

Python
C++
def EgyptianFraction(numerator, denominator):
result = []
if denominator % numerator == 0:
result.append(denominator // numerator)
elif numerator < denominator:
# 计算出最大单元分数
unit = denominator // numerator + 1
result.append(unit)
# 求出余下部分的单元分数 a/b - 1/c = (a*c-1) / (b*c)
remain = EgyptianFraction(numerator * unit - denominator,denominator * unit)
result.extend(remain)
# 不考虑其他情况
return result
vector<int> EgyptianFraction( unsigned int numerator, unsigned int denominator )
{
vector<int> ret;
vector<int> remain;
int unit;
if ( denominator % numerator == 0) // eg. 2/6
{
ret.push_back( denominator / numerator );
return ret;
}
else if ( numerator < denominator )
{
unit = denominator / numerator + 1;
ret.push_back( unit );
remain = EgyptianFraction( numerator*unit - denominator, denominator*unit );
}
ret.insert( end( ret ), begin( remain ), end( remain ) );
return ret;
}
Copy link
On this page
描述:
举例:
输入:
输出:
思路
实现