最近开始做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这些质数也会被除尽。因此只要在试奇数商的时候被除尽了，那么这个奇数就是质数。

算法实现如下：

import sys
from math import sqrt

def find_largest_primef(n):
    is_prime = True
    if n == 2:
        return n
    if n%2 == 0:
        print n, 'getting rid of 2s..'
        is_prime = False
        return find_largest_primef(n/2)
    else:
        for i in range(3,int(sqrt(n))+1,2):
            print 'try ..', i
            if n%i == 0:
                print 'n: ', n, 'i: ', i
                is_prime = False
                return pick_larger(i, find_largest_primef(n/i))
    if is_prime:
        print n, 'is prime!'
        return n

def pick_larger(first, second):
    if first >= second:
        return first
    else: return second

if __name__ == '__main__':
    print find_largest_primef(int(sys.argv[1]))

上了两个月的学了，可以稍微写点东西了。

1. 背景信息

标题已经说明，现在我在密歇根大学信息学院读两年制的MS in Information。需要注意的这里不是Information System，也不是Information Science，只有一个单词。我写简历的时候自作主张的写成MS in Information Science，被就业指导中心的人专门提出来需要修改。

学院很年轻，90年代成立的吧，前身是图书馆学系，去年刚刚搬到学校新建的North Quad楼。更多背景信息可以去这里看。MSI下设好多个方向，有Human  Computer Interaction这种比较热门的，也有传统方相如Library and Information Science等。我现在是HCI方向的，准备加Information Analysis and Retrieval做第二个方向。

这个信息学院在US News上排名前三，院长讲话的时候说“welcome to one of the finest iSchool in the States”。

2. 招生情况

新生报到的时候，介绍会上院长说今年一共招了170个左右的研究生，其中150个左右的硕士。这只是大概的数字。去年申请的时候好像在网站上看过说就读学生一共不到400个，后来网站改版我再也找不到这个数字了……

今年中国学生一共有20个左右吧，其中博士生大概两三个。整个学院很跨学科，所以学生背景很丰富。就我了解的，中国学生的背景有来自各类学校的各种专业：北大、清华、北邮、对外经贸等等，MIS、人机工程、CS等等。

学校招生办公室总在招学生临时工，我觉得太没意思所以从来没申请过，哪位同学有兴趣去干这类工作的话应该会有更多信息。

3. 学校周边环境和生活

Ann Arbor，距底特律大概1个小时车程。典型大学城，downtown就在中校旁边。Ann Arbor的U-M分为中、北、南三大校区，校园面积号称全美数一数二。不同校区有学校免费公车链接，另外市政的公交用学生卡可以免费坐。校巴一直到凌晨3点还有，所以住在学校提供的宿舍没有车去图书馆刷夜也是比较方便。市政公交比较坑爹，一般10点后就没有了，周末六点后就没有了。

小镇消费，应该比大城市便宜。我住的学校研究生公寓，两人一个Town House，上层卧室下面客厅厨房，地下室有洗衣机和烘干机，东西坏了打电话给Housing第二天就有人来修，一个月571包水电网。我选择这个房子最大的理由就是省事。同学大多住在校外，房租一般不到500，便宜的400出头。有的包一些bill，有的完全不包。我食量较大，所以会在吃上面花很多钱。这里午、晚餐如果不自带的话6块左右可以搞定。自己做更便宜。

但是我听到几个美国学生抱怨过这里物价较高，不知是否可信。

已经在这里住了一年的室友告诉我这里很安全。我也觉得还蛮安全的。学校保卫处时不时会发Crime Alert，两个月收到三四封的，一些打劫和骚扰的案子。这种透明度让我感觉到更安全。

夜生活很丰富，刚刚开学跟同学去夜店和脱衣舞俱乐部疯过一次。

4. 学习生活

累得跟狗似的。

周一到周五白天上课晚上图书馆，周六周天白天图书馆晚上图书馆。其中穿插着各种课程项目的小组会议。通宵过几次，平均每天1点半睡觉。图书馆晚上1点都还人满。我喜欢这个气氛。

当然你也可以换一种方式学习，不要像我一样选那么多课……

选课很自由。

5. 就业、实验室和social

刚来两个月，就业情况不好说，听学院宣传还是可以的。每周都能收到很多招聘信息，前几届前辈们实习就业的公司看起来也很光鲜。只是我没有什么数据。

我估计会继续申PhD，所以现在正在找一个PhD师兄帮他写代码，争取明年能找一个教授帮他做点事情，然后明年秋天能搞一个TA或者RA来付学费。

6. 其他

U-M最出名的应该是橄榄球了，这学期几乎每周都有比赛，所以周末的交通流量似乎比平时大很多。

最后贴几张照片吧：

• 体育场附近的小公园：

• 中校的大钟楼

• 研究生院的自习室

• 北校图书馆窗外

比如一个数组[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。具体代码如下：

#include <stdio.h>

void main(){
    int array_origin[4] = {4,6,10,9};
    int array_print[10][4] = {{0}};
    int i, j;
    for (i=0; i<4; i++){
        for (j=0;j<array_origin[i];j++){
            array_print[9-j][i] = 1;
        }
    }
    for (i=0; i<10; i++){
        for (j=0; j<4; j++){
            printf("%d ", array_print[i][j]);
        }
        printf("\n");
    }
}

另外一个有趣的小现象后面的故事：
大家可以尝试一下，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″，则先把这个项算出来。

具体代码如下： (more…)