📄 page_1129.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html> <head> <title>page_1129</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_1128.html">< previous page</a></td> <td align="center" width="40%" style="background: #EEF3E2"><strong style="color: #2F4F4F; font-size: 120%;">page_1129</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_1130.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 1129</font></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">rithm: to free the <i>n</i>th circle, we have to move <i>n</i> - 1 circles. Each stage can be thought of as beginning again with three pegs, but with one less circle each time. Let's see if we can summarize this process, using <i>n</i> instead of an actual number.</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">Get聽N聽Circles聽Moved聽from聽Peg聽1聽to聽Peg聽3</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="384" 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">Get聽n聽-聽1聽circles聽moved聽from聽peg聽1聽to聽peg聽2<br />Move聽nth聽circle聽from聽peg聽1聽to聽peg聽3<br />Get聽n聽-聽1聽circles聽moved聽from聽peg聽2聽to聽peg聽3</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 certainly sounds simple; surely there must be more. But this really is all there is to it.</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">Let's write a recursive function that implements this algorithm. We can't actually move disks, of course, but we can print out a message to do so. Notice that the beginning peg, the ending peg, and the auxiliary peg keep changing during the algorithm. To make the algorithm easier to follow, we call the pegs </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">beginPeg</font><font face="Times New Roman, Times, Serif" size="3">, </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">endPeg</font><font face="Times New Roman, Times, Serif" size="3">, and </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">auxPeg</font><font face="Times New Roman, Times, Serif" size="3">. These three pegs, along with the number of circles on the beginning peg, are the parameters of the function.</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">We have the recursive or general case, but what about a base case? How do we know when to stop the recursive process? The clue is in the expression Get <i>n</i> circles moved. If we don't have any circles to move, we don't have anything to do. We are finished with that stage. Therefore, when the number of circles equals 0, we do nothing (that is, we return).</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">void聽DoTowers(<br />聽聽聽/*聽in聽*/聽int聽circleCount,聽聽聽聽//聽Number聽of聽circles聽to聽move<br />聽聽聽/*聽in聽*/聽int聽beginPeg,聽聽聽聽聽聽聽//聽Peg聽containing聽circles聽to聽move<br />聽聽聽/*聽in聽*/聽int聽auxPeg,聽聽聽聽聽聽聽聽聽//聽Peg聽holding聽circles聽temporarily<br />聽聽聽/*聽in聽*/聽int聽endPeg聽聽聽聽聽聽)聽聽聽//聽Peg聽receiving聽circles聽being聽moved<br />{<br />聽聽聽聽if聽(circleCount聽>聽0)<br />聽聽聽聽{<br />聽聽聽聽聽聽聽聽//聽Move聽n聽-聽1聽circles聽from聽beginning聽peg聽to聽auxiliary聽peg<br /><br />聽聽聽聽聽聽聽聽DoTowers(circleCount聽-聽1,聽beginPeg,聽endPeg,聽auxPeg);<br />聽聽聽聽聽聽聽聽cout聽<<聽Move聽circle聽from聽peg聽聽<<聽beginPeg<br />聽聽聽聽聽聽聽聽聽聽聽聽聽<<聽聽to聽peg聽聽<<聽endPeg聽<<聽endl;<br /><br />聽聽聽聽聽聽聽聽//聽Move聽n聽-聽1聽circles聽from聽auxiliary聽peg聽to聽ending聽peg<br /><br />聽聽聽聽聽聽聽聽DoTowers(circleCount聽-聽1,聽auxPeg,聽beginPeg,聽endPeg);<br />聽聽聽聽}<br />}</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_1128.html">< previous page</a></td> <td align="center" width="40%" style="background: #EEF3E2"><strong style="color: #2F4F4F; font-size: 120%;">page_1129</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_1130.html">next page ></a></td> </tr> </table> </body> </html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -