You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
67 lines
2.0 KiB
67 lines
2.0 KiB
4 months ago
|
from fractions import Fraction
|
||
|
|
||
|
# 第五章 作业一
|
||
|
# 有分数1/2,1/3,1/4,1/5,1/6,1/8,1/10,1/12,1/15,求将其中若干个分数相加和恰好等于1的组成方案,并输出
|
||
|
#
|
||
|
# 1. 给定的分数使用 Fraction 类型,可以方便地进行分数的计算和比较。
|
||
|
#
|
||
|
# 2. 使用递归来查找满足条件的组合。参数:
|
||
|
# - `target`:目标和,初始值为 1。
|
||
|
# - `current_combination`:当前已选择的分数组合,初始为空列表。
|
||
|
# - `index`:当前处理的分数在列表中的索引,初始为 0。
|
||
|
#
|
||
|
# 3. 在递归函数中,有两个选择:
|
||
|
# - 不选择当前分数:继续递归,不修改 `target` 和 `current_combination`。
|
||
|
# - 选择当前分数:继续递归,更新 `target` 为 `target - fractions[index]`,并将当前分数添加到 `current_combination` 中。
|
||
|
#
|
||
|
# 4. 当 `target` 等于 0 时,我们找到了一个满足条件的组合,将其打印出来。
|
||
|
#
|
||
|
# 5. 递归继续处理下一个分数,直到遍历完所有分数或找到所有满足条件的组合。
|
||
|
|
||
|
|
||
|
def find_combinations(
|
||
|
target: Fraction,
|
||
|
fractions: list[Fraction],
|
||
|
current_combination: list[Fraction],
|
||
|
index: int,
|
||
|
resultSet: list[list[Fraction]],
|
||
|
):
|
||
|
if target == 0:
|
||
|
resultSet.append(current_combination.copy())
|
||
|
return
|
||
|
if index >= len(fractions):
|
||
|
return
|
||
|
|
||
|
# 不选择当前分数
|
||
|
find_combinations(target, fractions, current_combination, index + 1, resultSet)
|
||
|
# 选择当前分数
|
||
|
find_combinations(
|
||
|
target - fractions[index],
|
||
|
fractions,
|
||
|
current_combination + [fractions[index]],
|
||
|
index + 1,
|
||
|
resultSet,
|
||
|
)
|
||
|
|
||
|
|
||
|
fractions = [
|
||
|
Fraction(1, 2),
|
||
|
Fraction(1, 3),
|
||
|
Fraction(1, 4),
|
||
|
Fraction(1, 5),
|
||
|
Fraction(1, 6),
|
||
|
Fraction(1, 8),
|
||
|
Fraction(1, 10),
|
||
|
Fraction(1, 12),
|
||
|
Fraction(1, 15),
|
||
|
]
|
||
|
|
||
|
result_set = []
|
||
|
|
||
|
find_combinations(
|
||
|
target=1, fractions=fractions, current_combination=[], index=0, resultSet=result_set
|
||
|
)
|
||
|
|
||
|
for result in result_set:
|
||
|
print(" + ".join(map(str, result)) + " = 1")
|