Linux迷+Python粉 - 动态规划//blog.pythonwood.com/2017-12-16T16:30:00+08:00威佐夫博弈:取石子游戏算法——挑战PythonTip2017-12-16T16:30:00+08:002017-12-16T16:30:00+08:00pythonwoodtag:blog.pythonwood.com,2017-12-16:/2017/12/威佐夫博弈:取石子游戏算法——挑战PythonTip/<p><a href="http://www.pythontip.com" title="PythonTip">PythonTip</a> 里未攻克的题目,如<a href="http://www.pythontip.com/coding/code_oj_case/46" title="取石子游戏">取石子游戏</a>,如今积累工作经验之后从新挑战,成功了。把过程记录分享下。</p> <h3 id="_1">描述:<a class="headerlink" href="#_1" title="Permanent link">&para;</a></h3> <p>有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法, 一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。 现在给出初始的两堆石子的数目a和b,如果轮到你先取,假设双方都采取最好的策略 …</p><p><a href="http://www.pythontip.com" title="PythonTip">PythonTip</a> 里未攻克的题目,如<a href="http://www.pythontip.com/coding/code_oj_case/46" title="取石子游戏">取石子游戏</a>,如今积累工作经验之后从新挑战,成功了。把过程记录分享下。</p> <h3 id="_1">描述:<a class="headerlink" href="#_1" title="Permanent link">&para;</a></h3> <p>有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法, 一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。 现在给出初始的两堆石子的数目a和b,如果轮到你先取,假设双方都采取最好的策略,问最后你是胜者还是败者。 如果你是胜者,输出Win,否则输出Loose。 例如,a=3,b=1,&nbsp;则输出Win(你先在a中取一个,此时a=2,b=1,此时无论对方怎么取,你都能将所有石子都拿走).</p> <h3 id="_2">分析(动态规划):<a class="headerlink" href="#_2" title="Permanent link">&para;</a></h3> <p>我的思路是转变成图形化表示,二维表中点(x,y)用W表示会赢,L表示为输。</p> <p>(x,y)的结果显然决定与前面已填好的(m,n) , 其中m,n 分别小于 x,y 。 所以可以用动态规划。&nbsp;根据之前失败坐标的集合推算本行的失败坐标。</p> <p>并且每行至多有一个失败坐标。所以能保证动态规划的时间复杂度不会很高。</p> <p>当我从(0,0)开始,填到(a,b)时就知道结果了。</p> <p>明显(x,y)和(y,x)结果一样,因此我刚开始只填半个表,导致结果不准,看了其他人的奇异坐标才明白到自己的错误。从新填好。</p> <h4 id="_3">错误填表分析过程<a class="headerlink" href="#_3" title="Permanent link">&para;</a></h4> <p><img alt="错误填表图1" src="//blog.pythonwood.com/uploads/2017/挑战PythonTip,威佐夫博弈:取石子游戏错误填表图1.png"></p> <p><img alt="错误填表图2" src="//blog.pythonwood.com/uploads/2017/挑战PythonTip,威佐夫博弈:取石子游戏错误填表图2.png"></p> <p><img alt="错误填表图3" src="//blog.pythonwood.com/uploads/2017/挑战PythonTip,威佐夫博弈:取石子游戏错误填表图3.png"></p> <p>我根据这个过程写出版本一代码。</p> <h4 id="_4">正确填表分析过程<a class="headerlink" href="#_4" title="Permanent link">&para;</a></h4> <p><img alt="正确填表图1" src="//blog.pythonwood.com/uploads/2017/挑战PythonTip,威佐夫博弈:取石子游戏正确填表图1.png"></p> <p><img alt="正确填表图2" src="//blog.pythonwood.com/uploads/2017/挑战PythonTip,威佐夫博弈:取石子游戏正确填表图2.png"></p> <p><img alt="正确填表图3" src="//blog.pythonwood.com/uploads/2017/挑战PythonTip,威佐夫博弈:取石子游戏正确填表图3.png"></p> <p>我本来猜测需要推到前面代码从来。幸运的是,运行正常的版本二的代码只在版本一加一行就可以了。</p> <p>下面是我的算法代码,比较简洁。动态规划确实强大,另外还有分治法也强。</p> <h3 id="python">Python代码:<a class="headerlink" href="#python" title="Permanent link">&para;</a></h3> <div class="highlight"><pre><span></span>################################################################################ # print &quot;T: 二维坐标表示法, 每行至多有一个失败坐标。二维表只填半边导致失误,改正&quot; ################################################################################ if a &lt; 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 &quot;Loose&quot; if (a,b) in m else &quot;Win&quot; </pre></div>【实习记】2014-08-29算法学习Boyer-Moore和最长公共子串(LCS)问题——阿里校招题2014-08-29T21:23:00+08:002017-11-30T22:12:00+08:00pythonwoodtag:blog.pythonwood.com,2014-08-29:/2014/08/【实习记】2014-08-29算法学习Boyer-Moore和最长公共子串(LCS)问题——阿里校招题/<!-- 昨天的问题 方案一:寻找hash函数,可行性极低。 方案二:载入内存,维护成一个守护进程的服务。难度比较大。 方案三:使用前5位来索引,由前3位增至前5位唯一性,理论上是分拆记录扩大100倍,但可以就地利用mysql,最易行。 方案四:使用方案三,但增加一个表以减少冗余,但代价新开一个表,并且每次查询都select join两个表。 --> <h3 id="_1">最长公共子串问题分析<a class="headerlink" href="#_1" title="Permanent link">&para;</a></h3> <p>其实这是一个序贯决策问题,可以用动态规划来求解。我们采用一个二维矩阵来记录中间的结果。这个二维矩阵怎么构造呢?直接举个例子吧:&rdquo;bab&rdquo;和&rdquo;caba&rdquo;(当然我们现在一眼就可以看出来最长公共子串是&rdquo;ba&rdquo;或&rdquo;ab&rdquo;)</p> <p>b  a  b</p> <p>c  0  0  0 …</p><!-- 昨天的问题 方案一:寻找hash函数,可行性极低。 方案二:载入内存,维护成一个守护进程的服务。难度比较大。 方案三:使用前5位来索引,由前3位增至前5位唯一性,理论上是分拆记录扩大100倍,但可以就地利用mysql,最易行。 方案四:使用方案三,但增加一个表以减少冗余,但代价新开一个表,并且每次查询都select join两个表。 --> <h3 id="_1">最长公共子串问题分析<a class="headerlink" href="#_1" title="Permanent link">&para;</a></h3> <p>其实这是一个序贯决策问题,可以用动态规划来求解。我们采用一个二维矩阵来记录中间的结果。这个二维矩阵怎么构造呢?直接举个例子吧:&rdquo;bab&rdquo;和&rdquo;caba&rdquo;(当然我们现在一眼就可以看出来最长公共子串是&rdquo;ba&rdquo;或&rdquo;ab&rdquo;)</p> <p>b  a  b</p> <p>c  0  0  0</p> <p>a  0  1  0</p> <p>b  1  0  1</p> <p>a  0  1  0</p> <p>我们看矩阵的斜对角线最长的那个就能找出最长公共子串。</p> <p>不过在二维矩阵上找最长的由1组成的斜对角线也是件麻烦费时的事,下面改进:当要在矩阵是填1时让它等于其左上角元素加1。</p> <p>b  a  b</p> <p>c  0  0  0</p> <p>a  0  1  0</p> <p>b  1  0  2</p> <p>a  0  2  0</p> <p>这样矩阵中的最大元素就是&nbsp;最长公共子串的长度。</p> <p>在构造这个二维矩阵的过程中由于得出矩阵的某一行后其上一行就没用了,所以实际上在程序中可以用一维数组来代替这个矩阵。</p> <h3 id="_2">代码实践<a class="headerlink" href="#_2" title="Permanent link">&para;</a></h3> <p>根据以上算法&nbsp;使用C语言实践了一下。</p> <div class="highlight"><pre><span></span><span class="cp">#include</span> <span class="cpf">&lt;stdlib.h&gt;</span><span class="cp"></span> <span class="cp">#include</span> <span class="cpf">&lt;stdio.h&gt;</span><span class="cp"></span> <span class="cp">#include</span> <span class="cpf">&lt;string.h&gt;</span><span class="cp"></span> <span class="kt">int</span> <span class="nf">comfix</span><span class="p">(</span><span class="k">const</span> <span class="kt">char</span><span class="o">*</span> <span class="n">stra</span><span class="p">,</span> <span class="k">const</span> <span class="kt">char</span><span class="o">*</span> <span class="n">strb</span><span class="p">);</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(</span><span class="kt">void</span><span class="p">){</span> <span class="k">const</span> <span class="kt">char</span> <span class="o">*</span><span class="n">stra</span> <span class="o">=</span> <span class="s">&quot;hello world&quot;</span><span class="p">,</span> <span class="o">*</span><span class="n">strb</span> <span class="o">=</span> <span class="s">&quot;malloc&quot;</span><span class="p">;</span> <span class="n">printf</span><span class="p">(</span><span class="s">&quot;%s,%s: %d</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span> <span class="n">stra</span><span class="p">,</span> <span class="n">strb</span><span class="p">,</span> <span class="n">comfix</span><span class="p">(</span><span class="n">stra</span><span class="p">,</span> <span class="n">strb</span><span class="p">));</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">comfix</span><span class="p">(</span><span class="k">const</span> <span class="kt">char</span><span class="o">*</span> <span class="n">stra</span><span class="p">,</span> <span class="k">const</span> <span class="kt">char</span><span class="o">*</span> <span class="n">strb</span><span class="p">){</span> <span class="cm">/*</span> <span class="cm"> * 变量第一字符</span> <span class="cm"> * c:char*, l:len</span> <span class="cm"> * 变量第二字符</span> <span class="cm"> * s:small, l:large</span> <span class="cm"> */</span> <span class="k">const</span> <span class="kt">char</span> <span class="o">*</span><span class="n">cs</span> <span class="o">=</span> <span class="n">stra</span><span class="p">,</span> <span class="o">*</span><span class="n">cl</span> <span class="o">=</span> <span class="n">strb</span><span class="p">;</span> <span class="kt">int</span> <span class="n">ret</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">la</span> <span class="o">=</span> <span class="n">strlen</span><span class="p">(</span><span class="n">stra</span><span class="p">),</span> <span class="n">lb</span> <span class="o">=</span> <span class="n">strlen</span><span class="p">(</span><span class="n">strb</span><span class="p">),</span> <span class="n">ls</span> <span class="o">=</span> <span class="n">la</span><span class="p">,</span> <span class="n">ll</span> <span class="o">=</span> <span class="n">lb</span><span class="p">;</span> <span class="cm">/* 如果不对,就调换呗 */</span> <span class="k">if</span> <span class="p">(</span><span class="n">lb</span><span class="o">&lt;</span><span class="n">la</span><span class="p">)</span> <span class="n">cs</span> <span class="o">=</span> <span class="n">strb</span><span class="p">,</span> <span class="n">ls</span> <span class="o">=</span> <span class="n">lb</span><span class="p">,</span> <span class="n">cl</span> <span class="o">=</span> <span class="n">stra</span><span class="p">,</span> <span class="n">ll</span> <span class="o">=</span> <span class="n">la</span><span class="p">;</span> <span class="cm">/* 矩阵,只保存矩阵的一行即可动态之 */</span> <span class="kt">int</span> <span class="o">*</span><span class="n">pint</span> <span class="o">=</span> <span class="p">(</span><span class="kt">int</span><span class="o">*</span><span class="p">)</span><span class="n">malloc</span><span class="p">((</span><span class="n">ls</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span><span class="o">*</span><span class="mi">4</span><span class="p">);</span> <span class="n">memset</span><span class="p">(</span><span class="n">pint</span> <span class="p">,</span><span class="mi">0</span> <span class="p">,</span> <span class="p">(</span><span class="n">ls</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span><span class="o">*</span><span class="mi">4</span><span class="p">);</span> <span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="p">;</span> <span class="k">for</span> <span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">ll</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="cm">/* 生成下一行,同时上一行内容被回收 */</span> <span class="k">for</span> <span class="p">(</span><span class="n">j</span><span class="o">=</span><span class="n">ls</span><span class="p">;</span> <span class="n">j</span><span class="o">&gt;</span><span class="n">ret</span><span class="p">;</span> <span class="n">j</span><span class="o">--</span><span class="p">)</span> <span class="k">if</span> <span class="p">(</span><span class="n">cl</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">==</span><span class="n">cs</span><span class="p">[</span><span class="n">j</span><span class="p">])</span> <span class="n">pint</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">pint</span><span class="p">[</span><span class="n">j</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span><span class="o">+</span><span class="mi">1</span><span class="p">;</span> <span class="cm">/* 如果有更大就更新ret */</span> <span class="k">for</span> <span class="p">(</span><span class="n">j</span><span class="o">=</span><span class="n">ls</span><span class="p">;</span> <span class="n">j</span><span class="o">&gt;</span><span class="n">ret</span><span class="p">;</span> <span class="n">j</span><span class="o">--</span><span class="p">)</span> <span class="k">if</span> <span class="p">(</span><span class="n">pint</span><span class="p">[</span><span class="n">j</span><span class="p">]</span><span class="o">&gt;</span><span class="n">ret</span><span class="p">)</span> <span class="n">ret</span> <span class="o">=</span> <span class="n">pint</span><span class="p">[</span><span class="n">j</span><span class="p">];</span> <span class="p">}</span> <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> <span class="p">}</span> </pre></div> <p>这种算法非常巧妙地化繁为简,有时换一个思路,就会扩然开朗!</p> <p>比较喜欢这种锻炼。</p> <h3 id="_3">参考<a class="headerlink" href="#_3" title="Permanent link">&para;</a></h3> <p>研究了&nbsp;求最长公共子串问题,顺便研究了字符串匹配</p> <p>字符串匹配的Boyer-Moore算法&nbsp;http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html</p> <p>字符串匹配的<span class="caps">KMP</span>算法&nbsp;http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html</p> <p>动态规划算法之:最长公共子序列 <span class="amp">&amp;</span> 最长公共子串(<span class="caps">LCS</span>)&nbsp;http://my.oschina.net/leejun2005/blog/117167</p>