最近开始做Project Euler里的题目，做到第三题就有点小小的卡住了。第三题的题目如文章标题，需要找到一个自然数的最大质因数。 假设输入的自然数是N，最直接的方法是从小到大算出N的每一个因数，然后再判断这个因数是不是质数。显然这种算法的复杂度很高。在最坏情况下是O(N^2)的复杂度。 自己想更好的算法，没有想出来，只好借助于Google，看到了这样一个思路： 函数biggest(N)是求最大质因数的函数。 在函数里，先将N里的2除完，余下的商M是0或者一个奇数。如果是0，那么N是2的次方，2就是N的最大质因数。 如果余下的商是奇数，那么将M用从3开始的到sqrt(M)+1的奇数J试商。如果能被奇数J除尽，那么J一定是质数。再递归求M/J的商的最大质因数I，并将I与J比较，取较大的一个。 这个算法的巧妙之处就是用3开始的奇数试商。比如如果M能被3除尽，那么将3和biggest(M/3)比较。这样的递归，可以保证把M中的3都除尽，这样以来，3的次方就不会出现在返回结果里。同理，5、7、11这些质数也会被除尽。因此只要在试奇数商的时候被除尽了，那么这个奇数就是质数。 算法实现如下：

比如一个数组[4,6,7]可以输出成： 0 0 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 连续的1可以被看作一个直方。 基本思路：将输出看作一个矩阵，矩阵的大小是由原数组的长度N和数组中最大的数字M决定。左上角的坐标是（0，0），右下角的是（N，M）。则原问题被转化为，如何将原来的一维数组转化为这样一个二维数组，二位数组的每一个元素对应相应的坐标打印出来的数字是0还是1。以直方图的第一列为例，新的二维数组是a[M][N], 那么a[*][0]这一列则应该是0，0，0，1，1，1，1。具体代码如下： 另外一个有趣的小现象后面的故事： 大家可以尝试一下，142,857这个数与2、3、4、5、6相乘的6个不同结果，全是由“1”，“2”，“4”，“5”，“7”，“8”这六个数排列组合而成的。 这是为什么呢？ 原因在于1/7的结果的是0.142857142857…..无限循环，之所以能这样循环，是因为1除以7的展开式里，商为1的时候余3，商为4的时候余2，……，一直到商为7的时候余1，余1的时候开始循环。因为一个数除以7只能有6个余数，所以这个无限寻婚小数的周期是6。 那142,857和7的余数相乘的结果的奥秘也就不难看出了，1除以7的余数是3、2、6、4、5、1，导致的商是1、4、2、8、5、7，那么如果是2除以7，则是把上面的余数的循环变成了从4开始，商的循环变成了从2开始，但是商的循环中的那几个数还是不变的。2/7 = 2 * (1/7)，也就等于2*0.142857  循环，组成循环的数字不会变。同理，142857与3，4，5，6的乘积仍然是那几个数字的排练组合。

今天的题目： 实现Random Shuffle的功能，给你一个随机数发生器把一个数组里的元素乱序。 关于“随机乱序“这个概念，我自己的定义是1）新数列和就数列中元素排列的顺序不一样，是为乱序;2）乱序后不能以某种规律来恢复原序，是为随机。 我的思路： 随机从数组A中选一个数，将之作为输出数组的第一个元素，然后将这个元素从数组A中删除得到A’，再从 A’中随机选一个元素，将之作为输出数组的第二个元素。 如此循环下去，得到的输出数组就是一个随机大乱原有数组元素排序的新数组。 地里还有个思路： for(int i=0; i<n; i++) swap(x[n],x[rand()%(n)]); 每次都用数组最后一个数，和前面随机位置的数交换。 这个思路比我的思路要简洁，节省了存储空间。而且因该也满足以上我对题目的理解。然后从这个算法还能衍生别的算法，比如先随到一个m，然后将原数列分成A[0]-A[m]和A[m+1]-A[n-1]两个数列，然后将两个数列分别按照上面的方法打乱顺序。 如果还想跟随机一点，那么不要用数组最后一个位置的数与之前的数交换，而是用数组中随机的一个位置作为一个交换位置，总是让这个位置上的数随机的同它之前或者之后的某一个数交换。

今天的题目是： 如何写出一个简单的4则运算的程序。如输入 ” 1 -2*3 + 6/3″ ，输出 -3。只用支持正整数，不用考虑有括号的情况。 思路：因为不用考虑括号，所以乘和除的优先级最高。可以先把输入字符串用“+”和“-”分隔成一个数组，数组的结构是一个数字和符号间隔，把乘除法的项当作一个数字处理，如题目中的输入会被分成[“1″,”-“,”2*3″,”+”,”6/3″]，然后再每三个数组项计算一次，把得到的结果加入到剩下的数组里，递归计算。如果计算过程中碰到还有乘除法的项，如”2*3″，则先把这个项算出来。 具体代码如下：

写在前面—— 准备从这周开始，平常每两天一道题，周末争取一天一道题，练练招式。题目会源自一个叫做CareerCup的网站（需翻了个墙），上面有各种IT公司的面试题，基本集中在基础算法方面。这将成为我的博客中的一个系列——“做做题”。 今天的题目是： “Write a code which return square of any number, but you can not use Star or caret sign” 我的第一个思路就是把这个数加N遍就好了： 但是这个解显然只对整数有效，并且效率低下，我试了一下100000000，一分钟过去了还的不到结果，然后强制终止的时候，python崩溃了……