我有一个数字数组,我想使用基本算术运算(加法、减法、乘法和除法)找到所有可能的计算,从而得到所需的数字。
例如,给定输入数组
[2, 1, 4, 6, 7]
和所需结果 3
,该函数应返回:
2 + 1 = 3
7 - 4 = 3
6 / 2 = 3
这是我想出的一个基本实现:
def find_calculations(arr, target):
results = []
operations = ['+', '-', '*', '/']
for i in range(len(arr)):
for j in range(len(arr)):
if i != j:
a, b = arr[i], arr[j]
for op in operations:
if op == '+':
if a + b == target:
results.append(f'{a} + {b} = {target}')
elif op == '-':
if a - b == target:
results.append(f'{a} - {b} = {target}')
elif op == '*':
if a * b == target:
results.append(f'{a} * {b} = {target}')
elif op == '/':
if b != 0 and a / b == target:
results.append(f'{a} / {b} = {target}')
return results
# Example usage
arr = [2, 1, 4, 6, 7]
target = 3
output = find_calculations(arr, target)
print(output)
上面示例的输出是:
['2 + 1 = 3', '7 - 4 = 3', '6 / 2 = 3']
限制:
如何改进或优化此函数以处理更大的数组或更复杂的情况?
您想要做的是评估所有可能的计算并找到导致正确结果的选项。
构建它的一种简单方法是实现 RPN 计算(反向波兰表示法)。 https://en.wikipedia.org/wiki/Reverse_Polish_notation
基本上你要做的就是枚举数字和运算符的堆栈,这样你总是比运算符多一个数字。
我认为这是一个有趣的问题,所以我决定演示如何有效地完成它。 在我的系统上,大约需要半秒才能找到所有 4193 个解决方案。
诀窍是使用动态编程来构建一个数据结构,从中可以有效地找到所有表达式。
from fractions import Fraction
def bit_subset(index, things):
i = 0
bit = 1
answer = []
while bit <= index:
if bit & index:
answer.append(things[i])
i += 1
bit += bit
return answer
def indexes_to_bit_subset(indexes):
answer = 0
for index in indexes:
answer += 2**index
return answer
def calculation_tree (digits):
# Here is the tree structure:
#
# By bit_integer of subset used
# By value reached
# [
# count_of_ways,
# [
# [
# count,
# first subset bit_integer,
# first value,
# op ('+', '-', '*', '/', None),
# second subset bit_integer (may be 0),
# second value (may be None)
# ]
# ]
# ]
#
tree = {}
# Populate with all of the raw numnbers.
for i in range(len(digits)):
# By bit_integer for 1 thing.
tree[2**i] = {
# By value reached (use fractions to avoid roundoff
Fraction(digits[i], 1): [
# Just 1 way to do it.
1,
# What are the ways? Let me tell you!
[[1, 2**i, digits[i], None, 0, None]]
]
}
# This loops over all subsets with something in the first.
for subset_index in range(1, 2**len(digits)):
# The indexes into the chosen subset.
index_subset = bit_subset(subset_index, list(range(len(digits))))
if subset_index not in tree:
subtree = {}
tree[subset_index] = subtree
# Look at ways to split it with something in both sides
for sub_subset_index in range(1, 2**len(index_subset)-1):
co_subset_index = 2**(len(index_subset)) - 1 - sub_subset_index
# We have a split by indexes into index_subset.
# We need to turn that into a split by indexes into digits
# Which we represent by integers representing bits.
index_sub_subset = bit_subset(sub_subset_index, index_subset)
sub_subset_bit_index = indexes_to_bit_subset(index_sub_subset)
index_co_subset = bit_subset(co_subset_index, index_subset)
co_subset_bit_index = indexes_to_bit_subset(index_co_subset)
# Let's pull out the already known calculation results.
subtree1 = tree[sub_subset_bit_index]
subtree2 = tree[co_subset_bit_index]
for value1 in subtree1.keys():
count1 = subtree1[value1][0]
for value2 in subtree2.keys():
count2 = subtree2[value2][0]
# We now have to add each possible operation result to subtree
options = {
'+': value1 + value2,
'-': value1 - value2,
'*': value1 * value2,
}
if value2 != 0:
options['/'] = value1 / value2
for op, value in options.items():
if value in subtree:
subtree[value][0] += count1 * count2
subtree[value][1].append([
count1 * count2,
sub_subset_bit_index,
value1,
op,
co_subset_bit_index,
value2
])
else:
subtree[value] = [
count1 * count2,
[[
count1 * count2,
sub_subset_bit_index,
value1,
op,
co_subset_bit_index,
value2
]]
]
return tree
# Yields the expressions that result in value
def expression_iter (tree, bit_integer, value):
if bit_integer in tree:
subtree = tree[bit_integer]
if value in subtree:
ways = subtree[value][1]
for (
count,
bit_integer1, value1,
op,
bit_integer2, value2
) in ways:
if op is None:
yield str(value1)
else:
for expr1 in expression_iter(tree, bit_integer1, value1):
for expr2 in expression_iter(tree, bit_integer2, value2):
yield f'({expr1} {op} {expr2})'
def all_expressions(digits, target):
tree = calculation_tree(digits)
frac_target = Fraction(target, 1)
for bit_integer, subtree in tree.items():
if frac_target in subtree:
for expr in expression_iter(tree, bit_integer, frac_target):
yield expr
for expr in all_expressions([2, 1, 4, 6, 7], 3):
print(expr)
我认为你可以做的是你可以使用 rng 让它生成随机数
模块。让他们在有理数范围内做随机数,并对其进行随机运算。如果方程等于某个数字,则打印方程。你还可以制作一个类似人工智能的简单东西,设置随机数的合理范围以使其更快。 (注意/编辑,随机范围选择一个数字,并将该数字转换为输入数字之一。)
示例
# simple 2 digit example
import random
array = [2, 5, 6, 1]
c = 1
wantedresult = 7
while c == 1:
i = random.randint(0, 4)
a = random.randint(0, 4)
numa = array[i]
numb = array[a]
answer = numb - numa
if answer == wantedresult:
print(numb + " - " + numa)
answer = numb + numa
if answer == wantedresult:
print(numb + " + " + numa)
answer = numa + numb
if answer == wantedresult:
print(numa + " + " + numb
answer = numa - numb
if answer == wantedresult:
print(numa + " - " + numb