In a 挪威科学博物馆 https://nordnorsk.vitensenter.no/我遇到了以下数学游戏:
目标是放置从 0 到 9 的 10 位数字,使两种产品之间的差异最接近于零。 (246是目前最低分)。
回到家我写了以下暴力代码:
import time
from itertools import permutations
def form_number(x, y, z, a, b):
# not explicitly stated, but presume that leading zeroes are not allowed
if x == 0 or a == 0:
return 0
return ((100 * x) + (10 * y) + z) * ((10 * a) + b)
def find_nearest_zero(*args):
assert len(args) == 10
return form_number(*args[:5]) - form_number(*args[5:])
if __name__ == '__main__':
start = time.time()
count = 0
for p in permutations(range(10), 10):
result = find_nearest_zero(*p)
if result == 0:
count += 1
print '{}{}{} * {}{} = {n}'.format(*p[:5], n=form_number(*p[:5]))
print '{}{}{} * {}{} = {n}'.format(*p[5:], n=form_number(*p[5:]))
print
print 'found {} solutions'.format(count)
print time.time() - start
如果我们不允许前导零,那么这将在大约 12 秒内打印 128 个可能的解决方案。
但我想知道,是否有一种算法或更好的方法以非暴力方式解决这个问题?
如果您假设存在差值为 0 的解,则可以通过质因数来实现。
If ab - cd = 0,则 a 的质因数b and cd 必须相同。您可以通过遍历所有 3 位素数(只有 143 个)来开始搜索,并查看它们是否具有仅包含析取数字的倍数。如果是这种情况,您有 2 个三位数号码,只需检查 2 个位数即可。
如果找不到解决方案,请继续查找 2 位数质数,并查找具有分离数字的 2 或 3 位数倍数。那么你只需要对剩下的2个数进行排列即可,这样就少了很多。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)