Linux迷+Python粉 - 算法https://blog.pythonwood.com/2020-06-22T00:00:00+08:00面试算法编程选记2题之二分法-寻找斜率为K的2点2020-06-22T00:00:00+08:002020-06-22T00:00:00+08:00pythonwoodtag:blog.pythonwood.com,2020-06-22:/2020/06/面试算法编程选记2题之二分查-寻找斜率为K的2点/<p>因为一直是用自学+坚持自学方法走过来的,折腾技术运用还可以,基础算法编程能力一直偏弱。</p>
<p>1、二分法属于思维简单,细节弄人的典型。之前陷入过二分法脑风暴中不能通透,这次趁面试遇到好好再过一次,提高深度。</p>
<p>2、输入数组A 例如 [(x1,y1),(x2,y2)…],输出斜率为K的点对数目</p>
<h3 id="_1">二分查找<a class="headerlink" href="#_1" title="Permanent link">¶</a></h3>
<p>二分查找要处理好中点 …</p><p>因为一直是用自学+坚持自学方法走过来的,折腾技术运用还可以,基础算法编程能力一直偏弱。</p>
<p>1、二分法属于思维简单,细节弄人的典型。之前陷入过二分法脑风暴中不能通透,这次趁面试遇到好好再过一次,提高深度。</p>
<p>2、输入数组A 例如 [(x1,y1),(x2,y2)…],输出斜率为K的点对数目</p>
<h3 id="_1">二分查找<a class="headerlink" href="#_1" title="Permanent link">¶</a></h3>
<p>二分查找要处理好中点,缩小方法,避免死循环。重在细节实现。 Plus增强后支持最左最右查找</p>
<p>已过 leetcode算法题:<a href="https://www.nowcoder.com/questionTerminal/28d5a9b7fc0b4a078c9a6d59830fb9b9">https://www.nowcoder.com/questionTerminal/28d5a9b7fc0b4a078c9a6d59830fb9b9</a></p>
<div class="highlight"><pre><span></span><span class="s s-Atom">class</span> <span class="nv">BinarySearch</span><span class="s s-Atom">:</span>
<span class="s s-Atom">def</span> <span class="nf">getPos</span><span class="p">(</span><span class="s s-Atom">self</span><span class="p">,</span> <span class="nv">A</span><span class="p">,</span> <span class="s s-Atom">n</span><span class="p">,</span> <span class="s s-Atom">val</span><span class="p">)</span><span class="s s-Atom">:</span>
<span class="s s-Atom">a1</span><span class="p">,</span> <span class="s s-Atom">a2</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="s s-Atom">n</span><span class="o">-</span><span class="mi">1</span> <span class="s s-Atom">#</span> <span class="s s-Atom">a1</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="s s-Atom">a2</span> <span class="o">=</span> <span class="s s-Atom">n</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span>
<span class="s s-Atom">while</span> <span class="s s-Atom">a1</span> <span class="s s-Atom"><=</span> <span class="s s-Atom">a2:</span> <span class="s s-Atom">#</span> <span class="s s-Atom">a1</span><span class="p">,</span> <span class="s s-Atom">a2</span> <span class="s s-Atom">位置未检</span>
<span class="s s-Atom">mid</span> <span class="o">=</span> <span class="p">(</span><span class="s s-Atom">a1</span><span class="o">+</span><span class="s s-Atom">a2</span><span class="p">)</span><span class="o">//</span><span class="mi">2</span> <span class="s s-Atom">#</span> <span class="s s-Atom">中间索引赋值是关键,可等左,不等右</span>
<span class="s s-Atom">#</span> <span class="nf">print</span><span class="p">(</span><span class="s s-Atom">val</span><span class="p">,</span> <span class="nv">A</span><span class="p">,</span> <span class="s s-Atom">a1</span><span class="p">,</span> <span class="s s-Atom">a2</span><span class="p">,</span> <span class="s s-Atom">mid</span><span class="p">)</span>
<span class="s s-Atom">if</span> <span class="nv">A</span><span class="p">[</span><span class="s s-Atom">mid</span><span class="p">]</span> <span class="o">==</span> <span class="nn">val</span><span class="p">:</span>
<span class="s s-Atom">return</span> <span class="s s-Atom">mid</span>
<span class="s s-Atom">elif</span> <span class="nv">A</span><span class="p">[</span><span class="s s-Atom">mid</span><span class="p">]</span> <span class="o"><</span> <span class="nn">val</span><span class="p">:</span>
<span class="s s-Atom">#</span> <span class="nf">print</span><span class="p">(</span><span class="nv">A</span><span class="p">,</span> <span class="s s-Atom">a1</span><span class="p">,</span> <span class="s s-Atom">a2</span><span class="p">,</span> <span class="s s-Atom">mid</span><span class="p">)</span>
<span class="s s-Atom">a1</span> <span class="o">=</span> <span class="s s-Atom">mid</span> <span class="o">+</span> <span class="mi">1</span>
<span class="s s-Atom">#</span> <span class="nf">print</span><span class="p">(</span><span class="nv">A</span><span class="p">,</span> <span class="s s-Atom">a1</span><span class="p">,</span> <span class="s s-Atom">a2</span><span class="p">,</span> <span class="s s-Atom">mid</span><span class="p">)</span>
<span class="nn">else</span><span class="p">:</span>
<span class="s s-Atom">a2</span> <span class="o">=</span> <span class="s s-Atom">mid</span> <span class="o">-</span> <span class="mi">1</span>
<span class="nn">else</span><span class="p">:</span>
<span class="s s-Atom">return</span> <span class="o">-</span><span class="mi">1</span>
<span class="s s-Atom">def</span> <span class="nf">getPosPlus</span><span class="p">(</span><span class="s s-Atom">self</span><span class="p">,</span> <span class="nv">A</span><span class="p">,</span> <span class="s s-Atom">n</span><span class="p">,</span> <span class="s s-Atom">val</span><span class="p">,</span> <span class="s s-Atom">searchtype</span><span class="o">=</span><span class="mi">0</span><span class="p">)</span><span class="s s-Atom">:</span>
<span class="s s-Atom">'''支持最左,最右二分查找的修改Plus版本</span>
<span class="s s-Atom"> 'left':-1, 'fast':0, 'right':1 其中0是默认版本,找到即返回。</span>
<span class="s s-Atom"> '''</span>
<span class="s s-Atom">a1</span><span class="p">,</span> <span class="s s-Atom">a2</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="s s-Atom">n</span><span class="o">-</span><span class="mi">1</span>
<span class="s s-Atom">while</span> <span class="s s-Atom">a1</span> <span class="o"><</span> <span class="s s-Atom">a2:</span> <span class="s s-Atom">#</span> <span class="s s-Atom">直到重合时,单元素</span>
<span class="s s-Atom">mid</span> <span class="o">=</span> <span class="p">(</span><span class="s s-Atom">a1</span><span class="o">+</span><span class="s s-Atom">a2</span><span class="p">)</span><span class="o">//</span><span class="mi">2</span> <span class="s s-Atom">#</span> <span class="s s-Atom">中间索引赋值是关键,可等左,不等右</span>
<span class="s s-Atom">#</span> <span class="nf">print</span><span class="p">(</span><span class="s s-Atom">val</span><span class="p">,</span> <span class="nv">A</span><span class="p">,</span> <span class="s s-Atom">a1</span><span class="p">,</span> <span class="s s-Atom">a2</span><span class="p">,</span> <span class="s s-Atom">mid</span><span class="p">)</span>
<span class="s s-Atom">if</span> <span class="nv">A</span><span class="p">[</span><span class="s s-Atom">mid</span><span class="p">]</span> <span class="o">==</span> <span class="nn">val</span><span class="p">:</span>
<span class="s s-Atom">if</span> <span class="s s-Atom">searchtype</span> <span class="o">==</span> <span class="mi">0</span><span class="s s-Atom">:</span>
<span class="s s-Atom">return</span> <span class="s s-Atom">mid</span>
<span class="s s-Atom">if</span> <span class="s s-Atom">searchtype</span> <span class="o">==</span> <span class="o">-</span><span class="mi">1</span><span class="s s-Atom">:</span>
<span class="s s-Atom">a2</span> <span class="o">=</span> <span class="s s-Atom">mid</span>
<span class="s s-Atom">elif</span> <span class="s s-Atom">searchtype</span> <span class="o">==</span> <span class="mi">1</span><span class="s s-Atom">:</span>
<span class="s s-Atom">a1</span> <span class="o">=</span> <span class="s s-Atom">mid</span>
<span class="s s-Atom">elif</span> <span class="nv">A</span><span class="p">[</span><span class="s s-Atom">mid</span><span class="p">]</span> <span class="o"><</span> <span class="nn">val</span><span class="p">:</span>
<span class="s s-Atom">#</span> <span class="nf">print</span><span class="p">(</span><span class="nv">A</span><span class="p">,</span> <span class="s s-Atom">a1</span><span class="p">,</span> <span class="s s-Atom">a2</span><span class="p">,</span> <span class="s s-Atom">mid</span><span class="p">)</span>
<span class="s s-Atom">a1</span> <span class="o">=</span> <span class="s s-Atom">mid</span>
<span class="s s-Atom">if</span> <span class="s s-Atom">a1</span> <span class="o">+</span> <span class="mi">1</span> <span class="o">==</span> <span class="s s-Atom">a2:</span> <span class="s s-Atom">#</span> <span class="s s-Atom">避免剩余2个元素时,</span> <span class="s s-Atom">mid=左陷入死循环</span>
<span class="s s-Atom">a1</span> <span class="o">=</span> <span class="s s-Atom">a2</span>
<span class="s s-Atom">#</span> <span class="nf">print</span><span class="p">(</span><span class="nv">A</span><span class="p">,</span> <span class="s s-Atom">a1</span><span class="p">,</span> <span class="s s-Atom">a2</span><span class="p">,</span> <span class="s s-Atom">mid</span><span class="p">)</span>
<span class="nn">else</span><span class="p">:</span>
<span class="s s-Atom">a2</span> <span class="o">=</span> <span class="s s-Atom">mid</span>
<span class="nn">else</span><span class="p">:</span>
<span class="s s-Atom">assert</span> <span class="s s-Atom">a1</span> <span class="o">==</span> <span class="s s-Atom">a2</span>
<span class="s s-Atom">return</span> <span class="s s-Atom">a1</span> <span class="s s-Atom">if</span> <span class="nv">A</span><span class="p">[</span><span class="s s-Atom">a1</span><span class="p">]</span> <span class="o">==</span> <span class="s s-Atom">val</span> <span class="s s-Atom">else</span> <span class="o">-</span><span class="mi">1</span>
<span class="s s-Atom">if</span> <span class="k">__</span><span class="s s-Atom">name__</span> <span class="o">==</span> <span class="s s-Atom">'__main__':</span>
<span class="s s-Atom">rt</span> <span class="o">=</span> <span class="nv">BinarySearch</span><span class="p">()</span>
<span class="s s-Atom">for</span> <span class="nv">A</span> <span class="nf">in</span> <span class="p">((</span><span class="mi">1</span><span class="p">,),</span> <span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="mi">5</span><span class="p">),</span> <span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">5</span><span class="p">,</span> <span class="mi">9</span><span class="p">),</span> <span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">5</span><span class="p">),</span> <span class="p">[</span><span class="mi">4</span><span class="p">,</span><span class="mi">4</span><span class="p">,</span><span class="mi">10</span><span class="p">,</span><span class="mi">21</span><span class="p">])</span><span class="s s-Atom">:</span>
<span class="s s-Atom">n</span> <span class="o">=</span> <span class="nf">len</span><span class="p">(</span><span class="nv">A</span><span class="p">)</span>
<span class="s s-Atom">for</span> <span class="s s-Atom">val</span> <span class="s s-Atom">in</span> <span class="nv">A</span><span class="s s-Atom">:</span>
<span class="s s-Atom">#</span> <span class="s s-Atom">idx</span> <span class="o">=</span> <span class="s s-Atom">rt</span><span class="p">.</span><span class="nf">getPos</span><span class="p">(</span><span class="nv">A</span><span class="p">,</span> <span class="s s-Atom">n</span><span class="p">,</span> <span class="s s-Atom">val</span><span class="p">)</span>
<span class="s s-Atom">#</span> <span class="nf">print</span><span class="p">(</span><span class="s s-Atom">'find %3s in %10s: index=%s'</span> <span class="c1">% (val, A, idx))</span>
<span class="s s-Atom">#</span> <span class="s s-Atom">支持最左,最右二分查找的修改Plus版本</span>
<span class="s s-Atom">idx</span> <span class="o">=</span> <span class="s s-Atom">rt</span><span class="p">.</span><span class="nf">getPosPlus</span><span class="p">(</span><span class="nv">A</span><span class="p">,</span> <span class="s s-Atom">n</span><span class="p">,</span> <span class="s s-Atom">val</span><span class="p">)</span>
<span class="nf">print</span><span class="p">(</span><span class="s s-Atom">'find %3s in %10s: index=%s'</span> <span class="c1">% (val, A, idx))</span>
<span class="s s-Atom">idx</span> <span class="o">=</span> <span class="s s-Atom">rt</span><span class="p">.</span><span class="nf">getPosPlus</span><span class="p">(</span><span class="nv">A</span><span class="p">,</span> <span class="s s-Atom">n</span><span class="p">,</span> <span class="s s-Atom">val</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">)</span>
<span class="nf">print</span><span class="p">(</span><span class="s s-Atom">'find %3s in %10s: index=%s'</span> <span class="c1">% (val, A, idx))</span>
</pre></div>
<h3 id="k">寻找斜率为K的点对<a class="headerlink" href="#k" title="Permanent link">¶</a></h3>
<p>算法题:</p>
<p>有一个数组,数组每个元素是一个对象,每个对象有x和y两个值,这个数组记录 为A: A = [{x1, y1}, {x2, y2}, …];我们把数组A中任意两个满足以下关系的元素叫 做“点对”:(y2-y1)/(x2-x1) = K, K是一个常数。编写程序:给定A与K,返回A中点 对的数目。</p>
<div class="highlight"><pre><span></span><span class="kn">from</span> <span class="nn">itertools</span> <span class="kn">import</span> <span class="n">groupby</span>
<span class="n">K</span> <span class="o">=</span> <span class="mi">1</span> <span class="c1"># 斜率</span>
<span class="k">def</span> <span class="nf">kpairs</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">k</span><span class="o">=</span><span class="n">K</span><span class="p">):</span>
<span class="sd">'''</span>
<span class="sd"> 分析:计算一遍点到直线y=kx距离 |Kx - y| / √(k*k+1),距离等两点的可能与y=kx平行。先验证y=kx上的,距离等不一定平行。</span>
<span class="sd"> 技巧:结合题目实际,可不开平方pow运算,不取绝对值。</span>
<span class="sd"> '''</span>
<span class="k">print</span><span class="p">(</span><span class="s1">'debug: kpairs(</span><span class="si">%s</span><span class="s1">, </span><span class="si">%s</span><span class="s1">)'</span> <span class="o">%</span> <span class="p">(</span><span class="n">k</span><span class="p">,</span> <span class="n">A</span><span class="p">))</span>
<span class="n">result</span> <span class="o">=</span> <span class="mi">0</span>
<span class="n">distance</span> <span class="o">=</span> <span class="p">[</span> <span class="p">(</span><span class="n">k</span><span class="o">*</span><span class="n">x</span><span class="o">-</span><span class="n">y</span><span class="p">)</span> <span class="o">/</span> <span class="p">(</span><span class="n">k</span><span class="o">**</span><span class="mi">2</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span> <span class="k">for</span> <span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">)</span> <span class="ow">in</span> <span class="n">A</span> <span class="p">]</span>
<span class="n">point_distance</span> <span class="o">=</span> <span class="nb">sorted</span><span class="p">(</span><span class="nb">zip</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">distance</span><span class="p">),</span> <span class="n">key</span><span class="o">=</span><span class="k">lambda</span> <span class="n">x</span><span class="p">:</span> <span class="n">x</span><span class="p">[</span><span class="mi">1</span><span class="p">])</span> <span class="c1"># 距离排序,取点</span>
<span class="k">for</span> <span class="n">distance</span><span class="p">,</span> <span class="n">pointiter</span> <span class="ow">in</span> <span class="n">groupby</span><span class="p">(</span><span class="n">point_distance</span><span class="p">,</span> <span class="n">key</span><span class="o">=</span><span class="k">lambda</span> <span class="n">x</span><span class="p">:</span> <span class="n">x</span><span class="p">[</span><span class="mi">1</span><span class="p">]):</span>
<span class="n">points</span> <span class="o">=</span> <span class="nb">list</span><span class="p">(</span><span class="n">x</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">pointiter</span><span class="p">)</span>
<span class="n">count</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">points</span><span class="p">)</span>
<span class="k">print</span><span class="p">(</span><span class="s1">'debug: line:y=</span><span class="si">%3s</span><span class="s1">x, got </span><span class="si">%3s</span><span class="s1"> point distance=</span><span class="si">%7.3s</span><span class="s1">: </span><span class="si">%s</span><span class="s1">'</span> <span class="o">%</span> <span class="p">(</span><span class="n">k</span><span class="p">,</span> <span class="n">count</span><span class="p">,</span> <span class="n">distance</span><span class="p">,</span> <span class="n">points</span><span class="p">))</span> <span class="c1"># debug</span>
<span class="k">if</span> <span class="n">count</span> <span class="o">></span> <span class="mi">1</span><span class="p">:</span>
<span class="n">result</span> <span class="o">+=</span> <span class="n">count</span><span class="o">*</span><span class="p">(</span><span class="n">count</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span><span class="o">/</span><span class="mi">2</span> <span class="c1"># 组合数 4 -> 6</span>
<span class="k">return</span> <span class="n">result</span>
<span class="k">if</span> <span class="vm">__name__</span> <span class="o">==</span> <span class="s1">'__main__'</span><span class="p">:</span>
<span class="n">A</span> <span class="o">=</span> <span class="p">[(</span><span class="mi">0</span><span class="p">,</span><span class="mi">3</span><span class="p">),</span> <span class="p">(</span><span class="mi">3</span><span class="p">,</span><span class="mi">0</span><span class="p">),</span> <span class="p">(</span><span class="mi">3</span><span class="p">,</span><span class="mi">3</span><span class="p">),</span> <span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">)]</span> <span class="c1"># 正方形</span>
<span class="k">assert</span> <span class="n">kpairs</span><span class="p">(</span><span class="n">A</span><span class="p">)</span> <span class="o">==</span> <span class="mi">1</span><span class="p">,</span> <span class="s1">'check and debug kpairs(</span><span class="si">%s</span><span class="s1">)'</span><span class="o">%</span><span class="n">A</span>
<span class="k">assert</span> <span class="n">kpairs</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="mi">10</span><span class="p">)</span> <span class="o">==</span> <span class="mi">0</span><span class="p">,</span> <span class="s1">'check and debug kpairs(</span><span class="si">%s</span><span class="s1">)'</span><span class="o">%</span><span class="n">A</span>
<span class="n">A</span> <span class="o">=</span> <span class="p">[(</span><span class="mi">3</span><span class="p">,</span><span class="mi">9</span><span class="p">),</span> <span class="p">(</span><span class="mi">9</span><span class="p">,</span><span class="mi">9</span><span class="p">),</span> <span class="p">(</span><span class="mi">20</span><span class="p">,</span><span class="mi">20</span><span class="p">),</span> <span class="p">(</span><span class="mi">10</span><span class="p">,</span><span class="mi">16</span><span class="p">),</span> <span class="p">(</span><span class="mi">22</span><span class="p">,</span><span class="mi">28</span><span class="p">)]</span>
<span class="k">assert</span> <span class="n">kpairs</span><span class="p">(</span><span class="n">A</span><span class="p">)</span> <span class="o">==</span> <span class="mi">4</span><span class="p">,</span> <span class="s1">'check and debug kpairs(</span><span class="si">%s</span><span class="s1">)'</span><span class="o">%</span><span class="n">A</span>
<span class="k">assert</span> <span class="n">kpairs</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="mi">4</span><span class="p">)</span> <span class="o">==</span> <span class="mi">1</span><span class="p">,</span> <span class="s1">'check and debug kpairs(</span><span class="si">%s</span><span class="s1">)'</span><span class="o">%</span><span class="n">A</span>
</pre></div>
<h2 id="_2">参考<a class="headerlink" href="#_2" title="Permanent link">¶</a></h2>
<ol>
<li>点到直线距离公式的几种推导 <a href="https://zhuanlan.zhihu.com/p/26307123">https://zhuanlan.zhihu.com/p/26307123</a></li>
</ol>RSA原理:欧几里德算法与奥数内容辗转相除法——挑战PythonTip2017-12-17T23:00:00+08:002017-12-17T23:00:00+08:00pythonwoodtag:blog.pythonwood.com,2017-12-17:/2017/12/RSA原理:欧几里德算法与奥数内容辗转相除法——挑战PythonTip/<p><a href="http://www.pythontip.com" title="PythonTip">PythonTip</a> 里未攻克的题目,如<a href="http://www.pythontip.com/coding/code_oj_case/46" title="RSA密码方程"><span class="caps">RSA</span>密码方程</a>,如今积累工作经验之后从新挑战,仍然失败未成功了。把过程记录分享下。</p>
<h3 id="_1">描述:<a class="headerlink" href="#_1" title="Permanent link">¶</a></h3>
<p>在<span class="caps">RSA</span>密码体系中,欧几里得算法是加密或解密运算的重要组成部分。它的基本运算过程就是解 (x*a) % n = 1 这种方程。
其中 …</p><p><a href="http://www.pythontip.com" title="PythonTip">PythonTip</a> 里未攻克的题目,如<a href="http://www.pythontip.com/coding/code_oj_case/46" title="RSA密码方程"><span class="caps">RSA</span>密码方程</a>,如今积累工作经验之后从新挑战,仍然失败未成功了。把过程记录分享下。</p>
<h3 id="_1">描述:<a class="headerlink" href="#_1" title="Permanent link">¶</a></h3>
<p>在<span class="caps">RSA</span>密码体系中,欧几里得算法是加密或解密运算的重要组成部分。它的基本运算过程就是解 (x*a) % n = 1 这种方程。
其中,x,a,n皆为正整数。现在给你a和n的值(1 < a,n < 140000000),请你求出最小的满足方程的正整数解x(保证有解).
如:a = 1001, n = 3837,则输出23。</p>
<h3 id="_2">分析:<a class="headerlink" href="#_2" title="Permanent link">¶</a></h3>
<p>没头绪,在讨论里看时恍然,用到小学奥术内容辗转相除法(求最大公约数)了。如果 <code>(x*a) % n = 1</code> 变成 <code>(x*a) % n = 0</code> , 那x*a就是a和n公倍数了。如果这是小学奥数题,就先用辗转相除法得最大公约数,而最小公倍数用两数积除以最大公约数得出来。 rsa的原理数学基础欧几里得算法和小学奥数有着这样的联系,发现这点让我觉得不可思议又略有惊叹。看来学小学奥数有用,至少是可以为算法编程做准备的,学到了最朴素的数论。</p>
<h4 id="_3">辗转相除法(朴素欧几里得算法,中国余数定理,韩信点兵)<a class="headerlink" href="#_3" title="Permanent link">¶</a></h4>
<p>(引用自 <a href="https://xuanwo.org/2015/03/11/number-theory-gcd/," title="数论——欧几里得算法">数论——欧几里得算法</a>)</p>
<p>欧几里得算法,又名辗转相除法,是求最大公约数的算法。两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理:两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如,252和105的最大公约数是21(252 = 21 × 12;105 = 21 × 5);因为252 − 105 = 147,所以147和105的最大公约数也是21。在这个过程中,较大的数缩小了,所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时,所剩下的还没有变成零的数就是两数的最大公约数。 </p>
<p><img alt="辗转相除法演示图.gif" src="https://blog.pythonwood.com/uploads/2017/挑战PythonTip,辗转相除法演示图.gif"></p>
<h4 id="_4">题目语义转化<a class="headerlink" href="#_4" title="Permanent link">¶</a></h4>
<p>求这样一个数x*a,能被a整除,被n整除余1。 </p>
<p>这就很形似 <em>有一个数除以3余2,除以5余3,除以7余4,除以9余5.这个数至少是?</em> 被称为<a href="https://zh.wikipedia.org/wiki/中国余数定理," title="中国余数定理">中国余数定理</a></p>
<h4 id="_5">扩展欧几里德算法<a class="headerlink" href="#_5" title="Permanent link">¶</a></h4>
<p>基本算法:对于不完全为 0 的非负整数 a,b,gcd(a,b)表示 a,b 的最大公约数,必然存在整数对 x,y ,使得 gcd(a,b)=ax+by。</p>
<p>证明:设 a>b。</p>
<p>1,显然当 b=0,gcd(a,b)=a。此时 x=1,y=0;</p>
<p>2,ab!=0 时</p>
<p>设 ax1+by1=gcd(a,b);</p>
<p>bx2+(a mod b)y2=gcd(b,a mod b);</p>
<p>根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);</p>
<p>则:ax1+by1=bx2+(a mod b)y2;</p>
<p>即:ax1+by1=bx2+(a-(a/b)<em>b)y2=ay2+bx2-(a/b)</em>by2;</p>
<p>根据恒等定理得:x1=y2; y1=x2-(a/b)*y2;</p>
<p>这样我们就得到了求解 x1,y1 的方法:x1,y1 的值基于 x2,y2.</p>
<p>上面的思想是以递归定义的,因为 gcd 不断的递归求解一定会有个时候 b=0,所以递归可以结束。</p>
<p>…</p>
<p>同余方程 ax≡b (mod n)对于未知数 x 有解,当且仅当 gcd(a,n) | b。且方程有解时,方程有 gcd(a,n) 个解。</p>
<p>求解方程 ax≡b (mod n) 相当于求解方程 ax+ ny= b, (x, y为整数)</p>
<h3 id="_6">我的一个另类编程解法(融合了辗转相除法思想)。<a class="headerlink" href="#_6" title="Permanent link">¶</a></h3>
<h4 id="_7">算法描述<a class="headerlink" href="#_7" title="Permanent link">¶</a></h4>
<p>(x*a) % n = 1 对应 方程 ax - ny = 1 的整数解 </p>
<p>(a,n必定互质。如不互质可提取公因子,公因子*X=1,与X为整数矛盾)</p>
<p>化简降解方程分两情况:</p>
<ol>
<li>a>=n 时 变形为方程 (a mod n)x - n(y-[a/n]x) = 1 有整数解 </li>
<li>a<n 时 变形为方程 a(x-[n/a]a) - (n mod a)y = 1 有整数解</li>
</ol>
<p>无论那一种都变回 ax - ny = 1 的形式。所以重复化简,因a,n互质,最后会到达a,n其一是1的情况。</p>
<h4 id="971">例子说明: 求能被9整除,被7除余1的最小数<a class="headerlink" href="#971" title="Permanent link">¶</a></h4>
<ol>
<li>9x=1(mod7) 对应方程 9x - 7y = 1 的整数解</li>
<li>变形有2x - 7(y-x) = 1 然后令 x_1=x, y_1=y-x 得方程 2x_1 - 7y_1 = 1 </li>
<li>变形有2(x_1-3y_1) - y_1 = 1 然后令 x_2=x_1-3y_1, y_2=y_1 得方程 2x_2 - y_2 = 1 显然有解 x_2=1 y_2=1 </li>
<li>好了,往上一步一步回溯得最初的x,y值 (x_2,y_2), (x_1,y_1), (x,y) 分别为(1,1),(4,1),(4,5)</li>
<li>9x = (9<em>4 mod 9</em>7) = 36 答:求能被9整除,被7除余1的数是36</li>
</ol>
<p>python语言是弱递归化语言, python之父说递归都可以转成循环。所以我用递归后,转循环了。</p>
<h3 id="python">Python代码:<a class="headerlink" href="#python" title="Permanent link">¶</a></h3>
<div class="highlight"><pre><span></span><span class="c1">################################################################################</span>
<span class="c1"># print "F: 答案错误 循环解法"</span>
<span class="c1">################################################################################</span>
<span class="s s-Atom">def</span> <span class="nf">gcd</span><span class="p">(</span><span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span><span class="p">)</span><span class="s s-Atom">:</span> <span class="s s-Atom">#</span> <span class="s s-Atom">辗转相除求最大公约数</span>
<span class="s s-Atom">if</span> <span class="s s-Atom">a</span> <span class="o"><</span> <span class="nn">n</span><span class="p">:</span> <span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span> <span class="o">=</span> <span class="s s-Atom">n</span><span class="p">,</span><span class="s s-Atom">a</span>
<span class="s s-Atom">while</span> <span class="s s-Atom">n</span> <span class="p">!</span><span class="o">=</span> <span class="mi">0</span><span class="s s-Atom">:</span> <span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span> <span class="o">=</span> <span class="s s-Atom">n</span><span class="p">,</span><span class="s s-Atom">a</span><span class="c1">%n</span>
<span class="s s-Atom">return</span> <span class="s s-Atom">a</span>
<span class="s s-Atom">def</span> <span class="nf">exgcd</span><span class="p">(</span><span class="s s-Atom">a</span><span class="p">,</span> <span class="s s-Atom">n</span><span class="p">)</span><span class="s s-Atom">:</span> <span class="s s-Atom">#</span> <span class="s s-Atom">ax</span><span class="o">=</span><span class="mi">1</span><span class="p">(</span><span class="o">mod</span> <span class="s s-Atom">n</span><span class="p">)</span> <span class="s s-Atom">即</span> <span class="s s-Atom">ax</span><span class="o">-</span><span class="s s-Atom">ny</span><span class="o">=</span><span class="mi">1</span> <span class="s s-Atom">求x</span><span class="p">,</span><span class="s s-Atom">y</span>
<span class="s s-Atom">#</span> <span class="s s-Atom">print</span> <span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span>
<span class="s s-Atom">if</span> <span class="nf">gcd</span><span class="p">(</span><span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span><span class="p">)</span> <span class="p">!</span><span class="o">=</span> <span class="mi">1</span><span class="s s-Atom">:</span> <span class="s s-Atom">raise</span> <span class="nv">Exception</span><span class="p">(</span><span class="s s-Atom">'fei hu zhi'</span><span class="p">)</span> <span class="s s-Atom">#</span> <span class="s s-Atom">先检查是否互质</span>
<span class="s s-Atom">l</span> <span class="o">=</span> <span class="p">[]</span>
<span class="s s-Atom">while</span> <span class="s s-Atom">a</span><span class="p">!</span><span class="o">=</span><span class="mi">1</span> <span class="s s-Atom">and</span> <span class="s s-Atom">n</span><span class="p">!</span><span class="o">=</span><span class="mi">1</span><span class="s s-Atom">:</span> <span class="s s-Atom">#</span> <span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n总会有个先到1,触底条件就是1</span>
<span class="s s-Atom">l</span><span class="p">.</span><span class="nf">append</span><span class="p">((</span><span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span><span class="p">))</span>
<span class="s s-Atom">if</span> <span class="s s-Atom">a</span><span class="o">></span><span class="nn">n</span><span class="p">:</span> <span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span> <span class="o">=</span> <span class="s s-Atom">a</span><span class="c1">%n,n</span>
<span class="nn">else</span><span class="p">:</span> <span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span> <span class="o">=</span> <span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span><span class="c1">%a</span>
<span class="s s-Atom">if</span> <span class="s s-Atom">a</span><span class="o">==</span><span class="mi">1</span><span class="s s-Atom">:</span> <span class="s s-Atom">p</span> <span class="o">=</span> <span class="p">(</span><span class="s s-Atom">n</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">)</span>
<span class="s s-Atom">elif</span> <span class="s s-Atom">n</span><span class="o">==</span><span class="mi">1</span><span class="s s-Atom">:</span> <span class="s s-Atom">p</span> <span class="o">=</span> <span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="s s-Atom">a</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span>
<span class="s s-Atom">for</span> <span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span> <span class="s s-Atom">in</span> <span class="s s-Atom">l</span><span class="p">[</span><span class="s s-Atom">::-</span><span class="mi">1</span><span class="p">]</span><span class="s s-Atom">:</span>
<span class="s s-Atom">if</span> <span class="s s-Atom">a</span><span class="o">></span><span class="nn">n</span><span class="p">:</span> <span class="s s-Atom">p</span> <span class="o">=</span> <span class="p">(</span><span class="s s-Atom">p</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="c1">% n, (a//n*p[0]+p[1]) % a) # 这个值也是解,但没有最简:return (p[0], a//n*p[0]+p[1])</span>
<span class="nn">else</span><span class="p">:</span> <span class="s s-Atom">p</span> <span class="o">=</span> <span class="p">((</span><span class="s s-Atom">p</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">+</span><span class="s s-Atom">n</span><span class="o">//</span><span class="s s-Atom">a</span><span class="o">*</span><span class="s s-Atom">p</span><span class="p">[</span><span class="mi">1</span><span class="p">])</span> <span class="c1">% n, p[1] % a) # 这个值也是解,但没有最简:return (p[0]+n//a*p[1], p[1])</span>
<span class="s s-Atom">return</span> <span class="s s-Atom">p</span>
<span class="s s-Atom">print</span> <span class="nf">exgcd</span><span class="p">(</span><span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span><span class="p">)</span>
<span class="c1">################################################################################</span>
<span class="c1"># print "F: 答案错误 递归解法"</span>
<span class="c1">################################################################################</span>
<span class="s s-Atom">def</span> <span class="nf">gcd_r</span><span class="p">(</span><span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span><span class="p">)</span><span class="s s-Atom">:</span> <span class="s s-Atom">#</span> <span class="s s-Atom">辗转相除求最大公约数</span>
<span class="s s-Atom">if</span> <span class="s s-Atom">a</span> <span class="o">*</span> <span class="s s-Atom">n</span> <span class="o">==</span> <span class="mi">0</span><span class="s s-Atom">:</span> <span class="s s-Atom">return</span> <span class="s s-Atom">a</span><span class="o">+</span><span class="s s-Atom">n</span>
<span class="s s-Atom">return</span> <span class="nf">gcd_r</span><span class="p">(</span><span class="s s-Atom">a</span><span class="c1">%n,n) if a>=n else gcd_r(a,n%a)</span>
<span class="c1"># print gcd(a,n)</span>
<span class="s s-Atom">def</span> <span class="nf">exgcd_r</span><span class="p">(</span><span class="s s-Atom">a</span><span class="p">,</span> <span class="s s-Atom">n</span><span class="p">)</span><span class="s s-Atom">:</span> <span class="s s-Atom">#</span> <span class="s s-Atom">ax</span><span class="o">=</span><span class="mi">1</span><span class="p">(</span><span class="o">mod</span> <span class="s s-Atom">n</span><span class="p">)</span> <span class="s s-Atom">即</span> <span class="s s-Atom">ax</span><span class="o">-</span><span class="s s-Atom">ny</span><span class="o">=</span><span class="mi">1</span> <span class="s s-Atom">求x</span><span class="p">,</span><span class="s s-Atom">y</span> <span class="s s-Atom">#</span> <span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n总会有个先到1,触底条件就是1</span>
<span class="s s-Atom">#</span> <span class="s s-Atom">print</span> <span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span>
<span class="s s-Atom">if</span> <span class="nf">gcd_r</span><span class="p">(</span><span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span><span class="p">)</span> <span class="p">!</span><span class="o">=</span> <span class="mi">1</span><span class="s s-Atom">:</span> <span class="s s-Atom">raise</span> <span class="nv">Exception</span><span class="p">(</span><span class="s s-Atom">'fei hu zhi'</span><span class="p">)</span> <span class="s s-Atom">#</span> <span class="s s-Atom">先检查是否互质</span>
<span class="s s-Atom">if</span> <span class="s s-Atom">a</span><span class="o">==</span><span class="mi">1</span><span class="s s-Atom">:</span> <span class="nf">return</span> <span class="p">(</span><span class="s s-Atom">n</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">)</span>
<span class="s s-Atom">if</span> <span class="s s-Atom">n</span><span class="o">==</span><span class="mi">1</span><span class="s s-Atom">:</span> <span class="nf">return</span> <span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="s s-Atom">a</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span>
<span class="s s-Atom">if</span> <span class="s s-Atom">a</span><span class="o">></span><span class="nn">n</span><span class="p">:</span>
<span class="s s-Atom">p</span> <span class="o">=</span> <span class="nf">exgcd_r</span><span class="p">(</span><span class="s s-Atom">a</span><span class="c1">%n, n)</span>
<span class="nf">return</span> <span class="p">(</span><span class="s s-Atom">p</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="c1">% n, (a//n*p[0]+p[1]) % a) # 这个值也是解,但没有最简:return (p[0], a//n*p[0]+p[1])</span>
<span class="nn">else</span><span class="p">:</span>
<span class="s s-Atom">p</span> <span class="o">=</span> <span class="nf">exgcd_r</span><span class="p">(</span><span class="s s-Atom">a</span><span class="p">,</span> <span class="s s-Atom">n</span><span class="c1">%a) </span>
<span class="nf">return</span> <span class="p">((</span><span class="s s-Atom">p</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">+</span><span class="s s-Atom">n</span><span class="o">//</span><span class="s s-Atom">a</span><span class="o">*</span><span class="s s-Atom">p</span><span class="p">[</span><span class="mi">1</span><span class="p">])</span> <span class="c1">% n, p[1] % a) # 这个值也是解,但没有最简:return (p[0]+n//a*p[1], p[1])</span>
<span class="s s-Atom">print</span> <span class="nf">exgcd_r</span><span class="p">(</span><span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span><span class="p">)</span>
</pre></div>
<p>小学初中就知道数论,数论真有魅力,非常漂亮。</p>
<h3 id="_8">参考<a class="headerlink" href="#_8" title="Permanent link">¶</a></h3>
<p>数论——欧几里得算法 https://xuanwo.org/2015/03/11/number-theory-gcd/</p>
<p>欧几里德与扩展欧几里德算法 http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html</p>
<p>欧几里得算法(辗转相除法) https://my.oschina.net/u/1780798/blog/646739</p>
<p>https://zhidao.baidu.com/question/406531667.html?qbl=relate_question_3</p>威佐夫博弈:取石子游戏算法——挑战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">¶</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">¶</a></h3>
<p>有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,
一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。
现在给出初始的两堆石子的数目a和b,如果轮到你先取,假设双方都采取最好的策略,问最后你是胜者还是败者。
如果你是胜者,输出Win,否则输出Loose。
例如,a=3,b=1, 则输出Win(你先在a中取一个,此时a=2,b=1,此时无论对方怎么取,你都能将所有石子都拿走).</p>
<h3 id="_2">分析(动态规划):<a class="headerlink" href="#_2" title="Permanent link">¶</a></h3>
<p>我的思路是转变成图形化表示,二维表中点(x,y)用W表示会赢,L表示为输。</p>
<p>(x,y)的结果显然决定与前面已填好的(m,n) , 其中m,n 分别小于 x,y 。 所以可以用动态规划。 根据之前失败坐标的集合推算本行的失败坐标。</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">¶</a></h4>
<p><img alt="错误填表图1" src="https://blog.pythonwood.com/uploads/2017/挑战PythonTip,威佐夫博弈:取石子游戏错误填表图1.png"></p>
<p><img alt="错误填表图2" src="https://blog.pythonwood.com/uploads/2017/挑战PythonTip,威佐夫博弈:取石子游戏错误填表图2.png"></p>
<p><img alt="错误填表图3" src="https://blog.pythonwood.com/uploads/2017/挑战PythonTip,威佐夫博弈:取石子游戏错误填表图3.png"></p>
<p>我根据这个过程写出版本一代码。</p>
<h4 id="_4">正确填表分析过程<a class="headerlink" href="#_4" title="Permanent link">¶</a></h4>
<p><img alt="正确填表图1" src="https://blog.pythonwood.com/uploads/2017/挑战PythonTip,威佐夫博弈:取石子游戏正确填表图1.png"></p>
<p><img alt="正确填表图2" src="https://blog.pythonwood.com/uploads/2017/挑战PythonTip,威佐夫博弈:取石子游戏正确填表图2.png"></p>
<p><img alt="正确填表图3" src="https://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">¶</a></h3>
<div class="highlight"><pre><span></span>################################################################################
# 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"
</pre></div>Python解无穷大数除法算法——挑战PythonTip2017-12-15T16:30:00+08:002017-12-15T16:30:00+08:00pythonwoodtag:blog.pythonwood.com,2017-12-15:/2017/12/Python解无穷大数除法算法——挑战PythonTip/<p><a href="http://www.pythontip.com" title="PythonTip">PythonTip</a>提供了一个不错的学习算法平台,大学毕业前挑战进入了前几名<a href="http://www.pythontip.com/coding/userAcList/624" title="pythonwood解题数量">pythonwood解题数量</a>。</p>
<p>当时有些未攻克的题目,比如密码生成题目,如今积累工作经验之后从新挑战,成功了。把过程记录分享下。</p>
<h3 id="_1">描述:<a class="headerlink" href="#_1" title="Permanent link">¶</a></h3>
<p>生活在当代社会,我们要记住很多密码,银行卡,qq,人人,微博,邮箱等等。小P经过一番思索之后,发明了下面这种生成密码方法:给定两个正整数a和b …</p><p><a href="http://www.pythontip.com" title="PythonTip">PythonTip</a>提供了一个不错的学习算法平台,大学毕业前挑战进入了前几名<a href="http://www.pythontip.com/coding/userAcList/624" title="pythonwood解题数量">pythonwood解题数量</a>。</p>
<p>当时有些未攻克的题目,比如密码生成题目,如今积累工作经验之后从新挑战,成功了。把过程记录分享下。</p>
<h3 id="_1">描述:<a class="headerlink" href="#_1" title="Permanent link">¶</a></h3>
<p>生活在当代社会,我们要记住很多密码,银行卡,qq,人人,微博,邮箱等等。小P经过一番思索之后,发明了下面这种生成密码方法:给定两个正整数a和b, 利用a / b我们会得到一个长度无限的小数(若a / b不是无限小数,比如1/2=0.5,我们认为0.5是0.5000000…,同样将其看做无限长的小数),小P将该小数点后第x位到第y位的数字当做密码,这样,无论密码有多长,小P只要记住a,b,x,y四个数字就可以了,牢记密码再也不是那么困难的事情了。现在告诉你a,b,x,y(0 < a,b <= 20132013, 0 < x <= y < 100000000000),请你输出密码。例如:a = 1, b = 2, x = 1, y = 4, 则 a / b = 0.5000000…, 输出小数点后第1到4位数字,即5000</p>
<h3 id="_2">分析:<a class="headerlink" href="#_2" title="Permanent link">¶</a></h3>
<p>计算机浮点计算有精度问题,所以直接除法得结果的思路不通。这次我想到小学的列竖式除法算法本身是可以解无穷除法的。于是,这道题就是把我们小学早已学过的算法,用代码表示出来。 </p>
<p>下面包含几个算法, 都比较简介,比较pythonic(在网上看到是算法代码普遍臃肿)。只有最后的循环记录法是在规定时间内通过的。</p>
<h3 id="python">Python代码:<a class="headerlink" href="#python" title="Permanent link">¶</a></h3>
<table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80</pre></div></td><td class="code"><div class="highlight"><pre><span></span><span class="ch">#! /usr/bin/env python</span>
<span class="c1">#coding: utf8</span>
<span class="c1"># 返回a除以b的商的小数部分的第x位到第y位</span>
<span class="n">a</span> <span class="o">=</span> <span class="mi">22</span><span class="p">;</span> <span class="n">b</span> <span class="o">=</span> <span class="mi">300003</span><span class="p">;</span> <span class="n">x</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">y</span> <span class="o">=</span> <span class="mi">50</span>
<span class="c1">################################################################################</span>
<span class="k">print</span> <span class="s2">"F: 不能引入sys 模拟手工除法"</span>
<span class="c1">################################################################################</span>
<span class="kn">import</span> <span class="nn">sys</span>
<span class="n">t</span> <span class="o">=</span> <span class="n">a</span> <span class="o">%</span> <span class="n">b</span>
<span class="k">for</span> <span class="n">c</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">y</span><span class="p">):</span>
<span class="n">t</span> <span class="o">*=</span> <span class="mi">10</span>
<span class="k">if</span> <span class="n">c</span><span class="o">+</span><span class="mi">1</span> <span class="o">>=</span> <span class="n">x</span><span class="p">:</span>
<span class="n">sys</span><span class="o">.</span><span class="n">stdout</span><span class="o">.</span><span class="n">write</span><span class="p">(</span> <span class="nb">str</span><span class="p">(</span><span class="n">t</span><span class="o">//</span><span class="n">b</span><span class="p">)</span> <span class="p">)</span>
<span class="n">t</span> <span class="o">%=</span> <span class="n">b</span>
<span class="k">print</span>
<span class="c1">################################################################################</span>
<span class="k">print</span> <span class="s2">"F: 时间复杂度不足 同上"</span>
<span class="c1">################################################################################</span>
<span class="n">code</span> <span class="o">=</span> <span class="s2">""</span>
<span class="n">t</span> <span class="o">=</span> <span class="n">a</span> <span class="o">%</span> <span class="n">b</span>
<span class="k">for</span> <span class="n">c</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">y</span><span class="p">):</span>
<span class="n">t</span> <span class="o">*=</span> <span class="mi">10</span>
<span class="k">if</span> <span class="n">c</span><span class="o">+</span><span class="mi">1</span> <span class="o">>=</span> <span class="n">x</span><span class="p">:</span>
<span class="n">code</span> <span class="o">+=</span> <span class="nb">str</span><span class="p">(</span><span class="n">t</span><span class="o">//</span><span class="n">b</span><span class="p">)</span>
<span class="n">t</span> <span class="o">%=</span> <span class="n">b</span>
<span class="k">print</span> <span class="n">code</span>
<span class="c1">################################################################################</span>
<span class="k">print</span> <span class="s2">"F: 时间复杂度不足 变除为乘补零难"</span>
<span class="c1">################################################################################</span>
<span class="n">t</span> <span class="o">=</span> <span class="n">a</span> <span class="o">%</span> <span class="n">b</span>
<span class="n">lzero</span> <span class="o">=</span> <span class="s2">""</span>
<span class="n">_t</span> <span class="o">=</span> <span class="n">t</span> <span class="o">*</span> <span class="mi">10</span>
<span class="k">while</span> <span class="n">_t</span> <span class="o"><</span> <span class="n">b</span><span class="p">:</span>
<span class="n">lzero</span> <span class="o">+=</span> <span class="s2">"0"</span>
<span class="n">_t</span> <span class="o">*=</span> <span class="mi">10</span>
<span class="k">print</span> <span class="n">lzero</span> <span class="o">+</span> <span class="nb">str</span><span class="p">(</span><span class="n">t</span> <span class="o">*</span> <span class="mi">10</span> <span class="o">**</span> <span class="n">y</span> <span class="o">//</span> <span class="n">b</span><span class="p">)[</span><span class="n">x</span><span class="o">-</span><span class="mi">1</span><span class="p">:]</span>
<span class="c1">################################################################################</span>
<span class="k">print</span> <span class="s2">"F: 时间复杂度不足 同上"</span>
<span class="c1">################################################################################</span>
<span class="n">t</span> <span class="o">=</span> <span class="n">a</span> <span class="o">%</span> <span class="n">b</span>
<span class="n">lzero</span> <span class="o">=</span> <span class="s2">""</span>
<span class="n">_t</span> <span class="o">=</span> <span class="n">t</span> <span class="o">*</span> <span class="mi">10</span>
<span class="k">while</span> <span class="n">_t</span> <span class="o"><</span> <span class="n">b</span><span class="p">:</span>
<span class="n">lzero</span> <span class="o">+=</span> <span class="s2">"0"</span>
<span class="n">_t</span> <span class="o">*=</span> <span class="mi">10</span>
<span class="k">print</span> <span class="n">lzero</span> <span class="o">+</span> <span class="nb">str</span><span class="p">(</span><span class="nb">int</span><span class="p">(</span> <span class="nb">str</span><span class="p">(</span><span class="n">t</span><span class="p">)</span> <span class="o">+</span> <span class="s1">'0'</span> <span class="o">*</span> <span class="n">y</span> <span class="p">)</span> <span class="o">//</span> <span class="n">b</span><span class="p">)[</span><span class="n">x</span><span class="o">-</span><span class="mi">1</span><span class="p">:]</span>
<span class="c1">################################################################################</span>
<span class="k">print</span> <span class="s2">"T: 挑战成功 循环小数记录法"</span>
<span class="c1">################################################################################</span>
<span class="n">code</span> <span class="o">=</span> <span class="s2">""</span> <span class="c1"># 遇见循环即止</span>
<span class="n">rep</span> <span class="o">=</span> <span class="s2">""</span> <span class="c1"># 循环体</span>
<span class="n">left</span> <span class="o">=</span> <span class="p">[]</span> <span class="c1"># 余数池</span>
<span class="n">t</span> <span class="o">=</span> <span class="n">a</span> <span class="o">%</span> <span class="n">b</span>
<span class="k">for</span> <span class="n">c</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="n">y</span><span class="p">):</span>
<span class="k">if</span> <span class="n">t</span> <span class="ow">in</span> <span class="n">left</span><span class="p">:</span>
<span class="n">rep</span> <span class="o">=</span> <span class="n">code</span><span class="p">[</span><span class="n">left</span><span class="o">.</span><span class="n">index</span><span class="p">(</span><span class="n">t</span><span class="p">):]</span>
<span class="k">break</span>
<span class="k">else</span><span class="p">:</span>
<span class="n">left</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">t</span><span class="p">)</span>
<span class="n">t</span> <span class="o">*=</span> <span class="mi">10</span>
<span class="n">code</span> <span class="o">+=</span> <span class="nb">str</span><span class="p">(</span><span class="n">t</span><span class="o">//</span><span class="n">b</span><span class="p">)</span>
<span class="n">t</span> <span class="o">%=</span> <span class="n">b</span>
<span class="k">else</span><span class="p">:</span>
<span class="k">print</span> <span class="n">code</span><span class="p">[</span><span class="n">x</span><span class="o">-</span><span class="mi">1</span><span class="p">:]</span>
<span class="k">print</span> <span class="p">(</span> <span class="n">code</span> <span class="o">+</span> <span class="n">rep</span> <span class="o">*</span> <span class="p">(</span> <span class="p">(</span><span class="n">y</span> <span class="o">-</span> <span class="nb">len</span><span class="p">(</span><span class="n">code</span><span class="p">))</span><span class="o">/</span><span class="nb">len</span><span class="p">(</span><span class="n">rep</span><span class="p">)</span> <span class="p">)</span> <span class="o">+</span> <span class="n">rep</span><span class="p">[:</span> <span class="p">(</span> <span class="p">(</span><span class="n">y</span> <span class="o">-</span> <span class="nb">len</span><span class="p">(</span><span class="n">code</span><span class="p">))</span><span class="o">%</span><span class="nb">len</span><span class="p">(</span><span class="n">rep</span><span class="p">)</span> <span class="p">)</span> <span class="p">]</span> <span class="p">)[</span><span class="n">x</span><span class="o">-</span><span class="mi">1</span><span class="p">:]</span>
</pre></div>
</td></tr></table>【实习记】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">¶</a></h3>
<p>其实这是一个序贯决策问题,可以用动态规划来求解。我们采用一个二维矩阵来记录中间的结果。这个二维矩阵怎么构造呢?直接举个例子吧:”bab”和”caba”(当然我们现在一眼就可以看出来最长公共子串是”ba”或”ab”)</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">¶</a></h3>
<p>其实这是一个序贯决策问题,可以用动态规划来求解。我们采用一个二维矩阵来记录中间的结果。这个二维矩阵怎么构造呢?直接举个例子吧:”bab”和”caba”(当然我们现在一眼就可以看出来最长公共子串是”ba”或”ab”)</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>这样矩阵中的最大元素就是 最长公共子串的长度。</p>
<p>在构造这个二维矩阵的过程中由于得出矩阵的某一行后其上一行就没用了,所以实际上在程序中可以用一维数组来代替这个矩阵。</p>
<h3 id="_2">代码实践<a class="headerlink" href="#_2" title="Permanent link">¶</a></h3>
<p>根据以上算法 使用C语言实践了一下。</p>
<div class="highlight"><pre><span></span><span class="cp">#include</span> <span class="cpf"><stdlib.h></span><span class="cp"></span>
<span class="cp">#include</span> <span class="cpf"><stdio.h></span><span class="cp"></span>
<span class="cp">#include</span> <span class="cpf"><string.h></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">"hello world"</span><span class="p">,</span>
<span class="o">*</span><span class="n">strb</span> <span class="o">=</span> <span class="s">"malloc"</span><span class="p">;</span>
<span class="n">printf</span><span class="p">(</span><span class="s">"%s,%s: %d</span><span class="se">\n</span><span class="s">"</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"><</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"><</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">></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">></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">></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">¶</a></h3>
<p>研究了 求最长公共子串问题,顺便研究了字符串匹配</p>
<p>字符串匹配的Boyer-Moore算法 http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html</p>
<p>字符串匹配的<span class="caps">KMP</span>算法 http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html</p>
<p>动态规划算法之:最长公共子序列 <span class="amp">&</span> 最长公共子串(<span class="caps">LCS</span>) http://my.oschina.net/leejun2005/blog/117167</p>