{"id":57,"date":"2010-06-14T22:35:36","date_gmt":"2010-06-15T02:35:36","guid":{"rendered":"http:\/\/hw.minilinux.net\/?p=57"},"modified":"2024-09-08T13:34:00","modified_gmt":"2024-09-08T17:34:00","slug":"%e6%af%8f%e6%97%a55%e9%a2%98-0613","status":"publish","type":"post","link":"https:\/\/hw.minilinux.net\/?p=57","title":{"rendered":"\u6bcf\u65e55\u9898–0613"},"content":{"rendered":"

1. \u5355\u94fe\u8868\u5012\u6570\u7b2cN\u4e2a\u8282\u70b9
\n2. template\u4e2d\u7528typename\u548c\u7528class\u6709\u4ec0\u4e48\u533a\u522b\uff1f
\n3. \u624b\u5199fab(n)\u51fd\u6570
\n4. \u4e00\u4e2a\u5927\u697c,10\u5c42,4\u4e2a\u7535\u68af,\u600e\u4e48\u8bbe\u8ba1\u7c7b\u6765\u5b9e\u73b0\u8fd9\u6837\u4e00\u4e2a\u7cfb\u7edf?
\n5. \u591a\u5c11\u4eba\u5728\u4e00\u8d77\uff0c\u751f\u65e5\u53ef\u80fd\u51fa\u73b0\u91cd\u590d\u6982\u7387\u5927\u4e8e0.5\uff1f
\n<\/strong><\/p>\n

1.\u8fd9\u4e2a\u4e0d\u96be, \u8bbe\u7f6e\u4e24\u4e2a\u6307\u9488, \u4e00\u4e2a\u5728\u7b2cN\u4e2a\u8282\u70b9(p2), \u4e00\u4e2a\u5728head\u8282\u70b9(p1), \u7136\u540e\u540c\u6b65\u5411\u524d\u8d70, \u76f4\u5230P2\u5230NULL
\n\u65f6, \u8fd9\u65f6\u5019\u7684p1\u5c31\u662f\u6211\u4eec\u8981\u5bfb\u627e\u7684\u90a3\u4e2a\u8282\u70b9. (\u53ea\u662f\u6ce8\u610f\u8981\u8003\u8651\u4e00\u4e0b\u8fb9\u754c\u6761\u4ef6\u7684\u95ee\u9898\u5c31\u597d\u4e86);
\n2.<\/p>\n

http:\/\/www.csai.cn\u3000\u4f5c\u8005\uff1afatalerror99\u3000\u6765\u6e90\uff1aBLOGCSDN<\/p>\n

\u6ca1\u4ec0\u4e48\u4e0d\u540c\u3002\u5728\u58f0\u660e\u4e00\u4e2a template type parameter\uff08\u6a21\u677f\u7c7b\u578b\u53c2\u6570\uff09\u7684\u65f6\u5019\uff0cclass \u548c typename \u610f\u5473\u7740\u5b8c\u5168\u76f8\u540c\u7684\u4e1c\u897f\u3002\u4e00\u4e9b\u7a0b\u5e8f\u5458\u66f4\u559c\u6b22\u5728\u6240\u6709\u7684\u65f6\u95f4\u90fd\u7528 class\uff0c\u56e0\u4e3a\u5b83\u66f4\u5bb9\u6613\u8f93\u5165\u3002\u5176\u4ed6\u4eba\uff08\u5305\u62ec\u6211\u672c\u4eba\uff09\u66f4\u559c\u6b22 typename\uff0c\u56e0\u4e3a\u5b83\u6697\u793a\u7740\u8fd9\u4e2a\u53c2\u6570\u4e0d\u5fc5\u8981\u662f\u4e00\u4e2a class type\uff08\u7c7b\u7c7b\u578b\uff09\u3002\u5c11\u6570\u5f00\u53d1\u8005\u5728\u4efb\u4f55\u7c7b\u578b\u90fd\u88ab\u5141\u8bb8\u7684\u65f6\u5019\u4f7f\u7528 typename\uff0c\u800c\u628a class \u4fdd\u7559\u7ed9\u4ec5\u63a5\u53d7 user-defined types\uff08\u7528\u6237\u5b9a\u4e49\u7c7b\u578b\uff09\u7684\u573a\u5408\u3002\u4f46\u662f\u4ece C++ \u7684\u89c2\u70b9\u770b\uff0cclass \u548c typename \u5728\u58f0\u660e\u4e00\u4e2a template parameter\uff08\u6a21\u677f\u53c2\u6570\uff09\u65f6\u610f\u5473\u7740\u5b8c\u5168\u76f8\u540c\u7684\u4e1c\u897f\u3002<\/p><\/blockquote>\n

3. \u66fe\u7ecf\u88ab\u95ee\u9053\u8fc7\u8fd9\u9898, \u4e00\u822c\u6709\u4e09\u79cd\u65b9\u6cd5.
\na. \u9012\u5f52 \u65f6\u95f4\u590d\u6742\u5ea6O(2^n)<\/p>\n

int fab(int n)\n{\n      if(n<1) exit(1);\n      if(n==1) return 1;\n   \t  else if(n==2) return 1;\n\t  else return fab(n-1)+fab(n-2);\n}<\/pre>\n
b. Bottom Up \u65f6\u95f4\u590d\u6742\u5ea6O(n)<\/p>\n
int fab(int n)\n{\n\tif(n<1) exit(1);\n\tint a[n];\n\tif(n==1) return 1;\n\telse if (n==2) return 1;\n\ta[0] = 1;\n\ta[1] = 1;\n\tfor(int i=2;i<n;i++)\n              a[i] = a[i-1]+a[i-2];\n       return a[n-1];\n}<\/pre>\n
c. Matrix Multiplication+Divide and Conquer
\n\u53d1\u73b0 fab\u6570\u7ec4\u53ef\u4ee5\u5199\u6210\u77e9\u9635\u76f8\u4e58\u7684\u5f62\u5f0f,
\n\"\left[\begin{matrix}F(n)\\F(n-1)\\\end{matrix}\right]=\left[\begin{matrix}1&1\\1&0\\\end{matrix}\right]\left[\begin{matrix}F(n-1)\\F(n-2)\\\end{matrix}\right]\"<\/p>\n
\u53c8\u56e0\u4e3a \"\left[\begin{matrix}F(2)\\F(1)\end{matrix}\right]=\left[\begin{matrix}1\\1\end{matrix}\right]\"<\/p>\n
\"\left[\begin{matrix}F(n)\\F(n-1)\\\end{matrix}\right]=\left[\begin{matrix}1&1\\1&0\\\end{matrix}\right]^{n-2}\left[\begin{matrix}1\\1\\\end{matrix}\right]\"
\n\u8fd9\u6837\u6211\u4eec\u5c31\u6709<\/p>\n
\u7136\u540e\u6c42\u77e9\u9635\u7684n\u6b21\u65b9,\u53ef\u4ee5\u7528divide and conquer\u6765\u505a, \u8fd1\u4f3c\u8ba4\u4e3a\u53ef\u4ee5\u5728O(log n)\u65f6\u95f4\u505a\u5230,(\u6ce8\u610f\u662f\u8fd1\u4f3c<\/del>), \u6240\u4ee5\u7b2c\u4e09\u79cd\u65b9\u6cd5\u7684\u65f6\u95f4\u662fO(log n) \u8bd5\u60f3\u5728The Da Vinci Code\u91cc\u9762\u7684\u5362\u6d6e\u5bab\u9986\u957fJacques Sauni\u00e8re\u88ab\u8c0b\u6740\u524d\u7528\u4e86O(log(n))\u7684\u65b9\u6cd5\u5199\u51fa\u8fd9\u4e2aFibonacci\u6570\u5217, \u7136\u540e\u591a\u51fa\u6765\u7684\u65f6\u95f4\u518d\u60f3\u60f3\u6709\u6ca1\u6709\u66f4\u597d\u7684\u65b9\u6cd5\u8ba9\u5386\u53f2\u5b66\u5bb6Robert Langdon\u66f4\u5bb9\u6613\u770b\u51fa\u4e8b\u60c5\u7684\u7aef\u502a\u5c31\u597d\u4e86<\/del><\/p>\n
5. \u8fd9\u4e2a\u95ee\u9898\u88ab\u79f0\u4f5c(birthday paradox), \u5927\u6982\u7ed3\u679c\u4f1a\u5f88\u51fa\u4e4e\u4eba\u7684\u610f\u6599\u628a<\/del>, \u505a\u505a\u770b\u5c31\u77e5\u9053\u4e86,<\/p>\n
\u6211\u4eec\u5148\u7b97n\u4e2a\u4eba\u91cc\u9762\u751f\u65e5\u5b8c\u5168\u4e0d\u4e00\u6837\u7684\u6982\u7387, \u5f88\u5bb9\u6613\u53ef\u4ee5\u53d1\u73b0
\n\"T(n) = \frac{A_{364}^{n-1}}{365^{n-1}}\"
\n\u90a3\u4e48\u53ea\u8981\u8ba1\u7b97 1-T(n)>0.5\u6ee1\u8db3\u7684\u6700\u5c0f\u7684n\u503c\u5c31\u597d\u4e86, \u53d1\u73b0 n = 23\u65f6, \u6982\u7387p= 0.507297, \u5373\u662f\u6211\u4eec\u7684\u89e3.<\/p>\n
\u591a\u8bf4\u4e00\u53e5, \u5f53n=50\u7684\u65f6\u5019, p \u5df2\u7ecf\u8fbe\u5230\u4e86\u60ca\u4eba\u76840.970374,\u8bf4\u660e\u57fa\u672c\u4e0a\u572850\u4e2a\u4eba\u4ee5\u4e0a\u7684\u573a\u5408, \u4e00\u5b9a\u4f1a\u6709\u4e24\u4e2a\u4eba\u7684\u751f\u65e5\u662f\u4e00\u6837\u7684, \u8bf6, \u4e0d\u8fc7\u6211\u600e\u4e48\u8bb0\u5f97\u4ee5\u524d\u5199\u540c\u5b66\u5f55\u7684\u65f6\u5019\u6ca1\u4e00\u4e2a\u4eba\u548c\u6211\u751f\u65e5\u4e00\u6837\u7684?<\/del>\u8bf6, \u90a3\u4e2a\u5c5e\u4e8e\u53e6\u4e00\u4e2a\u95ee\u9898\u4e86\u628a…. \u00a0;<\/del><\/p>\n","protected":false},"excerpt":{"rendered":"
1. \u5355\u94fe\u8868\u5012\u6570\u7b2cN\u4e2a\u8282\u70b9 2. template\u4e2d\u7528typename\u548c\u7528class\u6709\u4ec0\u4e48\u533a\u522b\uff1f 3. \u624b\u5199fab(n)\u51fd\u6570 4. \u4e00\u4e2a\u5927\u697c,10\u5c42,4\u4e2a\u7535\u68af,\u600e\u4e48\u8bbe\u8ba1\u7c7b\u6765\u5b9e\u73b0\u8fd9\u6837\u4e00\u4e2a\u7cfb\u7edf? 5. \u591a\u5c11\u4eba\u5728\u4e00\u8d77\uff0c\u751f\u65e5\u53ef\u80fd\u51fa\u73b0\u91cd\u590d\u6982\u7387\u5927\u4e8e0.5\uff1f 1.\u8fd9\u4e2a\u4e0d\u96be, \u8bbe\u7f6e\u4e24\u4e2a\u6307\u9488, \u4e00\u4e2a\u5728\u7b2cN\u4e2a\u8282\u70b9(p2), \u4e00\u4e2a\u5728head\u8282\u70b9(p1), \u7136\u540e\u540c\u6b65\u5411\u524d\u8d70, \u76f4\u5230P2\u5230NULL \u65f6, \u8fd9\u65f6\u5019\u7684p1\u5c31\u662f\u6211\u4eec\u8981\u5bfb\u627e\u7684\u90a3\u4e2a\u8282\u70b9. (\u53ea\u662f\u6ce8\u610f\u8981\u8003\u8651\u4e00\u4e0b\u8fb9\u754c\u6761\u4ef6\u7684\u95ee\u9898\u5c31\u597d\u4e86); 2. http:\/\/www.csai.cn\u3000\u4f5c\u8005\uff1afatalerror99\u3000\u6765\u6e90\uff1aBLOGCSDN \u6ca1\u4ec0\u4e48\u4e0d\u540c\u3002\u5728\u58f0\u660e\u4e00\u4e2a template type parameter\uff08\u6a21\u677f\u7c7b\u578b\u53c2\u6570\uff09\u7684\u65f6\u5019\uff0cclass \u548c typename \u610f\u5473\u7740\u5b8c\u5168\u76f8\u540c\u7684\u4e1c\u897f\u3002\u4e00\u4e9b\u7a0b\u5e8f\u5458\u66f4\u559c\u6b22\u5728\u6240\u6709\u7684\u65f6\u95f4\u90fd\u7528 class\uff0c\u56e0\u4e3a\u5b83\u66f4\u5bb9\u6613\u8f93\u5165\u3002\u5176\u4ed6\u4eba\uff08\u5305\u62ec\u6211\u672c\u4eba\uff09\u66f4\u559c\u6b22 typename\uff0c\u56e0\u4e3a\u5b83\u6697\u793a\u7740\u8fd9\u4e2a\u53c2\u6570\u4e0d\u5fc5\u8981\u662f\u4e00\u4e2a class type\uff08\u7c7b\u7c7b\u578b\uff09\u3002\u5c11\u6570\u5f00\u53d1\u8005\u5728\u4efb\u4f55\u7c7b\u578b\u90fd\u88ab\u5141\u8bb8\u7684\u65f6\u5019\u4f7f\u7528 typename\uff0c\u800c\u628a class \u4fdd\u7559\u7ed9\u4ec5\u63a5\u53d7 user-defined types\uff08\u7528\u6237\u5b9a\u4e49\u7c7b\u578b\uff09\u7684\u573a\u5408\u3002\u4f46\u662f\u4ece C++ \u7684\u89c2\u70b9\u770b\uff0cclass \u548c typename \u5728\u58f0\u660e\u4e00\u4e2a template parameter\uff08\u6a21\u677f\u53c2\u6570\uff09\u65f6\u610f\u5473\u7740\u5b8c\u5168\u76f8\u540c\u7684\u4e1c\u897f\u3002 3. \u66fe\u7ecf\u88ab\u95ee\u9053\u8fc7\u8fd9\u9898, \u4e00\u822c\u6709\u4e09\u79cd\u65b9\u6cd5. a. \u9012\u5f52 \u65f6\u95f4\u590d\u6742\u5ea6O(2^n) int fab(int n) { if(n<1) … Continue reading “\u6bcf\u65e55\u9898–0613”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10],"tags":[12,13,11],"class_list":["post-57","post","type-post","status-publish","format-standard","hentry","category-programming-and-algorithm","tag-birthday-paradox","tag-fibonacci","tag-11"],"_links":{"self":[{"href":"https:\/\/hw.minilinux.net\/index.php?rest_route=\/wp\/v2\/posts\/57","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/hw.minilinux.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/hw.minilinux.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/hw.minilinux.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/hw.minilinux.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=57"}],"version-history":[{"count":66,"href":"https:\/\/hw.minilinux.net\/index.php?rest_route=\/wp\/v2\/posts\/57\/revisions"}],"predecessor-version":[{"id":636,"href":"https:\/\/hw.minilinux.net\/index.php?rest_route=\/wp\/v2\/posts\/57\/revisions\/636"}],"wp:attachment":[{"href":"https:\/\/hw.minilinux.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=57"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/hw.minilinux.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=57"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/hw.minilinux.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=57"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}