📄 cs5.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" align="center" style="text-align: center; line-height: 150%"><b><span style="font-size:15.0pt;mso-bidi-font-size:12.0pt;font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">第五章</span><span style="mso-spacerun: yes; font-size: 15.0pt; mso-bidi-font-size: 12.0pt" lang="EN-US">
</span><span style="font-size:15.0pt;
mso-bidi-font-size:12.0pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">递归</span><span lang="EN-US" style="font-size:15.0pt;mso-bidi-font-size:12.0pt"><o:p>
</o:p>
</span></b></p>
<p class="MsoNormal" style="line-height: 150%"><b><span lang="EN-US"> <o:p>
</o:p>
</span></b></p>
<p class="MsoNormal" style="line-height: 150%"><b><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">一、填空题</span><span lang="EN-US"><o:p>
</o:p>
</span></b></p>
<p class="MsoNormal" style="text-indent: -21.0pt; mso-list: l0 level1 lfo1; tab-stops: list 21.0pt; line-height: 150%; margin-left: 21.0pt"><span lang="EN-US">1.<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><span lang="EN-US">(a</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，</span><span lang="EN-US">(a</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">b)</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">d,e</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，</span><span lang="EN-US">((i</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">j)</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">k))</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，则该广义表的长度为</span><u><span style="mso-spacerun: yes" lang="EN-US">
</span></u><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，深度为</span><u><span style="mso-spacerun: yes" lang="EN-US">
</span></u><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">。</span></p>
<p class="MsoNormal" style="text-indent: -21.0pt; mso-list: l0 level1 lfo1; tab-stops: list 21.0pt; line-height: 150%; margin-left: 21.0pt"><span lang="EN-US">2.<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><span lang="EN-US">A=((a</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，</span><span lang="EN-US">b</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">c)</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">(d</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，</span><span lang="EN-US">e</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">0))</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">，则运算</span><span lang="EN-US">head(head(tail(tail(A))))=<u><span style="mso-spacerun: yes">
</span></u></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="text-indent: -21.0pt; mso-list: l0 level1 lfo1; tab-stops: list 21.0pt; line-height: 150%; margin-left: 21.0pt"><span lang="EN-US">3.<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><span lang="EN-US">Ls=(a</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，</span><span lang="EN-US">(b</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">c</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">d)</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，</span><span lang="EN-US">e)</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，运用</span><span lang="EN-US">head</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">和</span><span lang="EN-US">tail</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">函数取出</span><span lang="EN-US">Ls</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">中的原子</span><span lang="EN-US">b</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="text-indent: 21.0pt; mso-char-indent-count: 2.0; mso-char-indent-size: 10.5pt; line-height: 150%"><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">是</span><u><span style="mso-spacerun: yes" lang="EN-US">
</span></u><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">。</span></p>
<p class="MsoNormal" style="text-indent: -42.0pt; mso-list: l1 level1 lfo3; tab-stops: list 18.0pt; line-height: 150%; margin-left: 42.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><u><span style="mso-spacerun: yes" lang="EN-US">
</span></u><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">。</span></p>
<p class="MsoNormal" style="text-indent: -18.0pt; mso-list: l1 level1 lfo3; tab-stops: list 18.0pt; line-height: 150%; margin-left: 18.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><u><span style="mso-spacerun: yes" lang="EN-US">
</span></u><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">。</span></p>
<p class="MsoNormal" style="text-indent: -18.0pt; mso-list: l1 level1 lfo3; tab-stops: list 18.0pt; line-height: 150%; margin-left: 18.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><u><span style="mso-spacerun: yes" lang="EN-US">
</span></u><span style="mso-spacerun: yes" lang="EN-US"> </span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">；也可称为</span><u><span style="mso-spacerun:
yes" lang="EN-US">
</span></u><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"">放弃当前候选解，寻找下一个候选解的过程叫做</span><u><span style="mso-spacerun: yes" lang="EN-US">
</span></u><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">。扩大当前候选解的规模并继续试探的过程叫</span></p>
<p class="MsoNormal" style="text-indent: 21.0pt; mso-char-indent-count: 2.0; mso-char-indent-size: 10.5pt; line-height: 150%"><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">做</span><u><span style="mso-spacerun: yes" lang="EN-US">
</span></u><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: 150%"><span lang="EN-US"> <o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="line-height: 150%"><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: 150%"><span lang="EN-US">1</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -