Comment on page

埃及分数

描述：
每一个分数都可以表达为多个不同的单元分数的和， 
单元分数： 分子为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
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;
}
​

使括号平衡的最小交换次数

DynamicProgramming

Last modified 4yr ago