写一个程序，让系统任务管理器的CPU使用曲线为50%，进阶是如何让 曲线为正弦曲线[1]。还有，如何实现双线程高效下载[2]。都是比较有意思、实用的例子。
##最大距离##
现在有一个题:求二叉树中节点的最大距离。这种题目一看感觉就是必须用到递归。_算法导论_上说递归算法可能将问题划分为规模不同的子问题。而寻找最小子问题就是关键。
解法如下:
|
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 |
<span class="k">struct</span> <span class="n">Node</span> <span class="p">{</span> <span class="k">struct</span> <span class="n">Node</span> <span class="o">*</span><span class="n">LNode</span><span class="p">;</span> <span class="k">struct</span> <span class="n">Node</span> <span class="o">*</span><span class="n">RNode</span><span class="p">;</span> <span class="kt">int</span> <span class="n">LeftMaxLen</span><span class="p">;</span> <span class="kt">int</span> <span class="n">RightMaxLen</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">MaxLen</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="kt">void</span> <span class="nf">FindMax</span><span class="p">(</span><span class="k">struct</span> <span class="n">Node</span> <span class="o">*</span><span class="n">root</span><span class="p">)</span> <span class="p">{</span> <span class="k">if</span><span class="p">(</span><span class="n">root</span><span class="o">==</span><span class="nb">NULL</span><span class="p">)</span> <span class="k">return</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">root</span><span class="o">-></span><span class="n">LNode</span><span class="o">==</span><span class="nb">NULL</span><span class="p">)</span> <span class="n">root</span><span class="o">-></span><span class="n">LeftMaxLen</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">root</span><span class="o">-></span><span class="n">RNode</span><span class="o">==</span><span class="nb">NULL</span><span class="p">)</span> <span class="n">root</span><span class="o">-></span><span class="n">RightMaxLen</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">root</span><span class="o">-></span><span class="n">LNode</span><span class="o">!=</span><span class="nb">NULL</span><span class="p">)</span> <span class="p">{</span> <span class="n">FindMax</span><span class="p">(</span><span class="n">root</span><span class="o">-></span><span class="n">LNode</span><span class="p">);</span> <span class="p">}</span> <span class="k">if</span><span class="p">(</span><span class="n">root</span><span class="o">-></span><span class="n">RNode</span><span class="o">!=</span><span class="nb">NULL</span><span class="p">)</span> <span class="p">{</span> <span class="n">FindMax</span><span class="p">(</span><span class="n">root</span><span class="o">-></span><span class="n">RNode</span><span class="p">);</span> <span class="p">}</span> <span class="k">if</span><span class="p">(</span><span class="n">root</span><span class="o">-></span><span class="n">LNode</span><span class="o">!=</span><span class="nb">NULL</span><span class="p">)</span> <span class="p">{</span> <span class="kt">int</span> <span class="n">temp</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">root</span><span class="o">-></span><span class="n">LNode</span><span class="o">-></span><span class="n">LeftMaxLen</span> <span class="o">></span> <span class="n">root</span><span class="o">-></span><span class="n">LNode</span><span class="o">-></span><span class="n">RightMaxLen</span><span class="p">)</span> <span class="n">temp</span><span class="o">=</span><span class="n">root</span><span class="o">-></span><span class="n">LNode</span><span class="o">-></span><span class="n">LeftMaxLen</span><span class="p">;</span> <span class="k">else</span> <span class="n">temp</span><span class="o">=</span><span class="n">root</span><span class="o">-></span><span class="n">LNode</span><span class="o">-></span><span class="n">RightMaxLen</span> <span class="n">root</span><span class="o">-></span><span class="n">LeftMaxLen</span><span class="o">=</span><span class="n">temp</span><span class="o">+</span><span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="k">if</span><span class="p">(</span><span class="n">root</span><span class="o">-></span><span class="n">RNode</span><span class="o">!=</span><span class="nb">NULL</span><span class="p">)</span> <span class="p">{</span> <span class="kt">int</span> <span class="n">temp</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">root</span><span class="o">-></span><span class="n">RNode</span><span class="o">-></span><span class="n">LeftMaxLen</span> <span class="o">></span> <span class="n">root</span><span class="o">-></span><span class="n">RNode</span><span class="o">-></span><span class="n">RightMaxLen</span><span class="p">)</span> <span class="n">temp</span><span class="o">=</span><span class="n">root</span><span class="o">-></span><span class="n">RNode</span><span class="o">-></span><span class="n">LeftMaxLen</span><span class="p">;</span> <span class="k">else</span> <span class="n">temp</span><span class="o">=</span><span class="n">root</span><span class="o">-></span><span class="n">RNode</span><span class="o">-></span><span class="n">RightMaxLen</span> <span class="n">root</span><span class="o">-></span><span class="n">RightMaxLen</span><span class="o">=</span><span class="n">temp</span><span class="o">+</span><span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="k">if</span><span class="p">(</span><span class="n">root</span><span class="o">-></span><span class="n">LeftMaxLen</span> <span class="o">+</span> <span class="n">root</span><span class="o">-></span><span class="n">RightMaxLen</span> <span class="o">></span> <span class="n">MaxLen</span><span class="p">)</span> <span class="p">{</span> <span class="n">MaxLen</span><span class="o">=</span><span class="n">root</span><span class="o">-></span><span class="n">LeftMaxLen</span> <span class="o">+</span> <span class="n">root</span><span class="o">-></span><span class="n">RightMaxLen</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> |
这里的最小子问题是root==NULL或者可以看做root->LNode==NULL和root->RNode==NULL。所有的节点都是递归到了这一步得到MaxLen的初始化值。
MaxLen用来实时更新最大距离。
0
