贪心法:输入一个真分数,编写程序输出其表示为埃及分数之和的形式。如7/8=1/2+1/3+1/24,15/16=1/2+1/3+1/10+1/240,分母和分子分别由键盘分两次输入。python代码
时间: 2023-07-15 12:13:16 浏览: 166
knapsack.rar_数值算法/人工智能_C/C++_
以下是使用贪心算法的 Python 代码:
```python
# 求 a/b 的埃及分数表示
def egyptian_fraction(a, b):
res = []
while a != 0:
# 向上取整,得到 ceil(b/a)
c = -(-b // a)
res.append(c)
# 计算 a/b - 1/c
a = a * c - b
b = b * c
# 约分
d = math.gcd(a, b)
a //= d
b //= d
return res
# 输入分子和分母
numerator = int(input("请输入分子:"))
denominator = int(input("请输入分母:"))
# 求分数的埃及分数表示
ef = egyptian_fraction(numerator, denominator)
# 输出结果
print(f"{numerator}/{denominator}=", end="")
for i in range(len(ef)):
print(f"1/{ef[i]}", end="")
if i != len(ef) - 1:
print("+", end="")
else:
print()
```
示例输入:
```
请输入分子:7
请输入分母:8
```
示例输出:
```
7/8=1/2+1/3+1/24
```
阅读全文