{"id":9308,"date":"2016-06-07T23:30:20","date_gmt":"2016-06-08T03:30:20","guid":{"rendered":"http:\/\/cscircles.cemc.uwaterloo.ca\/?page_id=9308"},"modified":"2017-06-28T19:29:14","modified_gmt":"2017-06-28T23:29:14","slug":"zh-18","status":"publish","type":"page","link":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/zh-18\/","title":{"rendered":"18: \u6548\u7387"},"content":{"rendered":"<!-- Please retain this notice and add more notes if you create a new version.<br \/>\nOriginal lesson author: David Pritchard, daveagp@gmail.com, http:\/\/cscircles.ca<br \/>\nLicense: http:\/\/creativecommons.org\/licenses\/by-nc-sa\/3.0\/-->\n<p>\u7f16\u7a0b\u4efb\u52a1\u5f80\u5f80\u6709\u591a\u79cd\u89e3\u51b3\u65b9\u6848\uff0c\u7136\u800c\u4e00\u79cd\u65b9\u6848\u53ef\u80fd\u8fd0\u884c\u901f\u5ea6\u6bd4\u53e6\u4e00\u79cd\u5feb\u3002\u7f16\u5199\u8fd0\u884c\u901f\u5ea6\u5feb\u7684\u7a0b\u5e8f\u4e0d\u4ec5\u9700\u8981\u7f16\u7a0b\u8005\u62e5\u6709\u827a\u672f\u773c\u5149\uff0c\u8fd8\u8981\u62e5\u6709\u575a\u5b9e\u7684\u7f16\u7a0b\u57fa\u7840\u3002\u5728\u4e0b\u5217\u4e60\u9898\u4e2d\u4f1a\u6709\u4e00\u4e9b\u793a\u4f8b\u3002<\/p>\n<h1>\u7b2c1\u90e8\u5206\uff1a\u907f\u514d\u8fdb\u884c\u91cd\u590d\u8ba1\u7b97<\/h1>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Fibonacci_number\">\u6590\u6ce2\u90a3\u5951\u6570\u5217<\/a>\u662f\u4e00\u4e2a\u65e2\u7b80\u5355\u53c8\u5438\u5f15\u4eba\u7684\u6570\u5217\u3002\u524d\u4e24\u9879\u662f1\uff0c1\uff0c<em>\u63a5\u4e0b\u6765\u6bcf\u4e00\u4e2a\u6570\u5b57\u662f\u524d\u4e24\u4e2a\u6570\u5b57\u7684\u548c<\/em>\u3002\u6bd4\u5982\uff0c\u4e0b\u4e00\u4e2a\u6570\u5b57\u662f1+1=2\u3002\u8fd9\u6837\u524d\u4e09\u9879\u5c31\u786e\u5b9a\u4e86\uff0c<\/p>\n<p style=\"text-align: center;\"><code>1, 1, 2<\/code><\/p>\n<p>\u7b2c\u56db\u9879\u662f1+2=3\uff0c\u7136\u540e\u662f2+3=5\uff0c\u4ee5\u6b64\u7c7b\u63a8\uff1a<\/p>\n<p style=\"text-align: center;\"><code>1, 1, 2, 3, 5, 8, 13, ...<\/code><\/p>\n<p>\u6590\u6ce2\u90a3\u5951\u6570\u5217\u539f\u672c\u662f\u7528\u6765\u89e3\u51b3\u5154\u5b50\u6570\u91cf\u7684\u95ee\u9898\uff0c\u4f46\u662f\u8fd8\u548c\u690d\u7269\u5efa\u7b51\u76f8\u5173\u3002\u4e0b\u9762\u662f\u4e00\u4e2a\u6709\u5173\u6590\u6ce2\u90a3\u5951\u6570\u5217\u89c6\u9891\uff1a<div style='text-align: center;'>\n<iframe width='560' height='315' src='https:\/\/www.youtube.com\/embed\/ahXIMUkSXX0?rel=0' frameborder='0' allowfullscreen>\n<\/iframe>\n<\/div>\n<p>\u6590\u6ce2\u90a3\u5951\u6570\u5217\u7684\u5b9a\u4e49\u4f1a\u4ee4\u4eba\u5f88\u81ea\u7136\u5730\u60f3\u5230\u9012\u63a8\u65b9\u7a0b\u3002\u4e0b\u4e00\u4e2a\u7ec3\u4e60\u9898\u5b9a\u4e49\u4e86\u4e00\u4e2a\u65b9\u7a0b<code>Fibonacci(n)<\/code>\uff0c\u8fd4\u8fd8\u4e0a\u8ff0\u5e8f\u5217\u4e2d\u7b2c<code>n<\/code>\u9879\uff08\u4ece<code>n=1<\/code>\u5f00\u59cb\uff09\u3002<\/p>\n<p><form class=\"pbform\" action=\"#\" id=\"pbform0\" method=\"POST\">\n<div class='pybox modeNeutral scramble' id='pybox0'>\n<img title='You have not yet completed this problem.' src='https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Scramble Exercise: <\/span><span class='title'>Nibofacci<\/span><\/div>\u6574\u7406\u8fd9\u4e2a\u7a0b\u5e8f\uff0c\u8fd4\u8fd8\u4e00\u4e2a\u6590\u6ce2\u90a3\u5951\u6570\u5217\u9012\u63a8\u5b9a\u4e49\u3002\u5224\u5206\u7cfb\u7edf\u4f1a\u6253\u5370\u51fa\u5b83\u4eec\u7684\u524d\u5341\u9879\u3002<ul class=\"pyscramble\" name=\"pyscramble\" id=\"pyscramble0\">\n <li class=\"pyscramble\">        return Fibonacci(n-1) + Fibonacci(n-2)<\/li>\n <li class=\"pyscramble\">def Fibonacci(n):<\/li>\n <li class=\"pyscramble\">    else:<\/li>\n <li class=\"pyscramble\">    if (n==1 or n==2):<\/li>\n <li class=\"pyscramble\">        return 1<\/li>\n<\/ul>\n<input type='hidden' id='usercode0' name='usercode0'\/>\n<div id='pbhistory0' class='flexcontain' style='display:none;'><\/div>\n<div name=\"pyinput\" id=\"pyinput0\">Enter testing statements like <code>print(myfunction(\"test argument\"))<\/code> below.<div class=\"pyboxTextwrap resizy\" style=\"height: 102px;\" ><textarea wrap=\"off\" name=\"userinput\" class=\"pyboxInput\" cols=10 rows=4><\/textarea><\/div><\/div>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit0' value=' '\/><\/td>\n<td><input type='button' name='switch' id=\"switch0\" value=\"Input Switch\" onclick=\"pbInputSwitch(0,'Y')\" ><\/td>\n<\/tr><\/table><\/div>\n<input type=\"hidden\" name=\"lang\" value=\"\"\/><input type=\"hidden\" id=\"inputInUse0\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"0\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"771d5db1d831345d1541a0f9df133ac8\"\/>\n<div id='pbresults0' class='pbresults'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>pbInputSwitch(0,\"Y\");<\/script>\n<\/p>\n<p>\u7136\u800c\uff0c\u8fd9\u4e2a\u9012\u63a8\u65b9\u7a0b\u8fd0\u884c\u8d77\u6765\u5f88\u6162\u3002\u70b9\u51fb<strong>\u8f93\u5165\u6d4b\u8bd5\u8bed\u53e5<\/strong>\uff0c\u8f93\u5165<code>print(Fibonacci(80))<\/code>\u3002\u6d4b\u8bd5\u5b83\u65f6\u4f1a\u5f97\u5230\"\u8d85\u51fa\u65f6\u9650\"\u63d0\u793a\u3002<\/p>\n<p>\u4e3a\u4ec0\u4e48\u8fd0\u884c\u5730\u8fd9\u4e48\u6162\uff1f\u56e0\u4e3a\u8fd9\u4e2a\u65b9\u7a0b\u6ca1\u6709\u590d\u6742\u7684\u6307\u793a\u6216\u5faa\u73af\uff0c\u53ea\u6709\u52a0\u6cd5\uff0c\u603b\u5171\u8c03\u7528\u65b9\u7a0b\u7684\u6b21\u6570\u592a\u591a\u3002\u5982\u679c\u6211\u4eec\u8c03\u7528<code>Fibonacci(3)<\/code>\uff0c\u9012\u63a8\u65b9\u7a0b\u603b\u5171\u4f1a\u88ab\u8c03\u7528\u4e09\u6b21\uff1a\u6700\u5f00\u59cb\u7684\u8c03\u7528\uff0c\u7136\u540e\u662f\u4e24\u4e2a\u9012\u63a8\u8c03\u7528\u3002\u5982\u679c\u6211\u4eec\u8c03\u7528<code>Fibonacci(4)<\/code>\uff0c\u9012\u63a8\u65b9\u7a0b\u88ab\u8c03\u7528\u4e86\u4e94\u6b21\uff1a\u6700\u5f00\u59cb\u7684\u8c03\u7528\uff0c\u521a\u521a\u8bb2\u8fc7\u7684\u4e09\u6b21<code>n=3<\/code>\uff0c\u8fd8\u6709\u4e00\u4e2a\u9012\u63a8\u8c03\u7528<code>n=2<\/code>\u3002<code>Fibonacci(5)<\/code>\u603b\u5171\u4f1a\u6709\u4e5d\u6b21\u8c03\u7528\uff0c<code>Fibonacci(6)<\/code>\u4f1a\u67099+5+1=15\u6b21\u8c03\u7528\u3002\u8c03\u7528\u7684\u6b21\u6570\u4f1a\u968f\u7740<code>n<\/code>\u589e\u957f\u800c\u8fc5\u901f\u589e\u957f\uff01<\/p>\n<p>\u7c97\u7565\u4f30\u8ba1\uff0c<code>Fibonacci(n+2)<\/code>\u7684\u8c03\u7528\u6b21\u6570\u81f3\u5c11\u662f<code>Fibonacci(n)<\/code>\u8c03\u7528\u6b21\u6570\u7684\u4e24\u500d\u3002\u56e0\u4e3a<code>Fibonacci(n+2)<\/code>\u76f4\u63a5\u8c03\u7528\u4e00\u6b21<code>Fibonacci(n)<\/code>\uff0c\u8fd8\u6709\u901a\u8fc7\u9012\u63a8\u975e\u76f4\u63a5\u8c03\u7528<code>Fibonacci(n+1)<\/code>\u3002\u6240\u4ee5\u8ba1\u7b97\u65f6\u95f4\u4e0e<em>\u6307\u6570\u51fd\u6570<\/em>\u6210\u6b63\u6bd4\uff0c\u81f3\u5c11\u6709(\u221a2)<sup>n<\/sup>\u8fd9\u4e48\u5927\u3002\u6bd4\u5982\uff0c<code>Fibonacci(80)<\/code>\u9700\u8981\u591a\u4e8e2<sup>40<\/sup> =\u00a01099511627776\u6b21\u9012\u63a8\u8c03\u7528\u3002<\/p>\n<p>\u8fd9\u4e2a\u8bba\u636e\u8fd8\u7565\u8ff0\u4e86\u6982\u5ff5\u6027\u7684\u95ee\u9898\uff1a\u8c03\u7528<code>Fibonacci(n)<\/code>\u4e24\u6b21\uff0c\u4ece\u96f6\u5f00\u59cb\u91cd\u65b0\u8ba1\u7b97\u7ed3\u679c\u592a\u6d6a\u8d39\u65f6\u95f4\u4e86\u3002\u5982\u4f55\u7528\u76f8\u540c\u7684\u65b9\u6cd5\uff0c\u4f46\u662f\u4e0d\u91cd\u590d\u8ba1\u7b97\uff1f<\/p>\n<h2>\u7b54\u6848<\/h2>\n<p>\u8ba9\u6211\u4eec\u8bd5\u8bd5\u7c7b\u4f3c\u4e8e\u4ecb\u7ecd\u4e2d\u6240\u5199\u7684\u4e1c\u897f\u3002\u6211\u4eec\u4ece1, 1\u5f00\u59cb\u3002\u6b64\u540e\uff0c\u6211\u4eec\u628a\u6700\u540e\u4e24\u9879\u76f8\u52a0\u6765\u6269\u5145\u5e8f\u5217\u3002\u4e0b\u9762\u662f\u8fd9\u4e2a\u60f3\u6cd5\u7684\u4ee3\u7801\u5f62\u5f0f\uff0c\u5728\u8fd9\u4e2a\u57fa\u7840\u4e0a\u662f\u5426\u8fdb\u884c\u6574\u7406\u53d6\u51b3\u4e8e\u4f60\u3002<\/p>\n<p><form class=\"pbform\" action=\"#\" id=\"pbform1\" method=\"POST\">\n<div class='pybox modeNeutral scramble' id='pybox1'>\n<img title='You have not yet completed this problem.' src='https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Scramble Exercise: <\/span><span class='title'>Fast Fibonacci<\/span><\/div>\u8ba1\u7b97\u6590\u6ce2\u90a3\u5951\u503c\u7684\u6700\u5feb\u7248\u672c\u3002<ul class=\"pyscramble\" name=\"pyscramble\" id=\"pyscramble1\">\n <li class=\"pyscramble\">    return sequence[n]<\/li>\n <li class=\"pyscramble\">    for i in range(3, n+1):      <\/li>\n <li class=\"pyscramble\">        sequence.append(sequence[i-1] + sequence[i-2])<\/li>\n <li class=\"pyscramble\">    sequence = [0, 1, 1]  # Fibonacci(0) is 0, Fibonacci(1) and Fibonacci(2) are 1<\/li>\n <li class=\"pyscramble\">def Fibonacci(n):<\/li>\n<\/ul>\n<input type='hidden' id='usercode1' name='usercode1'\/>\n<div id='pbhistory1' class='flexcontain' style='display:none;'><\/div>\n<div name=\"pyinput\" id=\"pyinput1\">Enter testing statements like <code>print(myfunction(\"test argument\"))<\/code> below.<div class=\"pyboxTextwrap resizy\" style=\"height: 102px;\" ><textarea wrap=\"off\" name=\"userinput\" class=\"pyboxInput\" cols=10 rows=4><\/textarea><\/div><\/div>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit1' value=' '\/><\/td>\n<td><input type='button' name='switch' id=\"switch1\" value=\"Input Switch\" onclick=\"pbInputSwitch(1,'Y')\" ><\/td>\n<\/tr><\/table><\/div>\n<input type=\"hidden\" name=\"lang\" value=\"\"\/><input type=\"hidden\" id=\"inputInUse1\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"1\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"142dda911985eef1c235b123ab62a5ad\"\/>\n<div id='pbresults1' class='pbresults'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>pbInputSwitch(1,\"Y\");<\/script>\n<\/p>\n<p>\u56e0\u4e3a\u4e0d\u9700\u8981\u6bcf\u6b21\u8c03\u7528\u7684\u65f6\u5019\u91cd\u65b0\u8ba1\u7b97\u6574\u4e2a\u6570\u7ec4\uff0c\u6240\u4ee5\u5728\u8fd9\u4e2a\u57fa\u7840\u4e0a\u8fd8\u6709\u63d0\u5347\u7684\u7a7a\u95f4\u3002\u4f46\u662f\u8fd9\u4e2a\u7248\u672c\u5c31\u80fd\u591f\u6ee1\u8db3\u6211\u4eec\u7684\u8981\u6c42\uff0cn\u503c\u5f88\u5927\u7684\u65f6\u5019\u8fd0\u884c\u4e5f\u5f88\u5feb\uff01<\/p>\n<h1>\u7b2c2\u90e8\u5206\uff1a\u907f\u514d\u8ba1\u7b97\u4e0d\u91cd\u8981\u7684\u4e8b\u60c5\uff0c\u4e00\u6b21\u4e5f\u4e0d\u8981<\/h1>\n<p>\u7b2c\u4e8c\u4e2a\u4f8b\u5b50\u662f\u5173\u4e8e\u68c0\u67e5\u6570\u5b57\u662f\u5426\u662f<strong>\u8d28\u6570<\/strong>\uff0c\u8fd9\u5728\u52a0\u5bc6\u548c\u8ba1\u7b97\u673a\u5b89\u5168\u65b9\u9762\u975e\u5e38\u91cd\u8981\u3002\u5982\u679c\u4e00\u4e2a\u6570\u53ea\u6709\u4e24\u4e2a\u56e0\u5b50\uff1a1\u548c\u5b83\u672c\u8eab\uff0c\u90a3\u4e48\u8fd9\u4e2a\u6570\u5b57\u662f\u8d28\u6570\u3002\u4ece1\u5f00\u59cb\u7684\u51e0\u4e2a\u8d28\u6570\u662f2\uff0c3\uff0c5\uff0c7\uff0c11\uff0c13\uff0c17\uff0c19\uff0c23\uff0821\u4e0d\u662f\u8d28\u6570\u56e0\u4e3a\u9664\u4e86\u662f1\u548c21\u5916\uff0c21\u8fd8\u6709\u56e0\u5b503\u548c7\uff09\u3002<\/p>\n<p>Python\u4e2d\u5982\u4f55\u6d4b\u8bd5\u4e00\u4e2a\u6570\u5b57\u662f\u5426\u662f\u8d28\u6570\uff1f\u6211\u4eec<a href=\"\/7b-math\/\">\u4e4b\u524d<\/a>\u8bb2\u8fc7\u5982\u4f55\u6d4b\u8bd5\u6574\u9664\u6027\uff1a<\/p>\n<p style=\"text-align: center;\"><code>N % D == 0 \u00a0# will be True if D is a divisor of N, False otherwise<\/code><\/p>\n<p>\u4e0b\u5217\u7a0b\u5e8f\u6d4b\u8bd5\u6240\u6709\u53ef\u80fd\u7684\u56e0\u5b50\u3002<\/p>\n<p><form class=\"pbform\" action=\"#\" id=\"pbform2\" method=\"POST\">\n<div class='pybox modeNeutral  facultative' id='pybox2'>\n<div class=\"heading\"><span class=\"title\">Example<\/span><\/div>\u6d4b\u8bd5\u6570\u5b57\u662f\u5426\u662f\u8d28\u6570<div class='pyboxTextwrap pyboxCodewrap RO '  style='height: 162px;'><textarea wrap='off' name='usercode2' id='usercode2'  cols=10 rows=6 readonly='readonly'  style = 'height : 162px;'  class='pyboxCode RO'>\ndef isItPrime(N):\n  for D in range(2, N):                        # \u6d4b\u8bd5 D \u4ece 2 \u5230 N-1\n    if N % D == 0:                             # D\u662fN\u7684\u9664\u6570\u4e48?\n      print(N, \"is not prime; divisible by\", D)\n      return\n  print(N, \"is prime\")                         # \u6ca1\u6709\u9664\u6570<\/textarea><\/div>\n<div id='pbhistory2' class='flexcontain' style='display:none;'><\/div>\n<div name=\"pyinput\" id=\"pyinput2\">Enter testing statements like <code>print(myfunction(\"test argument\"))<\/code> below.<div class=\"pyboxTextwrap resizy\" style=\"height: 102px;\" ><textarea wrap=\"off\" name=\"userinput\" class=\"pyboxInput\" cols=10 rows=4><\/textarea><\/div><\/div>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit2' value=' '\/><\/td>\n<td><input type='button' name='switch' id=\"switch2\" value=\"Input Switch\" onclick=\"pbInputSwitch(2,'Y')\" ><\/td>\n<td><input type='button' name='consolecopy' value=\"Open in console\" onclick=\"pbConsoleCopy(2)\" ><\/td>\n<td><input type='button' name='visualize' value=\"Visualize\" onclick=\"pbVisualize(2,'Y')\" ><\/td>\n<\/tr><\/table><\/div>\n<input type=\"hidden\" name=\"lang\" value=\"\"\/><input type=\"hidden\" id=\"inputInUse2\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"2\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"eda848303afc01dc79302029288651b2\"\/>\n<div id='pbresults2' class='pbresults'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>pbInputSwitch(2,\"Y\");<\/script>\n<\/p>\n<p>\u8fd9\u4e2a\u7a0b\u5e8f\u53ef\u4ee5\u6ee1\u8db3\u6211\u4eec\u7684\u8981\u6c42\uff01\u4f46\u662f\u5982\u679c\u6570\u5b57\u5f88\u5927\uff0c\u8fd9\u4e2a\u7a0b\u5e8f\u4e5f\u4f1a\u5f88\u6162\u3002\u9009<strong>\u8f93\u5165<\/strong>\uff0c\u8f93\u5165<code>isItPrime(324635459)<\/code>\u3002\u4f60\u4f1a\u5f97\u5230\u8d85\u51fa\u65f6\u95f4\u9650\u5236\u7684\u63d0\u793a\u3002\u5c1d\u8bd5\u66f4\u591a\u7684\u503c\u2026\u2026\u5bf9\u4e8e\u5927\u4e8e10000000\u7684\u8d28\u6570\uff0c\u8fd9\u4e2a\u4ee3\u7801\u603b\u662f\u8d85\u51fa\u65f6\u95f4\u9650\u5236\uff0c\u6253\u5206\u5668\u53ea\u80fd\u4ee5\u6bcf\u79d2\u4e00\u5343\u4e07\u6b21\u7684\u901f\u5ea6\u8fdb\u884c\u6574\u9664\u6027\u68c0\u67e5\u5faa\u73af\u3002\u5982\u679c\u60f3\u68c0\u67e5\u6bd4\u8f83\u5927\u7684\u6570\u5b57\uff0c\u6211\u4eec\u9700\u8981\u5176\u4ed6\u66f4\u6709\u6548\u7387\u7684\u60f3\u6cd5\u3002\u8ba9\u6211\u4eec\u628a\u4ee3\u7801\u53d8\u5f97\u66f4\u6709\u6548\uff0c\u53ef\u4ee5\u5904\u7406\u5341\u4ebf\u4ee5\u4e0a\u7684\u6570\u5b57\uff01<\/p>\n<p>\u662f\u5426\u6709\u5fc5\u8981\u68c0\u67e5<strong>\u6240\u6709<\/strong>\u7684\u6570\u5b57\uff0c<code>2<\/code>\u548c<code>N-1<\/code>\u4e4b\u95f4\uff0c\u4ee5\u67e5\u770b<code>N<\/code>\u662f\u5426\u662f\u8d28\u6570\uff1f<a class=\"hintlink\"  id=\"hintlink3\">\u63d0\u793a<\/a><\/p>\n<h2>\u4e3b\u610f\u548c\u53c2\u6570<\/h2>\n<p>\u5982\u679c\u4f60\u9605\u8bfb\u4e86\u63d0\u793a\u6216\u8005\u8fdb\u884c\u4e86\u591a\u6b21\u5c1d\u8bd5\uff0c\u4f60\u53ef\u80fd\u4f1a\u6ce8\u610f\u5230\u5f53<code>N<\/code>\u4e0d\u662f\u8d28\u6570\uff0c\u8fd9\u4e2a\u7a0b\u5e8f\u901a\u5e38\u80fd\u627e\u5230\u4e00\u4e2a\u4e0e<code>N<\/code>\u76f8\u6bd4\u76f8\u5f53\u5c0f\u7684\u56e0\u6570\u3002\u6bd4\u5982\uff0c<code>isItPrime(34827948723948723984729834)<\/code>\u8fd0\u884c\u5730\u975e\u5e38\u5feb\uff1a\u5c3d\u7ba1\u6570\u5b57\u5f88\u5927\uff0c\u4f46\u627e\u5230\u7684\u56e0\u5b50\u5374\u662f<code>D=2<\/code>\u3002<\/p>\n<p>\u6216\u8bb8\u6211\u4eec\u4e0d\u9700\u8981\u68c0\u67e5\u6240\u6709\u7684\u56e0\u5b50\u3002\u4f46\u662f\u662f\u5426\u6709\u4e00\u4e9b\u56e0\u5b50\u6211\u4eec\u4e00\u5b9a\u8981\u68c0\u67e5\uff0c\u7136\u540e\u624d\u53ef\u4ee5\u786e\u5b9a<code>N<\/code>\u662f\u8d28\u6570\uff1f\u6ca1\u9519\uff01\u5b9e\u9645\u4e0a\uff0c\u6211\u4eec\u53ef\u4ee5\u8ba4\u4e3a<em>\u5982\u679c<\/em><code>N<\/code><em>\u4e0d\u662f\u8d28\u6570\uff0c\u5b83\u7684\u8d28\u6570\u6700\u5927\u4e0d\u8d85\u8fc7<\/em><code>sqrt(N)<\/code>\u3002\u4e3a\u4ec0\u4e48\uff1f\u56e0\u4e3a\u5982\u679c<code>N<\/code>\u4e0d\u662f\u8d28\u6570\uff0c\u90a3\u4e48\u5b83\u5c31\u6709\u4e00\u4e2a\u56e0\u5b50<code>A<\/code>\u3002\u4f5c\u4e3a\u4e00\u4e2a\u56e0\u5b50\u5c31\u610f\u5473\u7740\u8fd8\u6709\u53e6\u4e00\u4e2a\u6570\u5b57B\uff0c\u4f7f\u5f97<\/p>\n<p style=\"text-align: center;\"><code>A*B == N<\/code><\/p>\n<p>\u8ba9\u6211\u4eec\u7ee7\u7eed\u8bba\u8bc1\u3002\u5982\u679c<code>A &lt;= sqrt(N)<\/code>\u6216<code>B &lt;= sqrt(N)<\/code>\uff0c\u90a3\u4e48\u7686\u5927\u6b22\u559c\uff1a\u6211\u4eec\u627e\u5230\u4e86<code>N<\/code>\u7684\u4e00\u4e2a\u6bd4\u8f83\u5c0f\u7684\u56e0\u5b50\u3002\u5b9e\u9645\u4e0a\u8fd9\u91cc\u53ea\u6709\u8fd9\u4e9b\u53ef\u80fd\uff1a\u5426\u5219\uff0c\u6211\u4eec\u5c31\u4f1a\u5f97\u5230\u77db\u76fe<\/p>\n<p style=\"text-align: center;\"><code>N = A*B &gt; sqrt(N)*sqrt(N) &gt; N<\/code><\/p>\n<p>\u90a3\u4e48\u73b0\u5728\uff0c\u8ba9\u6211\u4eec\u5728Python\u4e2d\u65bd\u884c\u8fd9\u4e2a\u65b0\u7684\u4e3b\u610f\u3002\u6539\u53d8\u65e7\u65b9\u6cd5\u7684\u6700\u7b80\u5355\u7684\u65b9\u6cd5\u662f\u5728<code>for<\/code>\u5faa\u73af\u4e2d\u52a0\u5165\u4e00\u4e2a\u6d4b\u8bd5\uff1a\u4e00\u65e6<code>D &gt; sqrt(N)<\/code>\uff08\u6216\u8005<code>D*D &gt; N<\/code>\uff09\uff0c\u53ef\u4ee5\uff08<code>break<\/code>\uff09\u8df3\u51fa\u5faa\u73af\uff0c\u505c\u6b62\u6d4b\u8bd5\u3002<\/p>\n<p><form class=\"pbform\" action=\"#\" id=\"pbform4\" method=\"POST\">\n<div class='pybox modeNeutral  facultative' id='pybox4'>\n<div class=\"heading\"><span class=\"title\">Example<\/span><\/div>\u8fd0\u884c\u901f\u5ea6\u66f4\u5feb\u7684\u8d28\u6570\u6d4b\u8bd5<div class='pyboxTextwrap pyboxCodewrap RO '  style='height: 292px;'><textarea wrap='off' name='usercode4' id='usercode4'  cols=10 rows=11 readonly='readonly'  style = 'height : 292px;'  class='pyboxCode RO'>\ndef isItPrime(N): # \u548c\u4e4b\u524d\u7684\u4e00\u6837\n  for D in range(2, N):\n    if (D * D > N):          # \u88ab\u52a0\u4e0a\u7684\u7b2c\u4e00\u884c\n      break                  # \u88ab\u67b6\u4e0a\u7684\u7b2c\u4e8c\u884c\n    if N % D == 0:\n      print(N, \"is not prime; divisible by\", D)\n      return\n  print(N, \"is prime\")\n\nisItPrime(1000006000009)\nisItPrime(1666666009999)<\/textarea><\/div>\n<div id='pbhistory4' class='flexcontain' style='display:none;'><\/div>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit4' value=' '\/><\/td>\n<td><input type='button' name='consolecopy' value=\"Open in console\" onclick=\"pbConsoleCopy(4)\" ><\/td>\n<td><input type='button' name='visualize' value=\"Visualize\" onclick=\"pbVisualize(4,'N')\" ><\/td>\n<\/tr><\/table><\/div>\n<input type=\"hidden\" name=\"lang\" value=\"\"\/><input type=\"hidden\" id=\"inputInUse4\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"4\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"f7f41e06fbf5289cb5549afc15a550d7\"\/>\n<div id='pbresults4' class='pbresults'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>document.getElementById(\"submit4\").value = \"Run program\";document.getElementById(\"inputInUse4\").value = \"N\";<\/script>\n<\/p>\n<p>\u8fd9\u4e2a\u7a0b\u5e8f\u53ef\u4ee5\u5904\u7406\u5f88\u5927\u7684\u8d28\u6570\uff01<\/p>\n<h2>\u6700\u540e\u7684\u7ec3\u4e60\u9898<\/h2>\n<p>\u5728\u8fd9\u4e2a\u7ec3\u4e60\u4e2d\uff0c\u6211\u4eec\u5c06\u8fd9\u8282\u8bfe\u540e\u534a\u90e8\u5206\u7684\u8d28\u6570\u4e0e\u5e8f\u5217\u4e3a\u6838\u5fc3\u7684\u524d\u534a\u90e8\u5206\u7ed3\u5408\u3002\u4f60\u7684\u4ee3\u7801\u5e94\u8be5\u80fd\u591f\u586b\u5199\u4e00\u4e2a\u957f\u4e3a1000001\u8868\u683c\uff0c\u4f7f\u5f97\u5982\u679c<code>N<\/code>\u662f\u8d28\u6570<code>isPrime[N]<\/code>\u7b49\u4e8e<code>True<\/code>\uff1b\u5982\u679c<code>N<\/code>\u662f\u5408\u6570\uff0c\u5c31\u662f<code>False<\/code>\u3002\u5728\u8fd9\u91cc<code>N<\/code>\u5c0f\u4e8e\u7b49\u4e8e\u4e00\u767e\u4e07\uff08\u6bd4\u5982\uff0c<code>isPrime[0]<\/code>\u548c<code>isPrime[1]<\/code>\u5e94\u4e3a<code>False<\/code>\uff09\u3002<\/p>\n<p><a class=\"hintlink\"  id=\"hintlink5\">\u70b9\u51fb\u8fd9\u91cc\u67e5\u770b\u63d0\u793a\u3002\u5f88\u91cd\u8981\uff01<\/a><\/p>\n<p><form class=\"pbform\" action=\"#\" id=\"pbform6\" method=\"POST\">\n<div class='pybox modeNeutral ' id='pybox6'>\n<img title='You have not yet completed this problem.' src='https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Coding Exercise: <\/span><span class='title'>Primed for Takeoff<\/span><\/div>\u7f16\u5199\u6211\u4eec\u4e0a\u8ff0\u63cf\u8ff0\u7684\u7a0b\u5e8f<code>isPrime<\/code>\uff08\u6ce8\u610f<code>isPrime<\/code>\u662f\u4e00\u4e2a\u5e8f\u5217\uff0c\u4e0d\u662f\u65b9\u7a0b\uff09\u3002<a class=\"hintlink\"  id=\"hintlink7\">\u63d0\u793a<\/a><br\/> <em>\u5224\u65ad\u5668\u65f6\u95f4\u9650\u5236\u662f<strong>7\u79d2<\/strong>\uff0c\u4ee5\u786e\u4fdd\u4f60\u7684\u7a0b\u5e8f\u8fd0\u884c\u6210\u529f\u3002\u7136\u800c\uff0c\u5355\u72ec\u4f7f\u7528<\/em><code>isItPrime<\/code><em>\u65b9\u7a0b\u8fd8\u4e0d\u591f\u5feb\u3002<\/em><div class=\"helpOuter\" style=\"display: none;\"><div class=\"helpInner\"><div style=\"text-align: center\">You need to create an account and log in to ask a question.<\/div><\/div><\/div><div class='pyboxTextwrap pyboxCodewrap RW resizy'  style='height: 526px;'><textarea wrap='off' name='usercode6' id='usercode6'  cols=10 rows=20   class='pyboxCode RW'>\n<\/textarea><\/div>\n<div id='pbhistory6' class='flexcontain' style='display:none;'><\/div>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit6' value=' '\/><\/td>\n<td><input type='button' name='consolecopy' value=\"Open in console\" onclick=\"pbConsoleCopy(6)\" ><\/td>\n<td><input type='button' name='visualize' value=\"Visualize\" onclick=\"pbVisualize(6,'Y')\" ><\/td>\n<td><input type='button' name='history' value=\"History\" onclick=\"historyClick(6,'18.sieve')\" ><\/td>\n<\/tr><\/table><select id='pbSelect6' class='selectmore'><option name='more'>More actions...<\/option>\n<option name='help' data-pbonclick=\"helpClick(6);\" >Help<\/option>\n<\/select><\/div>\n<input type='hidden' name='timeout' value='20000'\/>\n<input type=\"hidden\" name=\"lang\" value=\"\"\/><input type=\"hidden\" id=\"inputInUse6\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"6\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"60d3615e367a5b1fa6db3c1c3a0676e4\"\/>\n<div id='pbresults6' class='pbresults avoidline'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>jQuery(function(){pbToggleCodeMirror(6);});document.getElementById(\"submit6\").value = \"Run program\";document.getElementById(\"inputInUse6\").value = \"N\";<\/script>\n<\/p>\n<p><table class='pywarn'><tr><td class='pywarnleft'><img src='https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-content\/plugins\/pybox\/files\/warning.png'\/><\/td><td class='pywarnright'><span> \u8fd9\u662fCS Circles\u7f51\u7ad9\u6700\u540e\u7684\u7ec3\u4e60\u9898\u3002\u606d\u559c\u5b8c\u6210\u6240\u6709\u8bfe\u7a0b\u7684\u540c\u5b66\uff01\u67e5\u770b<a class=\"open-same-window\" href=\"\/resources\/\">resources page<\/a>\uff0c\u91cc\u9762\u6709\u4e9b\u5efa\u8bae\u544a\u8bc9\u4f60\u63a5\u4e0b\u6765\u53ef\u4ee5\u5b66\u4ec0\u4e48\u3002\u5e0c\u671b\u4f60\u53ef\u4ee5\u4ece\u4e2d\u627e\u5230\u4e50\u8da3\uff0c\u7f16\u5199\u51fa\u597d\u7a0b\u5e8f\uff01\u795d\u4f60\u597d\u8fd0\uff01 <\/span><\/td><\/table><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u7f16\u7a0b\u4efb\u52a1\u5f80\u5f80\u6709\u591a\u79cd\u89e3\u51b3\u65b9\u6848\uff0c\u7136\u800c\u4e00\u79cd\u65b9\u6848\u53ef\u80fd\u8fd0\u884c\u901f\u5ea6\u6bd4\u53e6\u4e00\u79cd\u5feb\u3002\u7f16\u5199\u8fd0\u884c\u901f\u5ea6\u5feb\u7684\u7a0b\u5e8f\u4e0d\u4ec5\u9700\u8981\u7f16\u7a0b\u8005\u62e5\u6709\u827a\u672f\u773c\u5149\uff0c\u8fd8\u8981\u62e5\u6709\u575a\u5b9e\u7684\u7f16\u7a0b\u57fa\u7840\u3002\u5728\u4e0b\u5217\u4e60\u9898\u4e2d\u4f1a\u6709\u4e00\u4e9b\u793a\u4f8b\u3002 \u7b2c1\u90e8\u5206\uff1a\u907f\u514d\u8fdb\u884c\u91cd\u590d\u8ba1\u7b97 \u6590\u6ce2\u90a3\u5951\u6570\u5217\u662f\u4e00\u4e2a\u65e2\u7b80\u5355\u53c8\u5438\u5f15\u4eba\u7684\u6570\u5217\u3002\u524d\u4e24\u9879\u662f1\uff0c1\uff0c\u63a5\u4e0b\u6765\u6bcf\u4e00\u4e2a\u6570\u5b57\u662f\u524d\u4e24\u4e2a\u6570\u5b57\u7684\u548c\u3002\u6bd4\u5982\uff0c\u4e0b\u4e00\u4e2a\u6570\u5b57\u662f1+1=2\u3002\u8fd9\u6837\u524d\u4e09\u9879\u5c31\u786e\u5b9a\u4e86\uff0c 1, 1, 2 \u7b2c\u56db\u9879\u662f1+2=3\uff0c\u7136\u540e\u662f2+3=5\uff0c\u4ee5\u6b64\u7c7b\u63a8\uff1a 1, 1, 2, 3, 5, 8, 13, ... \u6590\u6ce2\u90a3\u5951\u6570\u5217\u539f\u672c\u662f\u7528\u6765\u89e3\u51b3\u5154\u5b50\u6570\u91cf\u7684\u95ee\u9898\uff0c\u4f46\u662f\u8fd8\u548c\u690d\u7269\u5efa\u7b51\u76f8\u5173\u3002\u4e0b\u9762\u662f\u4e00\u4e2a\u6709\u5173\u6590\u6ce2\u90a3\u5951\u6570\u5217\u89c6\u9891\uff1a \u6590\u6ce2\u90a3\u5951\u6570\u5217\u7684\u5b9a\u4e49\u4f1a\u4ee4\u4eba\u5f88\u81ea\u7136\u5730\u60f3\u5230\u9012\u63a8\u65b9\u7a0b\u3002\u4e0b\u4e00\u4e2a\u7ec3\u4e60\u9898\u5b9a\u4e49\u4e86\u4e00\u4e2a\u65b9\u7a0bFibonacci(n)\uff0c\u8fd4\u8fd8\u4e0a\u8ff0\u5e8f\u5217\u4e2d\u7b2cn\u9879\uff08\u4ecen=1\u5f00\u59cb\uff09\u3002 Scramble Exercise: Nibofacci\u6574\u7406\u8fd9\u4e2a\u7a0b\u5e8f\uff0c\u8fd4\u8fd8\u4e00\u4e2a\u6590\u6ce2\u90a3\u5951\u6570\u5217\u9012\u63a8\u5b9a\u4e49\u3002\u5224\u5206\u7cfb\u7edf\u4f1a\u6253\u5370\u51fa\u5b83\u4eec\u7684\u524d\u5341\u9879\u3002 def Fibonacci(n): return Fibonacci(n-1) + Fibonacci(n-2) else: return 1 if (n==1 or n==2): Enter testing statements like print(myfunction(\"test argument\")) below. &hellip; <a href=\"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/zh-18\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-9308","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/pages\/9308","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/comments?post=9308"}],"version-history":[{"count":16,"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/pages\/9308\/revisions"}],"predecessor-version":[{"id":10242,"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/pages\/9308\/revisions\/10242"}],"wp:attachment":[{"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/media?parent=9308"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}