Python使用超高效算法查找所有类似123

原创 2018-02-28 董付国，胡凤国 Python小屋

问题描述：在123456789这9个数字中间插入任意多个+和-的组合，使得表达式的值为100，输出所有符合条件的表达式。

昨天发了一个暴力测试的方法来解决问题，详见Python查找所有类似于123-45-67+89 = 100的组合，但是暴力测试的方法非常慢，大概需要运行3个小时多。今天分享一个超高效的算法及其实现，可以瞬间输出所有结果，感谢中国传媒大学胡凤国老师提供这个神奇的算法。

主要思路：设计一个三进制加法算法，让8个0逐步变化到8个3，其中每一位上的数字可以是0、1、2，然后让0对应空格、1对应+、2对应-，然后在1到9之间的8个位置上分别插入空格、+或-符号，最后删掉表达式中的空格并求值，如果等于100则满足条件。

参考代码：

'''[0,0,0,0,0,0,0,0]->[0,0,0,0,0,0,0,1]->...[2,2,2,2,2,2,2,2]'''

def triAdd(operators):

lastPosition = len(operators)-1

c = 1

for i in range(lastPosition,-1,-1):

c , operators[i] = divmod(operators[i]+c,3)

if c ==0:           

return None

return 1

def main(digits='123456789',total=100):

d = ' +-'

operators = [0]*(len(digits)-1)

while not triAdd(operators):

operator = map(lambda o:d[o],operators)

exp = ''.join((o+c for o,c in zip(digits,operator)))+digits[-1]

exp = ''.join(exp.split())

if eval(exp) == total:

print(exp)

main()

结果如下：

123+45-67+8-9 123+4-5+67-89 123-45-67+89 123-4-5-6-7+8-9 12+3+4+5-6-7+89 12+3-4+5+67+8+9 12-3-4+5-6+7+89 1+23-4+56+7+8+9 1+23-4+5+6+78-9 1+2+34-5+67-8+9 1+2+3-4+5+6+78+9

相关知识

花了1个月时间，把Python库全部整理出来了，覆盖所有，建议收藏
使用美汤从HTML中提取特定的标题
Python机器学习基础教程
使用Python调用mysql
用python实现KNN算法对鸢尾花的分类
【Python 123】水仙花数玫瑰数
Hello world Python新手赛题解
基于python编程的五种鲜花识别
python利用c4.5决策树对鸢尾花卉数据集进行分类（iris）
SKYNE/python

网址: Python使用超高效算法查找所有类似123 https://www.huajiangbk.com/newsview529928.html