一个计算数字的步数算法

论坛 期权论坛     
选择匿名的用户   2021-5-31 00:41   73   0
<div class="content-detail markdown-body">
<div class="content" style="color:rgb(51,51,51);font-family:&#39;Helvetica Neue&#39;, Helvetica, Arial, sans-serif;font-size:14px;line-height:20px;">
  <p>这两天看了下某位大神的github,知道他对算法比较感兴趣,看了其中的一个计算数字的步数算法,感觉这个有点意思,所以就自己实现了一个</p>
  <h3 style="font-weight:500;line-height:1.1;color:rgb(242,36,48);font-size:24px;">算法描述与实现原理</h3>
  <p>给出一个整型数字,统计出有多少种走法可以到达目标,比如一个数字<code style="font-family:Menlo, Monaco, Consolas, &#39;Courier New&#39;, monospace;font-size:12.6px;color:rgb(199,37,78);">4</code>,可以有下面几种走法</p>
  <div class="highlight">
   <pre class="blockcode"><code class="language-html" style="font-family:Menlo, Monaco, Consolas, &#39;Courier New&#39;, monospace;font-size:inherit;color:inherit;">    [ 1, 3 ]
        [ 4 ]
    [ 1, 1, 2 ]
        [ 2, 2 ]
    [ 1, 1, 1, 1 ]
</code></pre>
  </div>
  <p>其实通过上面的组合可以得出下面的结论</p>
  <ul><li> <p>先列出所有项是1的组合</p> </li><li> <p>依次从左到右项为1的组合</p> </li><li> <p>递归上面的集合,找出项里1的索引,然后计算左起2项的值,结果递归此操作</p> </li><li> <p>排除1和2的情况</p> </li></ul>
  <p>下面先提供三个工具函数</p>
  <div class="highlight">
   <pre class="blockcode"><code class="language-js" style="font-family:Menlo, Monaco, Consolas, &#39;Courier New&#39;, monospace;font-size:inherit;color:inherit;"><span class="c1" style="color:rgb(64,128,128);font-style:italic;">// 计算数组内的值</span>
<span class="kd" style="color:rgb(0,128,0);font-weight:bold;">function</span> <span class="nx">calculate</span><span class="p">(</span><span class="nx">arg</span><span class="p">){<!-- --></span>
    <span class="k" style="color:rgb(0,128,0);font-weight:bold;">return</span> <span class="nb" style="color:rgb(0,128,0);">eval</span><span class="p">(</span><span class="nx">arg</span><span class="p">.</span><span class="nx">join</span><span class="p">(</span><span class="s1" style="color:rgb(186,33,33);">&#39;&#43;&#39;</span><span class="p">));</span>
<span class="p">}</span>

<span class="c1" style="color:rgb(64,128,128);font-style:italic;">// 输出数组的值</span>
<span class="kd" style="color:rgb(0,128,0);font-weight:bold;">function</span> <span class="nx">print</span><span class="p">(</span><span class="nx">arg</span><span class="p">){<!-- --></span>
    <span class="k" style="color:rgb(0,128,0);font-weight:bold;">for</span><span class="p">(</span><span class="kd" style="color:rgb(0,128,0);font-weight:bold;">var</span> <span class="nx">i</span> <span class="o" style="color:rgb(102,102,102);">&#61;</span> <span class="mi" style="color:rgb(102,102,102);">0</span><span class="p">;</span> <span class="nx">i</span> <span class="o" style="color:rgb(102,102,102);">&lt;</span> <span class="nx">arg</span><span class="p">.</span><span class="nx">length</span><span class="p">;</span> <span class="nx">i</span><span class="o" style="color:rgb(102,102,102);">&#43;&#43;</span><span class="p">){<!-- --></span>
        <span class="nx">console</span><span class="p">.</span><span class="nx">log</span><span class="p">(</span><span class="nx">arg</span><span class="p">[</span><span class="nx">i</span><span class="p">]);</span>
    <span class="p">}</span>
<span class="p">}</span>

<span class="c1" style="color:rgb(64,128,128);font-style:italic;">// 检查是否是正反的走法</span>
<span class="kd" style="color:rgb(0,128,0);font-weight:bold;">function</span> <span class="nx">hasRepeat</span><span class="p">(</span><span class="nx">src</span><span class="p">,</span> <span class="nx">dist</span><span class="p">){<!-- --></span>
    <span class="k" style="color:rgb(0,128,0);font-weight:bold;">if</span> <span class="p">(</span><span class="nx">dist</span><span class="p">.</span><span class="nx">length</span> <span class="o" style="color:rgb(102,102,102);">!&#61;</span> <span class="mi" style="color:rgb(102,102,102);">2</span><span class="p">)</span> <span class="k" style="color:rgb(0,128,0);font-weight:bold;">return</span> <span class="kc" style="color:rgb(0,128,0);font-weight:bold;">false</span><span class="p">;</span>
    <span class="k" style="color:rgb(0,128,0);font-weight:bold;">for</span><span class="p">(</span><span class="kd" style="color:rgb(0,128,0);font-weight:bold;">var</span> <span class="nx">i</span> <span class="o" style="color:rgb(102,102,102);">&#61;</span> <span class="mi" style="color:rgb(102,102,102);">0</span><span class="p">,</span> <span class="nx">len</span> <span class="o" style="color:rgb(102,102,102);">&#61;</span> <span class="nx">src</span><span class="p">.</span><span class="nx">length</span><span class="p">;</span> <span class="nx">i</span> <span class="o" style="color:rgb(102,102,102);">&lt;</span> <span class="nx">len</span> <span class="p">;</span> <span class="nx">i</span><span class="o" style="color:rgb(102,102,102);">&#43;&#43;</span><span class="p">){<!-- --></span>
        <span class="k" style="color:rgb(0,128,0);font-weight:bold;">if</span><span class="p">(</span><span class="nx">dist</span><span class="p">.</span><span class="nx">length</span> <span class="o" style="color:rgb(102,102,102);">&#61;&#61;</span> <span class="nx">src</span><span class="p">[</span><span clas
分享到 :
0 人收藏
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

积分:3875789
帖子:775174
精华:0
期权论坛 期权论坛
发布
内容

下载期权论坛手机APP