📄 cs5da.htm
字号:
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<meta name="ProgId" content="FrontPage.Editor.Document">
<title>第五章 递归</title>
</head>
<body>
<p class="MsoNormal" style="margin-left:42.75pt;text-indent:-42.75pt;mso-list:
l6 level1 lfo7;tab-stops:list 42.75pt"><span lang="EN-US" style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">第五章<span style="font:7.0pt "Times New Roman"">
</span></span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">递归</span></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">一、填空题答案</span><span lang="EN-US">:</span></p>
<p class="MsoNormal" style="margin-left:21.0pt;text-indent:-21.0pt;mso-list:l2 level1 lfo6;
tab-stops:list 21.0pt"><span lang="EN-US">1.<span style="font:7.0pt "Times New Roman"">
</span>5,<span style="mso-spacerun: yes"> </span>3</span></p>
<p class="MsoNormal" style="margin-left:21.0pt;text-indent:-21.0pt;mso-list:l2 level1 lfo6;
tab-stops:list 21.0pt"><span lang="EN-US">2.<span style="font:7.0pt "Times New Roman"">
</span>e</span></p>
<p class="MsoNormal" style="margin-left:21.0pt;text-indent:-21.0pt;mso-list:l2 level1 lfo6;
tab-stops:list 21.0pt"><span lang="EN-US">3.<span style="font:7.0pt "Times New Roman"">
</span>head(head (tail(Ls)))</span></p>
<p class="MsoNormal" style="margin-left:21.0pt;text-indent:-21.0pt;mso-list:l2 level1 lfo6;
tab-stops:list 21.0pt"><span lang="EN-US">4.<span style="font:7.0pt "Times New Roman"">
</span></span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">递归过程</span></p>
<p class="MsoNormal" style="margin-left:21.0pt;text-indent:-21.0pt;mso-list:l2 level1 lfo6;
tab-stops:list 21.0pt"><span lang="EN-US">5.<span style="font:7.0pt "Times New Roman"">
</span></span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">分治法</span></p>
<p class="MsoNormal" style="margin-left:21.0pt;text-indent:-21.0pt;mso-list:l2 level1 lfo6;
tab-stops:list 21.0pt"><span lang="EN-US">6.<span style="font:7.0pt "Times New Roman"">
</span></span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">回溯法，试探法，回溯，向前试探</span></p>
<p class="MsoNormal"><span lang="EN-US"> <o:p>
</o:p>
</span></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">二、应用题</span></p>
<p class="MsoNormal" style="line-height:15.0pt"><span lang="EN-US">1</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">、</span><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman";mso-font-kerning:
8.0pt">【解答】</span><span style="mso-tab-count: 1; mso-font-kerning: 8.0pt" lang="EN-US">
</span><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman";
mso-font-kerning:8.0pt">根据递归定义，可以写出递归的算法。</span><span lang="EN-US" style="mso-font-kerning:8.0pt"><o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="line-height:15.0pt"><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;mso-font-kerning:8.0pt"><span style="mso-tab-count:2">
</span><b style="mso-bidi-font-weight:
normal">enum</b> boolean <b style="mso-bidi-font-weight:normal">{ </b>False,
True <b style="mso-bidi-font-weight:normal">}</b><o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="margin-left:21.25pt;text-indent:21.25pt;line-height:
15.0pt"><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;
mso-font-kerning:8.0pt">boolean Knap( <b style="mso-bidi-font-weight:normal">int</b>
s, <b style="mso-bidi-font-weight:normal">int</b> n ) <b style="mso-bidi-font-weight:
normal">{<o:p>
</o:p>
</b></span></p>
<p class="MsoNormal" style="line-height:15.0pt"><b style="mso-bidi-font-weight:
normal"><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;
mso-font-kerning:8.0pt"><span style="mso-tab-count:3">
</span>if </span></b><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;
mso-font-kerning:8.0pt">( s == 0 )<b style="mso-bidi-font-weight:normal"> return
</b>True<b style="mso-bidi-font-weight:normal">;<o:p>
</o:p>
</b></span></p>
<p class="MsoNormal" style="line-height:15.0pt"><b style="mso-bidi-font-weight:
normal"><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;
mso-font-kerning:8.0pt"><span style="mso-tab-count:3">
</span>if</span></b><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;mso-font-kerning:
8.0pt"> ( s < 0 || s > 0 <b style="mso-bidi-font-weight:normal">&&
</b>n < 1 ) <b style="mso-bidi-font-weight:normal">return</b> False<b style="mso-bidi-font-weight:normal">;<o:p>
</o:p>
</b></span></p>
<p class="MsoNormal" style="line-height:15.0pt"><b style="mso-bidi-font-weight:
normal"><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;
mso-font-kerning:8.0pt"><span style="mso-tab-count:3">
</span>if </span></b><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;
mso-font-kerning:8.0pt">( Knap ( s – W[n], n</span><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;font-family:宋体;mso-hansi-font-family:
"Times New Roman";mso-font-kerning:8.0pt">-</span><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;mso-font-kerning:8.0pt">1
) == True )<o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="line-height:15.0pt"><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;mso-font-kerning:8.0pt"><span style="mso-tab-count:4">
</span><b style="mso-bidi-font-weight:normal">{ cout</b> << W[n] <<
‘ , ’<b style="mso-bidi-font-weight:normal">;<span style="mso-spacerun: yes">
</span>return </b>True<b style="mso-bidi-font-weight:normal">; }<o:p>
</o:p>
</b></span></p>
<p class="MsoNormal" style="line-height:15.0pt"><b style="mso-bidi-font-weight:
normal"><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;
mso-font-kerning:8.0pt"><span style="mso-tab-count:3">
</span>return </span></b><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;
mso-font-kerning:8.0pt">Knap( s, n</span><span lang="EN-US" style="font-size:
9.0pt;mso-bidi-font-size:12.0pt;font-family:宋体;mso-hansi-font-family:"Times New Roman";
mso-font-kerning:8.0pt">-</span><span lang="EN-US" style="font-size:9.0pt;
mso-bidi-font-size:12.0pt;mso-font-kerning:8.0pt">1 )<b style="mso-bidi-font-weight:
normal">;<o:p>
</o:p>
</b></span></p>
<p class="MsoNormal" style="line-height:15.0pt"><b style="mso-bidi-font-weight:
normal"><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;
mso-font-kerning:8.0pt"><span style="mso-tab-count:2">
</span>} </span></b><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;
mso-font-kerning:8.0pt"><o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="line-height:15.0pt"><span style="mso-tab-count: 1; mso-font-kerning: 8.0pt" lang="EN-US">
</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-font-kerning:8.0pt">若设</span><span lang="EN-US" style="mso-font-kerning:8.0pt">w
= <b style="mso-bidi-font-weight:normal">{</b> 0, 1, 2, 4, 8, 16, 32 <b style="mso-bidi-font-weight:normal">}</b></span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-font-kerning:8.0pt">，</span><span lang="EN-US" style="mso-font-kerning:8.0pt">s
= 51, n = 6</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman";
mso-font-kerning:8.0pt">。则递归执行过程如下</span><span lang="EN-US" style="mso-font-kerning:
8.0pt"><o:p>
</o:p>
</span></p>
<table border="1" cellspacing="0" cellpadding="0" style="margin-left:7.4pt;
border-collapse:collapse;mso-table-layout-alt:fixed;border:none;mso-border-alt:
solid windowtext .5pt;mso-padding-alt:0cm 5.4pt 0cm 5.4pt">
<tr>
<td width="24" rowspan="8" valign="top" style="width:18.0pt;border:solid windowtext .5pt;
padding:0cm 5.4pt 0cm 5.4pt">
<p class="MsoNormal" style="line-height:15.0pt"><!--[if gte vml 1]><v:line
id="_x0000_s1026" style='position:absolute;left:0;text-align:left;z-index:1'
from="11pt,10.5pt" to="11pt,59.5pt" o:allowincell="f">
<v:stroke endarrow="block" endarrowwidth="narrow" endarrowlength="long"/>
</v:line><![endif]-->
<span style="mso-ignore:vglayout">
<table cellpadding="0" cellspacing="0" align="left">
<tr>
<td width="11" height="13"></td>
</tr>
<tr>
<td></td>
<td><img src="../tp/cs5da.7.gif" v:shapes="_x0000_s1026" width="10" height="68"></td>
</tr>
</table>
</span><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:
12.0pt;mso-font-kerning:8.0pt"> <o:p>
</o:p>
</span>
<p class="MsoNormal" style="line-height:15.0pt"><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;mso-font-kerning:8.0pt"> <o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="line-height:15.0pt"><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;mso-font-kerning:8.0pt"> <o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="line-height:15.0pt"><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;mso-font-kerning:8.0pt"> <o:p>
</o:p>
</span></p>
<br style="mso-ignore:vglayout" clear="ALL">
<p class="MsoNormal" style="line-height:15.0pt"><span style="font-size:9.0pt;
mso-bidi-font-size:12.0pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman";mso-font-kerning:8.0pt">递归</span><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;mso-font-kerning:
8.0pt"><o:p>
</o:p>
</span></p>
</td>
<td width="91" valign="top" style="width:68.0pt;border:solid windowtext .5pt;
border-left:none;mso-border-left-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt">
<p class="MsoNormal" style="line-height:15.0pt"><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;mso-font-kerning:8.0pt">Knap(51,
6)<o:p>
</o:p>
</span></p>
</td>
<td width="76" valign="top" style="width:57.0pt;border:none;border-top:solid windowtext .5pt;
mso-border-left-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt">
<p class="MsoNormal" style="line-height:15.0pt"> <span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;mso-font-kerning:
8.0pt"><o:p>
</o:p>
</span></p>
</td>
<td width="79" valign="top" style="width:59.0pt;border:none;border-top:solid windowtext .5pt;
padding:0cm 5.4pt 0cm 5.4pt">
<p class="MsoNormal" style="line-height:15.0pt"> <span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;mso-font-kerning:
8.0pt"><o:p>
</o:p>
</span></p>
</td>
<td width="77" valign="top" style="width:58.0pt;border:none;border-top:solid windowtext .5pt;
padding:0cm 5.4pt 0cm 5.4pt">
<p class="MsoNormal" style="line-height:15.0pt"> <span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;mso-font-kerning:
8.0pt"><o:p>
</o:p>
</span></p>
</td>
<td width="80" valign="top" style="width:60.0pt;border-top:solid windowtext .5pt;
border-left:none;border-bottom:none;border-right:solid windowtext .5pt;
padding:0cm 5.4pt 0cm 5.4pt">
<p class="MsoNormal" style="line-height:15.0pt"> <span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;mso-font-kerning:
8.0pt"><o:p>
</o:p>
</span></p>
</td>
<td width="120" valign="top" style="width:90.0pt;border:solid windowtext .5pt;
border-left:none;mso-border-left-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt">
<p class="MsoNormal" style="line-height:15.0pt"><b style="mso-bidi-font-weight:
normal"><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;
mso-font-kerning:8.0pt">return</span></b><span lang="EN-US" style="font-size:
9.0pt;mso-bidi-font-size:12.0pt;mso-font-kerning:8.0pt"> True, </span><span style="font-size:9.0pt;mso-bidi-font-size:12.0pt;font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman";mso-font-kerning:
8.0pt">完成</span><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:
12.0pt;mso-font-kerning:8.0pt"><o:p>
</o:p>
</span></p>
</td>
</tr>
<tr>
<td width="91" valign="top" style="width:68.0pt;border-top:none;border-left:none;
border-bottom:solid windowtext .5pt;border-right:solid windowtext .5pt;
mso-border-top-alt:solid windowtext .5pt;mso-border-left-alt:solid windowtext .5pt;
padding:0cm 5.4pt 0cm 5.4pt">
<p class="MsoNormal" style="line-height:15.0pt"><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;mso-font-kerning:8.0pt">Knap(51</span><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;font-family:宋体;
mso-hansi-font-family:"Times New Roman";mso-font-kerning:8.0pt">-</span><span lang="EN-US" style="font-size:9.0pt;mso-bidi-font-size:12.0pt;mso-font-kerning:
8.0pt">32, 5)<span style="mso-spacerun: yes"> </span><o:p>
</o:p>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -