📄 page_1147.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html> <head> <title>page_1147</title> <link rel="stylesheet" href="reset.css" type="text/css" media="all"> <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /> </head> <body> <table summary="top nav" border="0" width="100%"> <tr> <td align="left" width="30%" style="background: #EEF3E2"><a style="color: blue; font-size: 120%; font-weight: bold; text-decoration: none; font-family: verdana;" href="page_1146.html">< previous page</a></td> <td align="center" width="40%" style="background: #EEF3E2"><strong style="color: #2F4F4F; font-size: 120%;">page_1147</strong></td> <td align="right" width="30%" style="background: #EEF3E2"><a style="color: blue; font-size: 120%; font-weight: bold; text-decoration: none; font-family: verdana;" href="page_1148.html">next page ></a></td> </tr> <tr> <td align="left" colspan="3" style="background: #ffffff; padding: 20px;"> <table border="0" width="100%" cellpadding="0"><tr><td align="center"> <table border="0" cellpadding="2" cellspacing="0" width="100%"><tr><td align="left"></td> <td align="right"></td> </tr></table></td></tr><tr><td align="left"><p></p><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="right"><font face="Times New Roman, Times, Serif" size="2" color="#FF0000">Page 1147</font></td></tr></table><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="17"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="3">Problem-Solving Case Study Minimum Value in an Integer Array</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="3"><img src="e2232d699e914db72baae73d12c23521.gif" border="0" alt="1147-01.gif" width="120" height="252" /></font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="3">Problem: Find the minimum value in an integer array indexed from 0 through </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">length</font><font face="Times New Roman, Times, Serif" size="3"> - 1.</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="3">Discussion: This problem is easy to solve iteratively, but the objective here is to think recursively. The problem has to be stated in terms of a smaller case of itself. Because this is a problem using an array, a smaller case involves a smaller array. The minimum value in an array of length </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">length</font><font face="Times New Roman, Times, Serif" size="3"> is the smaller of </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">list[length-1]</font><font face="Times New Roman, Times, Serif" size="3"> and the smallest value in the array from </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">list[0]</font><font face="Times New Roman, Times, Serif" size="3"> ... </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">list[length-2]</font><font face="Times New Roman, Times, Serif" size="3">.</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="3">Minimum (In: list, length)</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table><table cellspacing="0" border="0" width="344" cellpadding="4"><tr><td valign="top"><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Courier New, Courier, Mono New, Courier, Mono" size="2">Set聽minSoFar聽=聽Minimum(list,聽length-1)<br />IF聽list[length-1]聽<聽minSoFar<br />聽聽聽Return聽list[length-1]<br />ELSE<br />聽聽Return聽minSoFar</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table></td></tr></table><br /><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="3">This algorithm looks reasonable. All we need is a base case. Because each recursive call reduces the length of the array by one, our base case occurs when </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">length</font><font face="Times New Roman, Times, Serif" size="3"> is 1. We know the minimum value for this call: it is the only value in the array.</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Courier New, Courier, Mono New, Courier, Mono" size="2">int聽Minimum(<br />聽聽聽聽聽聽聽/*聽in聽*/聽const聽int聽list[],聽聽聽聽//聽Array聽of聽integers聽to聽examine<br />聽聽聽聽聽聽聽/*聽in聽*/聽int聽聽聽聽聽聽聽length聽)聽聽聽//聽One聽greater聽than聽index聽of<br />聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽//聽聽聽last聽number聽in聽array<br />//聽Precondition:<br />//聽聽聽聽聽list[0..length-1]聽are聽assigned<br />//聽聽&&聽length聽>=聽1<br />//聽Postcondition:<br />//聽聽聽聽聽Function聽value聽==聽smallest聽number聽in聽list[0..length-1]<br /><br />{<br />聽聽聽聽int聽minSoFar;聽聽聽聽聽聽聽//聽Minimum聽returned聽from聽recursive聽call<br /><br />聽聽聽聽if聽(length聽==聽1)<br />聽聽聽聽聽聽聽聽return聽list[0];聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽//聽Base聽case</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table></td></tr></table><p><font size="0"></font></p>聽 </td> </tr> <tr> <td align="left" width="30%" style="background: #EEF3E2"><a style="color: blue; font-size: 120%; font-weight: bold; text-decoration: none; font-family: verdana;" href="page_1146.html">< previous page</a></td> <td align="center" width="40%" style="background: #EEF3E2"><strong style="color: #2F4F4F; font-size: 120%;">page_1147</strong></td> <td align="right" width="30%" style="background: #EEF3E2"><a style="color: blue; font-size: 120%; font-weight: bold; text-decoration: none; font-family: verdana;" href="page_1148.html">next page ></a></td> </tr> </table> </body> </html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -