威佐夫博弈：取石子游戏算法——挑战PythonTip

2017-12-16T16:30:00+08:00

PythonTip 里未攻克的题目，如取石子游戏，如今积累工作经验之后从新挑战，成功了。把过程记录分享下。

描述:¶

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目a和b，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。如果你是胜者，输出Win,否则输出Loose。例如，a=3,b=1, 则输出Win(你先在a中取一个，此时a=2，b=1,此时无论对方怎么取，你都能将所有石子都拿走).

分析（动态规划）：¶

我的思路是转变成图形化表示，二维表中点(x,y)用W表示会赢，L表示为输。

(x,y)的结果显然决定与前面已填好的(m,n) , 其中m,n 分别小于 x,y 。所以可以用动态规划。根据之前失败坐标的集合推算本行的失败坐标。

并且每行至多有一个失败坐标。所以能保证动态规划的时间复杂度不会很高。

当我从(0,0)开始，填到(a,b)时就知道结果了。

明显(x,y)和(y,x)结果一样，因此我刚开始只填半个表，导致结果不准，看了其他人的奇异坐标才明白到自己的错误。从新填好。

错误填表分析过程¶

我根据这个过程写出版本一代码。

正确填表分析过程¶

我本来猜测需要推到前面代码从来。幸运的是，运行正常的版本二的代码只在版本一加一行就可以了。

下面是我的算法代码，比较简洁。动态规划确实强大，另外还有分治法也强。

Python代码:¶

################################################################################
# print "T: 二维坐标表示法, 每行至多有一个失败坐标。二维表只填半边导致失误，改正" 
################################################################################
if a < b: a,b = b,a

m = [(0,0)]  # 失败的坐标纪录池
for i in range(1,a+1):
    for j in range(i+1):
        # if i == j or j == 0: # win
        #     continue

        for x in m:
            if (i-x[0]) == (j-x[1]) or i == x[0] or j == x[1]: # win
                break
        else:  # else 是for的部分，break for的时候也break了else
            m.append((i,j)) # 版本一：二维表只填半边，所以只有这行代码
            m.append((j,i)) # 版本二：二维表两边都填，多加这一行就OK了
        #print i,j,m

print "Loose" if (a,b) in m else "Win"

【实习记】2014-08-29算法学习Boyer-Moore和最长公共子串（LCS）问题——阿里校招题

2014-08-29T21:23:00+08:00

最长公共子串问题分析¶

其实这是一个序贯决策问题，可以用动态规划来求解。我们采用一个二维矩阵来记录中间的结果。这个二维矩阵怎么构造呢？直接举个例子吧：”bab”和”caba”(当然我们现在一眼就可以看出来最长公共子串是”ba”或”ab”)

b　　a　　b

c　　0　　0　　0

a　　0　　1　　0

b　　1　　0　　1

a　　0　　1　　0

我们看矩阵的斜对角线最长的那个就能找出最长公共子串。

不过在二维矩阵上找最长的由1组成的斜对角线也是件麻烦费时的事，下面改进：当要在矩阵是填1时让它等于其左上角元素加1。

b　　a　　b

c　　0　　0　　0

a　　0　　1　　0

b　　1　　0　　2

a　　0　　2　　0

这样矩阵中的最大元素就是最长公共子串的长度。

在构造这个二维矩阵的过程中由于得出矩阵的某一行后其上一行就没用了，所以实际上在程序中可以用一维数组来代替这个矩阵。

代码实践¶

根据以上算法使用C语言实践了一下。

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int comfix(const char* stra, const char* strb);
int main(void){
    const char
        *stra = "hello world",
        *strb = "malloc";
    printf("%s,%s: %d\n", stra, strb, comfix(stra, strb));
    return 0;
}

int comfix(const char* stra, const char* strb){
    /*
     * 变量第一字符
     * c:char*, l:len
     * 变量第二字符
     * s:small, l:large
     */
    const char
        *cs  = stra,
        *cl  = strb;
    int ret = 0,
        la  = strlen(stra),
        lb  = strlen(strb),
        ls  = la,
        ll  = lb;
    /* 如果不对，就调换呗 */
    if (lb<la)
        cs = strb, ls = lb, cl = stra, ll = la;
    /* 矩阵，只保存矩阵的一行即可动态之 */
    int *pint = (int*)malloc((ls+1)*4);
    memset(pint ,0 , (ls+1)*4);
    int i, j;
    for (i=0; i<ll; i++){
        /* 生成下一行，同时上一行内容被回收 */
       for (j=ls; j>ret; j--)
           if (cl[i]==cs[j])
               pint[j] = pint[j-1]+1;
       /* 如果有更大就更新ret */
       for (j=ls; j>ret; j--)
           if (pint[j]>ret)
               ret = pint[j];
    }
    return ret;
}

这种算法非常巧妙地化繁为简，有时换一个思路，就会扩然开朗！

比较喜欢这种锻炼。

参考¶

研究了求最长公共子串问题，顺便研究了字符串匹配

字符串匹配的Boyer-Moore算法 http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html

字符串匹配的KMP算法 http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

动态规划算法之：最长公共子序列 & 最长公共子串（LCS） http://my.oschina.net/leejun2005/blog/117167

Linux迷+Python粉 - 动态规划

威佐夫博弈：取石子游戏算法——挑战PythonTip

描述:¶

分析（动态规划）：¶

错误填表分析过程¶

正确填表分析过程¶

Python代码:¶

【实习记】2014-08-29算法学习Boyer-Moore和最长公共子串（LCS）问题——阿里校招题

最长公共子串问题分析¶

代码实践¶

参考¶