算法趣题（一）

前言

从本篇文章开始，开始一系列的算法题目的学习笔记。算法的题目来源于《程序员的算法趣题》这本书，作者是日本技术作家增井敏克，只不过作者在书中实现的代码是用Ruby这门语言实现的（谁叫Ruby是日本人发明的呢~~~）。

我写这一系列文章的目的，是为了刷刷题目，提高自己的算法思维能力。还有就是，我看书的过程中，发现作者其实在一些细节方面由于语言的限制，没讲得很明白，所以我将使用目前最流行的Python语言来实现这些算法。当然了，后期也会用C语言或者Java语言实现算法。同时，我会对一些题目做一些变形，来学习算法。

每篇文章，我都会选择两道算法题目，然后对其分析，给出它的代码实现。希望我写完这一系列笔记，可以去刷LeetCode题目；也希望我的读者朋友们，从中能了解一些有趣的算法知识！

1. 回文十进制数

问题描述：求十进制、二进制、八进制表示都是回文数的所有数字中，大于10的最小数值。例如：9（十进制数）= 1001（二进制数）= 11（八进制数），这样的数字，但要找到一个大于10的最小的符合规则的数字。

分析

因为二进制数字不能以0开头，所以二进制数字首位必定是数字1，根据回文数的特点可推知，二进制数最低位也必须是1。因此最低位是1的二进制数，必定是一个奇数，继而可以排除所有的偶数可能性。

算法：

从大于10的最小的奇数——11开始遍历

先判断十进制是否是回文数，再去判断二进制和十六进制是否符合

由于不确定搜索范围的上限（虽然可以定义是int最大值），所以应该用while True来达到不断循环的目的，直到找到第一个三种进制都满足回文数，当前数字就是大于10的最小的回文数，跳出循环

Python代码实现

2. 数列的四则运算

问题描述：将一个十进制四位数的每一位数字，按照原来的顺序进行加减乘除运算至少一次，使得其结果为原数字的倒序，求范围在1000 ~ 9999内满足要求的数字。例如：1314：1 * 3 + 14 = 17，或1314：131 * 4 = 524这样的组合，直到满足存在一组运算，使得1、3、1、4这四个数字的计算结果为4131。

分析：

很显然，对于一个四位数而言，若要满足其结果为原来的倒序的组成的数字，就意味着倒序的结果必定是一个四位数字。

对于任何一个四位数而言，一旦出现减法和除法，这种会减少原来值的运算，肯定不可能得出新的四位数。同样的，对于加法亦是如此，因此加法在四位数与四则运算组合中，最大的可能情况是 999 + 9 = 1008，1008虽然是个四位数，但明显与范围内最大值不同。综上，只有乘法运算，才可能找到符合要求的数字。

算法：

遍历1000 ~ 10000之间的所有四位数

使用 ，来实现将组合不同长度的数字，例如：1314：'1' + '' + '2' + '*' + '3' + '' + '4' = '12 * 34'

eval函数中，不允许出现数字前面带0的操作数，例如：eval("1*001")，会报错！因此，对于每个单独的数字字符串前面的0，需要删除掉！采用，函数达到删除每个数字字符串前的0

所有组合中，若最后一位数字是0，那么依据上一步算法，会将0删去。这就意味着出现数字后面带有乘号的字符串，例如：['7', '', '5*', '']组合的字符串就是 '75 *'，而eval('75 *')操作是非法的！所有，必须删除所有数字字符串后面的乘号，用函数 来删除

所有组合中，可能会出现这样的情况：['7*', ' *', ' *', '1']，当数字之间含有两个乘号时，这是一个幂乘运算，不是乘法运算。所以，只能保留一个乘号，用函数 变换成乘法运算

为了防止出现这样的情况：['5', '7', '7', '5'] 5775，即四个数字中没有加入运算符，因此，需要判断字符串的长度至少大于4位，即至少插入一个运算符

Python代码实现

OneMoreThing…

今天的封面图挺好看的，但是截图似乎总是截不好，下面献上完整图片吧！

By Michael Payne From Unsplash