最近又玩了一遍manufactoria,发现有些关卡都快忘记怎么过的，这次还是写下来好了。
关卡按照从左到右，从上到下计数。
1. Move robots from the entrance(top) to the exit (bottom)! 将机器从入口(顶部)移到出口(底部)!
简单，不多说
2. If a robot’s string starts with blue, accept. Otherwise, reject! 如果机器以蓝色字符开头，则接受。否则，丢弃。
3. ACCEPT:if there are three or more blues! 如果有三个或三个以上的蓝色的，则接受
4. ACCEPT: if a robot contains NO red! 如果机器不包含红色的，则接受。
5. OUTPUT:The input,but with the first symbol at the end! 对于输入的字符，将第一个字符移到末尾作为输出
6. ACCEPT: if the tape has only alternating colors! 如果只存在交替字符，则接受。
意思就是字符如果是交替出现的则接受，如蓝红蓝红蓝，红蓝红蓝等等，而蓝蓝红，红蓝蓝等出现连续相同的字符，所以不接受
7. OUTPUT：Replace blue with green, and red with yellow! 输出：将蓝色换成绿色，将红色换成黄色。
8. ACCEPT: if the tape ends with two blues! 如果末尾是两个蓝色，则接受。
9. OUTPUT： Put a green at the begining, and a yellow at the end! 输出： 对于输入的字符，在开头中添加一个绿色字符，在末尾中添加一个黄色字符。
10. ACCEPT: Strings that begin and end with the same color! 如果开始字符和结束字符时相同，则接受。
11. ACCEPT: With blue as 1 and red as 0, accept odd binary string! 把蓝色当做1，红色当做0， 接受奇数二进制数。
其实就是接受蓝色结尾的字符。
12. ACCEPT: Some number of blue, then the same number of red! 接受： 一些蓝色的，然后相同数量的红色的。
也就是接受诸如蓝蓝红红，蓝蓝蓝红红红等，当然空字符也要接受，因为空字符代表0个蓝色，0个红色。
解决办法是每次除去一个蓝色和红色
13.OUTPUT: Swap blue for red, and red for blue! 输出： 将蓝色换成红色，红色换成蓝色。
也就是将字符串中的颜色互换。
14. OUTPUT: All of the blue, but none of the red! 输出字符串中的所有蓝色字符，不输出红色字符。
也就是将字符串中的所有红色字符去掉，留下蓝色的。
15. OUTPUT： The input, but with the last symbol moved to the front! 输出： 对于输入的字符，将最后一个字符移动最前面。
在末尾添加一个绿色，用来标示最后一个字符
16. OUTPUT: With blue as 1 and red as 0, multiply by 8! 输出：把蓝色当做1，红色当做0，将二进制字符串乘以8.
其实也就是在字符串末尾添加3个0，也就是添加三个红色
17.ACCEPT: With blue as 1 and red as 0, accept binary strings > 15! 接受：把蓝色当做1，红色当做0，接受大于15的字符串。
18. An equal number of blue and red, in any order! 只要字符串中包含相同个数的蓝色和红色，则接受。
使用与12相同的办法
19.OUTPUT：Put a yellow in the middle of the (even-lenght) string! 输出： 在字符串（偶数个字符串）的中间放置一个黄色字符。
在头尾都添加黄色，之后每个循环，头部的向前移一步，尾部的向后移一步。
20.ACCEPT: X blue, then X red, then X more blue, for any X! 接受： X个蓝色，然后X个红色，接着X个蓝色，对于X没有限制。
也就是接受蓝红蓝，蓝蓝红红蓝蓝等字符串，对于空字符也接受，因为它代表0个蓝色，然后0个红色，接着0个蓝色。
使用与12题相同的办法
21.OUTPUT: The input, but with all blues moved to the front! 输出：对于输入，将字符串中所有的蓝色移到前面。
逆向思维，将红色字符移到后面
22.OUTPUT: With blue as 1 and red as 0, add 1 to the binary string! 输出： 将蓝色当做1，红色当做0，将二进制字符串加上1.
在末尾添加一个黄色，每个循环，如果黄色左边的是蓝色，则蓝色变成红色，并且黄色左后退一个字符，
如果黄色左边的红色，则将红色变成蓝色，程序结束。
23. ACCEPT: With blue as 1 and red as 0, accept natural powers of four! 接受：把蓝色当做1，红色当做0，接受四的开方
24.ACCEPT: (Even-length) strings that repeat midway through! 接受：(偶数长度)接受从中间开始重复的字符串
意思就是接受的字符串是偶数长度，前半段和后半段是一样的，如蓝红红蓝红红，
25. ACCEPT: If there are exactly twice as many blues as red! 接受：如果蓝色的个数是红色个数的两倍，则接受。
每个循环，除去两个蓝色和一个红色
26. OUTPUT: Reverse the input string! 输出：将输入的字符串逆转输出
27.OUTPUT: Subtract 1 from the binary string!(Input >= 1) 输出：从二进制字符串中减去1(输入字符串>=1)
在末尾添加一个黄色，每个循环，如果黄色左边的是红色，则红色变成蓝色，并且黄色左后退一个字符，
如果黄色左边的蓝色，则将蓝色变成红色，程序结束。
28.ACCEPT: Perfectly symmetrical strings! 接受：完美对称字符串！
意思就是回文串，也就是从左读到右和从右读到左是一样的。
每个循环，头尾消去的字符是一样的。
29.ACCEPT: Two identical strings, separated by a green! 接受：两个相同的字符串，由绿色隔开。
30. ACCEPT: Read the tape as two numbers, A and B, split by a green: accept if A > B! 接受：读入的字符串当做两个二进制数，A和B，由一个绿色隔开，如果A>B则接受。
每次比较A和B的字符，分四种情况
蓝蓝，继续比较A和B剩余的字符
红红，继续比较A和B剩余的字符
蓝红，这种情况下，有个小技巧，将B的字符再消去一个，这时A剩余的字符比B剩余的字符长，则A>B
红蓝,A剩余的字符比B剩余的字符长，则A>B
31. OUTPUT: Read the tape as two numbers, A and B, split by a green: output A + B! 输出：读入的字符串当做两个二进制数，A和B，由一个绿色隔开，输出A+B的和！
将A和B都转成黄色字符，之后再将黄色字符转成二进制。

之前就选修过Angrew Ng的机器学习,但是那是一味的只追求进度，所以收获甚微，于是这次又重新选修了这门课。

这么课程使用Octave语言，这可以说是Matlab的开源版本，使用这种高阶语言，可以让我们更专注于算法层面。今天在实现sigmoid函数时，老是出错。原来是忘记了在每个for循环之后加上end. 还有一点需要说明的是,在Octave中，数组是从1开始的。

1
2
3
4
5
6
7
8

x = [1 2; 3 4]
g = zeros(size(x));
for i = 1:size(x,1)
    for j = 1:size(x,2)
        g(i,j) = 1 / (1 + e ^ (-x(i, j)));
    end 
end
g

习惯在命令行下工作，都忘记用什么软件打开PDF了，才发现是用evince打开。

于是在命令行下执行evince 文件名即可打开，例如要打开ex1.pdf,则执行evince ex1.pdf

挂载U盘
mount -t auto /dev/sdb1 /mnt/usb
如果在mnt目录下不存在usb目录 则先执行 mkdir /mnt/usb,其中/mnt/usb为挂载目录,也可以使用将U盘挂载到其它目录

之后卸载U盘
umount /mnt/usb

如果是文件名中包含中文，还会遇到乱码问题，所以还要加上-o iocharset=utf8

整数划分说的是给定一个正整数N，求一共有多少种方式将N分解成不超过N的正整数和。
例如：N=4时，一共有5种划分，如下：
4 = 4
4 = 3 + 1
4 = 2 + 2
4 = 2 + 1 + 1
4 = 1 + 1 + 1 + 1

如果没记错的话，在《C名题精选百则》中出现过这题。我们可以考虑更普遍的情况，将正整数N分解成不超过M的整数和的情况。
对于这种情况，可以将分解分成包含整数M和不包含整数M的情况。令f(N,M)为总共的分解方式，则
f(N,M) = f(N - M, M) + f(N, M -1)，于是写成程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def partition(n):
    return _partition(n, n)

def _partition(n, m):
    if n == 0:
        return 1
    if n < 0:
        return 0
    if m == 1:
        return 1
    else:
        return _partition(n - m, m) + _partition(n, m - 1)
for i in xrange(1, 10):
    print i, partition(i)

只是当n比较大时，递归的效率太慢了，于是用动态规划重写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def partition(n):
    dp = [[0 for i in xrange(n + 1)] for j in xrange(n + 1)]
    for i in xrange(n + 1):
        dp[i][1] = 1
        dp[0][i] = 1
    for i in xrange(1, n + 1):
        for j in xrange(1, n + 1):
            if i - j >= 0:
                dp[i][j] = dp[i - j][j] + dp[i][j - 1]
            else:
                dp[i][j] = dp[i][j - 1]
    return dp[n][n]

for i in xrange(1, 10):
    print i, partition(i)

在欧拉工程中，很多时候都需要用到素数，而得到素数比较好就是用筛法生成。筛法还是很容易理解的，随便找一本教科书的可以找到。

有了这个函数后，要得到100以内的素数就非常容易了。

1
2
3
4
5
6
7
8
9
10
11
12
13

def getPrimes(n):
    primes = [True for i in xrange(n + 1)]
    primes[0] = primes[1] = False
    for x in xrange(2, n + 1):
        if not primes[x]:
            continue
        m = x * x
        while m <= n:
            primes[m] = False
            m += x
    return [i for i in xrange(n + 1) if primes[i]]

print get_primes(100)

2014年8月16日更新：
才发现这个函数的速度还不理想，于是改成

1
2
3
4
5
6
7
8
9

def getPrimes(n):
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    i = 2
    while i * i <= n:
        if primes[i]:
            primes[i * i:n + 1:i] = [False] * ((n - i * i) / i + 1)
        i += 1
    return [i for i in xrange(n + 1) if primes[i]]

之所以这么改，可参看Python筛法求素数的优化

知道这题，是在冼镜光的《C名题精选百则》中。记得这题是自己做出来的，所以稍微回忆一下，就能记起来。也许算法之所以这么难，就是因为不是自己想出来的，所以虽然看过，却很容易忘记。或许应该不只是看算法，而要知道原始作者的思考过程，这样才能真正理解。就像要想理解TCP/IP协议一样，比较好的办法是自己去设计TCP协议，看如何保证可靠传输。扯远了。

对于这题，很容易写出如下程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def max_con_sum(s):
    length = len(s)
    max_sum = s[0]
    i = 0
    temp_sum = s[0]
    while i + 1 < length:
        i += 1
        if temp_sum < 0:
            temp_sum = 0;
        temp_sum += s[i]
        if temp_sum > max_sum:
            max_sum = temp_sum

    return max_sum
L = [2,-3,3,50]
print max_con_sum(L)

而如果还想知道最大连续子序列的开始位置和结束位置，之需要再增加额外的记录信息即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

def max_con_sum(s):
    length = len(s)
    max_sum = s[0]
    start = 0;
    end = 0
    i = 0
    temp_sum = s[0]
    while i + 1 < length:
        i += 1
        if temp_sum < 0:
            temp_sum = 0;
            start = i
        temp_sum += s[i]
        if temp_sum > max_sum:
            max_sum = temp_sum
            end = i

    return (max_sum,start,end)
L = [2, -3, 3, 50]
max_sum,start,end =  max_con_sum(L)
print max_sum,start,end

给你一个list L, 如 L=[2,8,3,50], 对L进行选择排序并输出交换次数,
如样例L的结果为1

对于这题，无非就是写一个选择排序，在排序过程中记下交换的次数。很意外的是Pythontip上竟然会有那么多人写错，
按照选择排序的定义，写一个应该是分分钟的事。或许这帮人都没看书。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

L=[2,8,3,50]
length = len(L)
count = 0
for i in xrange(length):
    minum = L[i]
    index = i
    for j in xrange(i + 1, length):
        if L[j] < minum:
            minum = L[j]
            index = j
    if index != i:
        L[i],L[index] = L[index],L[i]
        count += 1
print count

扔蛋问题说的是，100层楼，给两个特制鸡蛋。从某层扔下鸡蛋，鸡蛋就会碎。问至少要测试多少次才能试出这个层数。对于这个问题，许多人都可以背出答案14层。但如果是200层呢?

事实上，还可以对这题进行扩展，假设n层，e个鸡蛋，求至少要测试多少次，才能测出这个层数。

对于这题，可以用动态规划。还是在面4399时，面试官要我解释什么是动态规划，当时没能解释清楚。现在想来，动态规划有两个重要的因素，一个是最优子结构，还有一个是重叠子问题。按我的理解，最优子结构说的是，当前的最优解包含了子问题的最优解。重叠子问题说的是，子问题具有重叠部分。

而对于这题，可以写出一个递推公式,设n为楼层数,e为鸡蛋数。
f(n,e) = 1 + min{max{f(n - r, e),f(r - 1, e -1)}} 其中r属于{2,3,…,n - 1},初始条件为f(n,1) = n, f(1,e) = 1, f(2,e) = 2. 这里要求n,e都是正整数。
写成程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def egg(n, e=2):
    dp = [[n for i in xrange(e + 1)] for j in xrange(n + 1)]
    for i in xrange(1, n + 1):
        dp[i][1] = i
    for i in xrange(1, e + 1):
        dp[1][i] = 1
        dp[2][i] = 2
    for i in xrange(3, n + 1):
        for j in xrange(2, e + 1):
            for r in xrange(1, n):
                dp[i][j] = min(dp[i][j], 1 + max(dp[i - r][j], dp[r - 1][j - 1]))

    return dp[n][e]

print egg(100, 2)

对于鸡蛋数为2时，还有特殊的解法。在鸡蛋数为2时，楼层数与测试次数如下：
1 1
2 2
3 2
4 3
5 3
6 3
7 4
8 4
9 4
10 4
11 5
…
于是可以猜测,对于楼层数n ,只要找到第一个x ,使得 x * (x + 1) / 2 >= n即可，对于100,正好是14。类似地，对于开头提出的鸡蛋数为2，楼层数为200时，测试层数也可以类似的求解

取石子游戏说的是有两堆任意数量的小石子，游戏由两个人轮流取石子，对于取法，游戏规定有两种，一种是可以在任意的一堆中，取走任意多的石子；一种是在两堆中同时取走相同数量的石子。游戏规定，最后把石子全部取完的为胜者。现在假设初始时两堆石子的数目为a和b, a <= b，假设双方都采取最好的策略，问先取的人是胜者还是败者。

对于这题，可以得到在以下情况下，先取的人必败，其它情况下，先取的人必胜。
1 2
3 5
4 7
6 10
8 13
9 16
…

可以看出，这两个数字之间一定有规律，而说到规律，很容易想到的是黄金分割比。记得那时还很粗心的将其中的数字写错了，于是任晓祎同学就过来纠正了。时光飞逝啊，已经过去三年了。