?? 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 + -