一个常见的脑筋急转弯是用0..9
精确地填充下面的空格一次,以使总和最小化。在
xxx*xx
- xxx*xx
=
一种解决方案是408 x 37 - 296 x 51 = 0
。然而,这个问题很容易解决,因为只有10! = 3.6*10^6
排列的数字。下面我写了一个简单的代码来解决这个问题。在
一个类似但更困难的问题是用十六进制数来做同样的事情。只使用一次数字0...F
,这样
最小化。我在这里只找到了两种解决办法。在
FD906 x 5A1
- 7EC83 x B42
= 0
FD906 x 15A
- 7EC83 x 2B4
= 0
有没有更聪明的方法来洗牌,找到零解?问题是现在有太多的排列需要暴力强制。在
对于16位数字系统,存在3.5 * 10^14
,而基数为10的版本只有3.6 * 10^6
。因此,一个简单的暴力解决方案需要很多年的时间。我的第一次尝试是把数字分成两组
[14, 13, 10, 9, 6, 5, 2, 1] [15, 12, 11, 8, 7, 4, 3, 0]
第一组是第一个产品,第二组是第二个产品。创建这些列表的方式是使用贪婪排序,两者的总和都是60。这应该给我们一个更高的理论上平等的机会。要迭代的置换数现在是8! * 8! = 1.6*10^9
。好得多,但仍然比基础10版本大150倍。在
任何一种更快的方法都是值得赞赏的。在
Base10版本
from itertools import permutations
def find_sum_equal_n():
n = 0
num = range(10)
solutions = set()
for perm in permutations(num):
tple = product_sum(perm)
if product_num(tple) == n:
tple = well_ordered(tple)
solutions.add(tple)
return list(solutions)
def product_num(tple):
total = tple[0]*tple[1] - tple[2]*tple[3]
return total
def product_sum(perm):
num1 = 100*perm[0] + 10*perm[1] + perm[2]
num2 = 10*perm[3] + perm[4]
num3 = 100*perm[5] + 10*perm[6] + perm[7]
num4 = 10*perm[8] + perm[9]
return (num1, num2, num3, num4)
def well_ordered(tple):
a = max(tple[0], tple[1])
b = min(tple[0], tple[1])
c = max(tple[2], tple[3])
d = min(tple[2], tple[3])
if a > c:
tple = (a,b,c,d)
else:
tple = (c,d,a,b)
return tple
def display_solutions(lst):
print '============================================'
for solution in lst:
display_sum(solution)
print '============================================'
def display_sum(tple):
print ' ' + str_num(tple[0], 3) + ' x ' + str_num(tple[1], 2)
print ' - ' + str_num(tple[2], 3) + ' x ' + str_num(tple[3], 2)
print ' = ', product_num(tple)
def str_num(num, length):
str_num = str(num)
diff = max(length - len(str_num), 0)
string = ' '*diff
string += str_num
return string
if __name__ == '__main__':
lst = find_sum_equal_n()
display_solutions(lst)
print len(lst)
Base16版本
from itertools import permutations
def find_sum_equal_n_16bit():
solutions = set()
key1 = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
key = key1 + ['A', 'B', 'C', 'D', 'E', 'F']
best = 10**6
num1, num2 = split_list(16)
list_perm2 = list(permutations(num2))
for perm1 in permutations(num1):
for perm2 in list_perm2:
perm = perm1 + perm2
tple = product_sum(perm)
temp_best = abs(product_num(tple))
if temp_best <= best:
print perm
display_tuple(tuple_2_16bit(perm))
best = temp_best
if temp_best == 0:
solutions.add(perm)
return list(solutions)
def split_list(n):
num = range(1, n)
high = [num.pop()]
low = []
while len(num) > 0:
while sum(high) >= sum(low) and len(num) > 0:
low.append(num.pop())
temp_high = high
high = low
low = temp_high
if len(high) > len(low):
low.append(0)
else:
high.append(0)
return high, low
def product_sum(tple):
lst = list(tple)
num1 = sum(k*16**(4-i) for i, k in enumerate(lst[0:5]))
num2 = sum(k*16**(2-i) for i, k in enumerate(lst[5:8]))
num3 = sum(k*16**(4-i) for i, k in enumerate(lst[8:13]))
num4 = sum(k*16**(2-i) for i, k in enumerate(lst[13:16]))
return (num1, num2, num3, num4)
def product_num(tple):
total = tple[0]*tple[1] - tple[2]*tple[3]
return total
def tuple_2_16bit(tple):
key1 = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
key = key1 + ['A', 'B', 'C', 'D', 'E', 'F']
lst = [str(key[i]) for i in tple]
return (''.join(lst[0: 5]), ''.join(lst[5: 8]), ''.join(lst[8: 13]), ''.join(lst[13: 16]))
def display_tuple(tple):
print ' ' + tple[0] + ' x ' + tple[1]
print ' - ' + tple[2] + ' x ' + tple[3]
print ' = ', int(tple[0], 16)*int(tple[1], 16) - int(tple[2], 16)*int(tple[3], 16)
if __name__ == '__main__':
print find_sum_equal_n_16bit()
在}。在
axx*bxx
中寻找一些a
和b
我们可以看到这限制了第二个产品中c
和{在10位数字中,您可以按此顺序构建(数字表示顺序)
这样,当检测到结果将大于先前找到的最优解时,可以通过快速减少搜索树的大部分来生成数字。在
相关问题 更多 >
编程相关推荐