Python使用超高效算法查找所有类似123-45-67+89=100的组合

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

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

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

参考代码:

运行结果:

原文发布于微信公众号 - Python小屋(Python_xiaowu)

原文发表时间:2018-02-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏云霄雨霁

设计模式----状态模式

1570
来自专栏linux运维学习

linux学习第六十五篇:for循环,while循环, break跳出循环,continue结束本次循环

for循环 语法:for 变量名 in 条件; do …; done for循环会以空格作为分隔符 案例1 #!/bin/bash sum=0 for i ...

29210
来自专栏向治洪

Android热补丁技术—dexposed原理简析(手机淘宝采用方案)

上篇文章《Android无线开发的几种常用技术》我们介绍了几种android移动应用开发中的常用技术,其中的热补丁正在被越来越多的开发团队所使用,它涉及到da...

2786
来自专栏向治洪

java造成内存泄露原因

一、Java内存回收机制  不论哪种语言的内存分配方式,都需要返回所分配内存的真实地址,也就是返回一个指针到内存块的首地址。Java中对象是采用new或者反射的...

28710
来自专栏web前端教室

javascript 红皮高程(18)-- 布尔操作符

可算是把绕来绕去的二进制-位操作符,给学完了。至少我学到了十之八九,你呢,,, 接下来是布尔操作符,它一共有三个,非(NOT),与(AND),或(OR)。 1,...

1999
来自专栏未闻Code

Python列表与deque的区别

3532
来自专栏hbbliyong

Invalid bound statement (not found)

1.6K2
来自专栏Vamei实验室

Java进阶05 多线程

多线程 多线程(multiple thread)是计算机实现多任务并行处理的一种方式。 在单线程情况下,计算机中存在一个控制权,并按照顺序依次执行指令。单线程好...

2226
来自专栏Golang语言社区

Golang语言--闭包和普通函数调用区别

代码: ? 运行这段程序,输出结果为 1 2 3 3 2 1 这里就是普通的函数调用,每次调用func p时,完成 i 的值复制,然后打印,此时 i 值复制了3...

2816
来自专栏Android-薛之涛

Android Parcelable

      Paracelable是android自己的实现序列化的接口,是anroid推荐使用的.那么什么事序列化呢?简单来说就是将对象转换为可以传输的二进制...

1043

扫码关注云+社区

领取腾讯云代金券