埃及分数

描述：

每一个分数都可以表达为多个不同的单元分数的和，

单元分数： 分子为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. 如果 b 能整除 a，直接返回 b/a

2. 如果 b 不能整除 a，则采用贪心算法的思想，每次求出最接近 a/b 的单元分数（假定为c），再使用递归的方法求得余下部分 a/b - c 的单元分数

实现

Python

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

C++

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;
}