{"id":854,"date":"2013-11-16T12:27:40","date_gmt":"2013-11-16T04:27:40","guid":{"rendered":"http:\/\/guoh.ai\/lifelog\/?p=854"},"modified":"2013-11-16T12:36:02","modified_gmt":"2013-11-16T04:36:02","slug":"towers-of-hanoi","status":"publish","type":"post","link":"https:\/\/guoh.ai\/lifelog\/2013\/11\/towers-of-hanoi\/","title":{"rendered":"\u6c49\u8bfa\u5854\u6e38\u620f"},"content":{"rendered":"

\u524d\u5929\u5728\u4e00\u6b21\u9762\u8bd5\u4e2d\uff0c\u9762\u8bd5\u5b98\u95ee\u5230\u6211\u6c49\u8bfa\u5854(Towers of Hanoi)\u7684\u95ee\u9898\uff0c\u5f53\u65f6\u53ea\u77e5\u9053\u662f\u9012\u5f52\uff0c\u77e5\u9053\u624b\u52a8\u73a9\u6e38\u620f\u600e\u4e48\u73a9\uff0c\u5199\u7a0b\u5e8f\u8fd8\u771f\u7684\u5fd8\u8bb0\u4e86\u3002\u5927\u5b66\u6211\u8bb0\u5f97\u662f\u6709\u5199\u8fc7\u8fd9\u6837\u7684\u4f5c\u4e1a\uff0c\u8fd8\u6709\u516b\u7687\u540e\u7b49\u7b49\uff0c\u4e0d\u8fc7\u771f\u7684\u90fd\u8fd8\u7ed9\u8001\u5e08\u4e86\uff0c\u54c8\u54c8\u54c8\uff01<\/p>\n

\u7136\u540e\u56de\u5bb6\u770b\u4e86\u4e0b\uff0c
\nhttp:\/\/www.cs.cmu.edu\/~cburch\/survey\/recurse\/hanoiimpl.html
\nhttp:\/\/www.python-course.eu\/towers_of_hanoi.php<\/p>\n

\u6c49\u8bfa\u5854\u7684\u4ecb\u7ecd\u53c2\u89c1http:\/\/en.wikipedia.org\/wiki\/Tower_of_Hanoi\u7b49\u7b49<\/p>\n

\u7a0b\u5e8f\u5982\u4e0b\uff0c<\/p>\n

\r\n#include <stdio.h>\r\n\r\nvoid move(char src, char dest)\r\n{\r\n\tprintf("\\nMove the top plate of %c to %c", src, dest);\r\n}\r\n\r\nvoid hanoi(int n, char a, char b, char c)\r\n{\r\n\tif (n == 1) { \/\/ \u9012\u5f52\u7ed3\u675f\r\n\t\tmove(a, c); \/\/ \u6700\u5c0f\u7684\u90a3\u4e2a\u76d8\u5b50\r\n\t} else {\r\n\t\thanoi(n - 1, a, c, b); \/\/ step 1\uff0c\u628a\u6240\u6709\u5c0f\u4e8e\u6700\u5927\u7684\u76d8\u5b50\u79fb\u52a8\u5230\u4e34\u65f6\u7684\u67f1\u5b50\u4e0a(\u53ef\u4ee5\u501f\u52a9\u76ee\u7684\u67f1\u5b50)\r\n\t\tmove(a, c); \/\/ step 2\uff0c\u628a\u6700\u5927\u7684\u76d8\u5b50\u79fb\u52a8\u5230\u76ee\u7684\u67f1\u5b50\u4e0a\r\n\t\thanoi(n - 1, b, a, c); \/\/ step 3\uff0c\u628a\u4e34\u65f6\u7684\u67f1\u5b50\u4e0a\u7684\u76d8\u5b50\u79fb\u52a8\u5230\u76ee\u7684\u67f1\u5b50\u4e0a(\u53ef\u4ee5\u501f\u52a9\u539f\u59cb\u67f1\u5b50)\uff0c\u548cstep 1\u7684\u65b9\u5f0f\u4e00\u6a21\u4e00\u6837\r\n\r\n\t\t\t\t\t\t\t\/\/ step 1\u548c3\u90fd\u4f1a\u6709\u9012\u5f52\u4ea7\u751f\r\n\t}\r\n}\r\n\r\nint main()\r\n{\r\n\tint n;\r\n\tprintf("\\nPlz input number of the plates:");\r\n\tscanf("%d", &n);\r\n\tprintf("\\nMoving %d plates from A to C:", n);\r\n\r\n\thanoi(n, 'A', 'B', 'C');\r\n\r\n\tprintf("\\nDone!\\n");\r\n}\r\n<\/pre>\n
\u5982\u679c\u4f60\u80fd\u770b\u61c2\u4e0a\u9762\u7684\u6ce8\u91ca\uff0c\u5f88\u597d\u3002\u5982\u679c\u4f60\u770b\u4e0d\u61c2\uff0c\u4e5f\u6ca1\u5173\u7cfb\uff0c\u73b0\u5728\u6211\u4eec\u6765\u8bd5\u7740\u8be6\u7ec6\u70b9\u89e3\u91ca\u8fd9\u4e2a\u95ee\u9898\u3002
\n\u6211\u4eec\u5148\u6765\u73a9\u8fd9\u4e2a\u6e38\u620f\uff0c\u5982\u56fe(\u70b9\u51fb\u56fe\u7247\u770b\u6b63\u5e38\u5927\u56fe)\uff0c
\n\"Towers<\/a>
\n\u4f60\u4f1a\u53d1\u73b0\u76d8\u5b50\u7684\u6570\u91cf\u548c\u6700\u7ec8\u8981\u82b1\u8d39\u7684\u6b65\u6570\u662f\u6709\u5173\u7cfb\u7684\uff0c\u4e3a2^n – 1<\/strong>\uff0c\u4e5f\u5c31\u662f\u8bf4\u53ea\u67091\u4e2a\u76d8\u5b50\u7684\u65f6\u5019\u9700\u89811\u6b65\uff0c2\u4e2a\u76d8\u5b50\u7684\u65f6\u5019\u9700\u89813\u6b65\uff0c3\u4e2a\u76d8\u5b50\u7684\u65f6\u5019\u9700\u89817\u6b65\uff0c\u4ee5\u6b64\u76f4\u5230\u5929\u8352\u5730\u8001\u3002\u3002\u3002<\/p>\n
\u6240\u4ee5\u8fd9\u79cd\u601d\u8def\u6211\u4eec\u662f\u4e0d\u662f\u53ef\u4ee5\u91c7\u7528\u9012\u5f52\u90a3\u5b8c\u6210\u5462\uff1f
\n\u6bd4\u59823\u4e2a\u76d8\u5b50\u7684\u65f6\u5019\uff0c\u6211\u4eec\u5148\u79fb\u52a8\u4e0a\u9762\u76842\u4e2a\u76d8\u5b50(\u9700\u89813\u6b65)\uff0c\u518d\u79fb\u52a8\u6700\u5927\u76841\u4e2a\u76d8\u5b50(\u9700\u89811\u6b65)\uff0c\u7136\u540e\u518d\u79fb\u52a8\u90a32\u4e2a\u76d8\u5b50\u5230\u6700\u5927\u7684\u76d8\u5b50\u4e0a\u9762(\u9700\u89813\u6b65)\uff0c\u52a0\u8d77\u6765\u4e00\u5171\u5c31\u662f7\u6b65\uff0c\u521a\u521a\u597d\u3002
\n\u5e76\u4e142\u4e2a\u76d8\u5b50\u4e5f\u53ef\u4ee5\u540c\u7406\u62c6\u5206\uff0c\u6700\u7ec8\u4f1a\u53d8\u62101\u4e2a\u76d8\u5b50\u7684\u60c5\u51b5\uff0c1\u4e2a\u76d8\u5b50\u7684\u60c5\u51b5\u5f88\u597d\u89e3\u51b3\uff0c\u5c311\u6b65\uff0c\u522b\u4e14\u8fd9\u4e5f\u5c31\u662f\u8fb9\u754c\u60c5\u51b5\u3002<\/p>\n
\u770b\u8d77\u6765\u8fd9\u6837\u662f\u53ef\u4ee5\uff0c\u518d\u56de\u5934\u6765\u770b\u770b\u7a0b\u5e8f\uff0c
\nstep 1 ~ 3\u662f\u4e0d\u662f\u5f88\u6e05\u6670\u4e86\uff0c\u5e76\u4e14step 1\u548c3\u81ea\u5df1\u53c8\u4f1a\u6709\u9012\u5f52\u4ea7\u751f\uff0c\u7ee7\u7eed\u62c6\u5206\uff0c\u76f4\u5230\u6700\u540e\u90fd\u662f1\u4e2a\u76d8\u5b50\u7684\u65f6\u5019\uff0c\u9012\u5f52\u7ed3\u675f\u3002<\/p>\n
\u5982\u679c\u4e0d\u5173\u5fc3\u5185\u90e8\u7ec6\u8282\u662f\u4e0d\u662f\u5c31\u8fd9\u6837\u5b8c\u7f8e\u7ed3\u675f\u4e86\u5462\uff1f\u786e\u5b9e\uff0c\u5982\u679c\u4f60\u4e0d\u5173\u5fc3\u5185\u90e8\u7ec6\u8282\uff0c\u8fd9\u6837\u5df2\u7ecf\u8ba9\u4eba\u5f88\u5bb9\u6613\u7684\u7406\u89e3\u8fd9\u4e2a\u95ee\u9898\u3002\u4f46\u662f\u603b\u5f52\u4f1a\u6709\u4e00\u90e8\u5206\u4eba\u4f1a\u7ee7\u7eed\u6df1\u6316\u3002
\n\u73b0\u5728\u6211\u4eec\u4ee53\u4e2a\u76d8\u5b50\u4e3a\u4f8b\uff0c\u4ee5\u7a0b\u5e8f\u6267\u884c\u7684\u89d2\u5ea6\u6765\u770b\uff0c<\/p>\n
\r\nhanoi(3, 'A', 'B', 'C')\r\n{\r\n\thanoi(2, 'A', 'C', 'B');\r\n\t\thanoi(1, 'A', 'B', 'C')\r\n\t\t\tmove('A', 'C')\r\n\t\tmove('A', 'B')\r\n\t\thanoi(1, 'C', 'A', 'B')\r\n\t\t\tmove('C', 'B')\r\n\tmove('A', 'C');\r\n\thanoi(2, 'B', 'A', 'C');\r\n\t\thanoi(1, 'B', 'C', 'A')\r\n\t\t\tmove('B', 'A')\r\n\t\tmove('B', 'C')\r\n\t\thanoi(1, 'A', 'B', 'C')\r\n\t\t\tmove('A', 'C')\r\n}\r\n<\/pre>\n
\u597d\u50cf\u4e5f\u6ca1\u4ec0\u4e48\u597d\u5199\u7684\uff0c\u6709\u673a\u4f1a\u770b\u770b\u975e\u9012\u5f52\u7684\u65b9\u5f0f\u6765\u5b9e\u73b0\u3002<\/p>\n
P.S.
\n\u9012\u5f52\u6709\u98ce\u9669\uff0c\u4f7f\u7528\u9700\u8c28\u614e\uff01<\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"
\u524d\u5929\u5728\u4e00\u6b21\u9762\u8bd5\u4e2d\uff0c\u9762\u8bd5\u5b98\u95ee\u5230\u6211\u6c49\u8bfa\u5854(Towers of Hanoi)\u7684\u95ee\u9898\uff0c\u5f53\u65f6\u53ea\u77e5\u9053\u662f\u9012\u5f52\uff0c\u77e5\u9053\u624b\u52a8\u73a9\u6e38\u620f\u600e\u4e48\u73a9\uff0c\u5199\u7a0b\u5e8f\u8fd8\u771f\u7684\u5fd8\u8bb0\u4e86\u3002\u5927\u5b66\u6211\u8bb0\u5f97\u662f\u6709\u5199\u8fc7\u8fd9\u6837\u7684\u4f5c\u4e1a\uff0c\u8fd8\u6709\u516b\u7687\u540e\u7b49\u7b49\uff0c\u4e0d\u8fc7\u771f\u7684\u90fd\u8fd8\u7ed9\u8001\u5e08\u4e86\uff0c\u54c8\u54c8\u54c8\uff01 \u7136\u540e\u56de\u5bb6\u770b\u4e86\u4e0b\uff0c http:\/\/www.cs.cmu.edu\/~cburch\/survey\/recurse\/hanoiimpl.html http:\/\/www.python-course.eu\/towers_of_hanoi.php \u6c49\u8bfa\u5854\u7684\u4ecb\u7ecd\u53c2\u89c1http:\/\/en.wikipedia.org\/wiki\/Tower_of_Hanoi\u7b49\u7b49 \u7a0b\u5e8f\u5982\u4e0b\uff0c #include <stdio.h> void move(char src, char dest) { printf("\\nMove the top plate of %c to %c", src, dest); } void hanoi(int n, char a, char b, char c) { if (n == 1) { \/\/ \u9012\u5f52\u7ed3\u675f move(a, c); \/\/ \u6700\u5c0f\u7684\u90a3\u4e2a\u76d8\u5b50 } else { hanoi(n – 1, a, … Continue reading \u6c49\u8bfa\u5854\u6e38\u620f<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_gfmr_meta_descriptions":[],"_gfmr_multilingual_taxonomy_terms":[],"footnotes":""},"categories":[29,8],"tags":[],"class_list":["post-854","post","type-post","status-publish","format-standard","hentry","category-c","category-paste"],"_links":{"self":[{"href":"https:\/\/guoh.ai\/lifelog\/wp-json\/wp\/v2\/posts\/854","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/guoh.ai\/lifelog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/guoh.ai\/lifelog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/guoh.ai\/lifelog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/guoh.ai\/lifelog\/wp-json\/wp\/v2\/comments?post=854"}],"version-history":[{"count":7,"href":"https:\/\/guoh.ai\/lifelog\/wp-json\/wp\/v2\/posts\/854\/revisions"}],"predecessor-version":[{"id":861,"href":"https:\/\/guoh.ai\/lifelog\/wp-json\/wp\/v2\/posts\/854\/revisions\/861"}],"wp:attachment":[{"href":"https:\/\/guoh.ai\/lifelog\/wp-json\/wp\/v2\/media?parent=854"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/guoh.ai\/lifelog\/wp-json\/wp\/v2\/categories?post=854"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/guoh.ai\/lifelog\/wp-json\/wp\/v2\/tags?post=854"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}