“好串”求解算法优化原理与Python实现
“好串”求解算法优化原理与Python实现
=====正文=======
题目要求：称一个 0-1 串是“好串”，如果它的任何子串不在其中连续出现三次以上。编写程序，输入正整数 n，输出某个长度为 n 的好串。
在数学学上可以证明：存在任意长度的好串。事实上，若 w 是一个长度为 k 的好串，将 w 中的 0 和 1 分别替换为 01 和 10 必然是一个长度为 2k 的好串（感兴趣的读者可以用反证法证明）；同时，好串的任意子串必然也是好串。
显然，单独的 0 和 1 都是好串，根据上面的性质，可以得到任意长度的好串。根据这个思路（称为“标准迭代”），可以写出下面的代码：
这个程序只有四行，算是十分短小精悍的。但是，它的可读性并不好：同时，还用到了 lambda 表达式、map 函数、字符串与列表的相互转化等十分复杂的机制；更重要的是，它的执行效率不高。
这时，应当仔细分析一下这个问题的特殊性 —— 考虑下面的 01-串序列：0、01、0110、01101001、…… （其规律为：下一个串是在上一个串的基础上添加原串的对偶串（即按位取反的串）获得）。 不难归纳证明：如果用 0 作为起始好串，上面的串列与按照标准方式迭代的序列恰好一样。
按位取反可以通过与一个全 1 序列进行异或操作得到，这样就获得了下面的代码：
细节：倒数第二行之所以需要切片操作，是因为要把异或后字串的符号位去掉。
这样，代码的效率与可读性较之于第一个版本有了大幅度的提高。但是，循环体代码里面仍然存在着进制转换、移位、求长度、切片等操作，效率仍然不是十分令人满意。同时，总感觉该问题某些特殊的性质没利用上！什么性质呢？—— 对！就是“对称性”！！！
想到了这三个字，代码的样子马上就会发生翻天覆地的变化！
这时，你可能不太相信，解决这个问题的代码竟可以简单成这样：循环体中，只存在简单的字串连接操作！
但是，冷静！这是仍然应该问一下自己：还能继续优化吗？ 中国传媒大学胡凤国老师敏锐的指出：这段代码跟原来比，多耗费了一倍的空间！
这的确是一个问题！怎么解决呢？事实上，串的长度每次增加一倍，这个“浪费”只出现在循环的最后一步！如果我们让循环少做一次，不就可以了吗？ 终极代码如下：
----------相关阅读----------
教学课件
1900页Python系列PPT分享一：基础知识（106页）
1900页Python系列PPT分享二：Python序列（列表、元组、字典、集合）（154页）
1900页Python系列PPT分享三：选择与循环结构语法及案例（96页）
1900页Python系列PPT分享四：字符串与正则表达式（109页）
1900页Python系列PPT分享五：函数设计与应用（134页）
1900页Python系列PPT分享六：面向对象程序设计（86页）
1900页Python系列PPT分享七：文件操作（132页）
1900页Python系列PPT分享八：异常处理结构与程序调试、测试（70页）
报告PPT（163页）：基于Python语言的课程群建设探讨与实践
系列题库分享
相关技术文章
Python使用超高效算法查找所有类似123-45-67+89=100的组合
Python查找所有类似于123-45-67+89 = 100的组合
数学老师从没这么教过，乘法竖式中进位可以是多位（附Python实现与测试源码）