{"id":2358,"date":"2014-03-27T11:29:16","date_gmt":"2014-03-27T03:29:16","guid":{"rendered":"http:\/\/kuki.idv.tw\/?p=2358"},"modified":"2014-03-27T11:29:29","modified_gmt":"2014-03-27T03:29:29","slug":"%e8%bd%89%e5%85%a9%e5%80%8b%e4%bf%9d%e9%bd%a1%e7%90%83%e7%9a%84%e6%95%85%e4%ba%8b","status":"publish","type":"post","link":"https:\/\/www.kuki.idv.tw\/?p=2358","title":{"rendered":"[\u8f49]\u5169\u500b\u4fdd\u9f61\u7403\u7684\u6545\u4e8b"},"content":{"rendered":"

\u4f86\u6e90 http:\/\/www.kimicat.com\/Home\/bowlingball<\/p>\n

\u5fc3\u5f97\uff1a\u5e38\u5e38\uff0c\u6211\u5011\u60f3\u8981\u53bb\u5c0b\u6c42\u6700\u4f73\u7684\u89e3\u6c7a\u65b9\u6cd5\uff0c\u4f46\u5f80\u5f80\u6211\u5011\u4e0d\u77e5\u9053\u7d50\u679c\uff0c\u4f46\u6211\u5011\u53ef\u4ee5\u9810\u6e2c\uff0c\u4f9d\u7167\u6211\u5011\u4ee5\u5f80\u7684\u7d93\u9a57\uff0c\u800c\u8a8d\u77e5\u89e3\u6c7a\u7684\u65b9\u5f0f\u3002<\/span>
\n\u5169\u9846\u4fdd\u9f61\u7403\uff0c\u5f9e\u5e7e\u6a13\u4e1f\u4e0b\u6703\u7834\u6389\uff0c\u4f9d\u65e5\u5e38\u7d93\u9a57\u4f86\u8aaa\uff0c\u78ba\u5be6\u5f88\u6709\u53ef\u80fd\u4e0d\u77e5\u9053\uff0c\u5fc5\u9700\u53bb\u6e2c\u8a66\u624d\u77e5\u9053\u3002\u5982\u4f55\u4f5c\u6700\u6709\u6548\u7684\u6642\u9593\uff0c\u78ba\u5be6\u4e5f\u662f\u4e00\u500b\u53ef\u4ee5\u601d\u8003\u7684\u554f\u984c\u3002<\/span><\/p>\n

 <\/p>\n

###################################################<\/p>\n

\u9019\u662f\u4e4b\u524d\u5728\u7db2\u8def\u4e0a\u770b\u5230\u7684\u4e00\u500b\u6578\u5b78\u554f\u984c\u3002\u984c\u76ee\u5f88\u7c21\u55ae\uff1a\u5047\u8a2d\u4f60\u6709\u5169\u500b\u5b8c\u5168\u76f8\u540c\u7684\u4fdd\u9f61\u7403\uff0c\u73fe\u5728\u4f60\u60f3\u8981\u6e2c\u8a66\u9019\u7a2e\u4fdd\u9f61\u7403\u53ef\u4ee5\u627f\u53d7\u5f9e\u591a\u9ad8\u7684\u9ad8\u5ea6\u6389\u843d\u800c\u4e0d\u6703\u640d\u58de\u3002\u5728\u4f60\u7684\u8eab\u65c1\u6709\u4e00\u68df 100 \u5c64\u6a13\u7684\u9ad8\u6a13\uff0c\u4f60\u53ef\u4ee5\u5f9e\u4efb\u4f55\u4e00\u5c64\u6a13\uff0c\u628a\u4fdd\u9f61\u7403\u4e1f\u4e0b\u53bb\uff0c\u770b\u770b\u5b83\u6703\u4e0d\u6703\u58de\u6389\u3002\u540c\u6642\uff0c\u4f60\u4e5f\u53ef\u4ee5\u5047\u8a2d\uff0c\u5982\u679c\u4fdd\u9f61\u7403\u5728\u67d0\u4e00\u5c64\u6a13\u4e1f\u4e0b\u53bb\u6703\u7834\u640d\uff0c\u5247\u540c\u6a23\u7684\u4fdd\u9f61\u7403\u5f9e\u66f4\u9ad8\u7684\u6a13\u5c64\u4e1f\u4e0b\u53bb\u4e5f\u4e00\u5b9a\u6703\u7834\u640d\u3002\u53e6\u4e00\u65b9\u9762\uff0c\u5982\u679c\u5f9e\u67d0\u4e00\u5c64\u6a13\u4e1f\u4e0b\u53bb\u4e0d\u6703\u7834\u640d\uff0c\u5247\u5f9e\u66f4\u4f4e\u7684\u6a13\u5c64\u4e1f\u4e0b\u53bb\uff0c\u4e5f\u4e0d\u6703\u7834\u640d\u3002\u53e6\u5916\uff0c\u5982\u679c\u4fdd\u9f61\u7403\u4e1f\u4e0b\u53bb\u800c\u7834\u640d\u5f8c\uff0c\u5c31\u5b8c\u5168\u4e0d\u80fd\u518d\u7528\u5b83\u4f86\u9032\u884c\u4efb\u4f55\u9032\u4e00\u6b65\u7684\u6e2c\u8a66\u3002\u9664\u6b64\u4e4b\u5916\uff0c\u4f60\u6c92\u8fa6\u6cd5\u5f9e\u4efb\u4f55\u5176\u5b83\u7684\u65b9\u5f0f\u53d6\u5f97\u4efb\u4f55\u8cc7\u8a0a\u3002\u73fe\u5728\uff0c\u8981\u8acb\u4f60\u8a2d\u8a08\u4e00\u500b\u65b9\u6cd5\uff0c\u53ef\u4ee5\u7528\u6700\u5c11\u7684\u6b21\u6578\uff0c\u77e5\u9053\u9019\u7a2e\u4fdd\u9f61\u7403\uff0c\u6700\u9ad8\u53ef\u4ee5\u627f\u53d7\u5f9e\u7b2c\u5e7e\u5c64\u6a13\u4e1f\u4e0b\u53bb\u800c\u4e0d\u6703\u7834\u640d\uff1f<\/p>\n

\n
<\/div>\n
\u5f88\u660e\u986f\u7684\uff0c\u5982\u679c\u53ea\u6709\u4e00\u500b\u4fdd\u9f61\u7403\u7684\u8a71\uff0c\u552f\u4e00\u7684\u65b9\u6cd5\uff0c\u5c31\u662f\u5f9e\u4e8c\u6a13\u958b\u59cb\u4e1f\u3002\u5982\u679c\u5f9e\u4e8c\u6a13\u4e1f\u4e0b\u53bb\u4e0d\u7834\uff0c\u5c31\u5f9e\u4e09\u6a13\u4e1f\u2026\u4f9d\u6b64\u985e\u63a8\uff0c\u76f4\u5230\u5f9e 100 \u6a13\u7684\u6a13\u9802\uff08\u7b49\u65bc\u662f 101 \u6a13\uff09\u70ba\u6b62\u3002\u9019\u6a23\u7684\u65b9\u6cd5\uff0c\u6700\u591a\u9700\u8981\u4e1f 100 \u6b21\u3002\u7576\u7136\uff0c\u73fe\u5728\u6709\u5169\u500b\u4fdd\u9f61\u7403\uff0c\u6240\u4ee5\u7b2c\u4e8c\u500b\u4fdd\u9f61\u7403\u61c9\u8a72\u53ef\u4ee5\u6709\u4e9b\u7528\u8655\u3002<\/div>\n
<\/div>\n
\u5f9e\u53e6\u4e00\u500b\u89d2\u5ea6\u601d\u8003\uff0c\u9019\u500b\u554f\u984c\u4f3c\u4e4e\u53ef\u4ee5\u7528\u985e\u4f3c\u300c\u4e8c\u5206\u641c\u5c0b\u6cd5\u300d\u4f86\u8655\u7406\u3002\u4f8b\u5982\uff0c\u53ef\u4ee5\u5148\u5f9e 50 \u6a13\u4e1f\u4e0b\u53bb\uff0c\u5982\u679c\u6c92\u7834\uff0c50 \u6a13\u4ee5\u4e0b\u7684\u5c31\u90fd\u4e0d\u7528\u518d\u6e2c\u8a66\u4e86\u3002\u5982\u679c\u7834\u4e86\uff0c50 \u6a13\u4ee5\u4e0a\u7684\u5c31\u4e0d\u9700\u8981\u6e2c\u8a66\u4e86\u3002\u4e0d\u5e78\u7684\u662f\uff0c\u56e0\u70ba\u53ea\u6709\u5169\u500b\u4fdd\u9f61\u7403\uff0c\u6240\u4ee5\u5982\u679c 50 \u6a13\u4e1f\u4e0b\u53bb\u7834\u4e86\uff0c\u90a3\u5c31\u53ea\u80fd\u4e56\u4e56\u7684\u5f9e\u4e8c\u6a13\u4e00\u76f4\u6e2c\u5230 49 \u6a13\u4e86\u3002\u6240\u4ee5\uff0c\u9019\u6a23\u505a\u7684\u8a71\uff0c\u6700\u591a\u9700\u8981\u4e1f 50 \u6b21\u3002\u76f8\u5c0d\u7684\uff0c\u5982\u679c\u7b2c\u4e00\u6b21\u4e1f\u6c92\u7834\uff0c\u90a3\u4e0b\u4e00\u6b21\u53ef\u4ee5\u5728 75 \u6a13\u4e1f\uff0c\u4f9d\u6b64\u985e\u63a8\u3002<\/div>\n
<\/div>\n
\u5f9e\u4e0a\u9762\u7684\u7d50\u679c\u4f86\u770b\uff0c\u4f3c\u4e4e\u4e00\u958b\u59cb\u4e0d\u61c9\u8a72\u5f9e 50 \u6a13\u958b\u59cb\u4e1f\uff0c\u800c\u61c9\u8a72\u9078\u64c7\u6bd4\u8f03\u4f4e\u7684\u6a13\u5c64\u624d\u5c0d\u3002\u6bd4\u5982\u8aaa\uff0c\u5982\u679c\u5f9e 11 \u6a13\u958b\u59cb\u4e1f\uff0c\u5982\u679c\u7834\u4e86\uff0c\u5c31\u5f9e\u4e8c\u6a13\u8a66\u5230\u5341\u6a13\u3002\u5982\u679c\u6c92\u7834\uff0c\u4e0b\u6b21\u5c31\u5f9e 21 \u6a13\u958b\u59cb\u4e1f\uff0c\u7834\u4e86\u5c31\u8a66 12 \u81f3 20 \u6a13\uff0c\u6c92\u7834\u518d\u5f9e 31 \u6a13\u958b\u59cb\uff0c\u4f9d\u6b64\u985e\u63a8\u3002\u9019\u6a23\u4e00\u4f86\uff0c\u6700\u5dee\u7684\u60c5\u5f62\u662f\u4e1f\u5230 91 \u6a13\u6c92\u7834\uff0c\u4f46 101 \u6a13\u6642\u7834\u4e86\uff0c\u6240\u4ee5\u518d\u5f9e 92 \u6a13\u4e1f\u5230 100 \u6a13\u3002\u4e5f\u5c31\u662f\u8aaa\uff0c\u7e3d\u5171\u9700\u8981\u4e1f 19 \u6b21\u3002<\/div>\n
<\/div>\n
\u9019\u6a23\u5df2\u7d93\u6bd4\u4e00\u958b\u59cb\u8981\u597d\u5f97\u591a\u4e86\uff0c\u4f46\u662f\u6709\u6c92\u6709\u8fa6\u6cd5\u8b93\u5b83\u8b8a\u5f97\u66f4\u597d\u5462\uff1f\u4e8b\u5be6\u4e0a\uff0c\u4e0a\u9762\u8aaa\u7684\u5f9e 11 \u6a13\u958b\u59cb\uff0c\u5b8c\u5168\u662f\u4e00\u500b\u96a8\u4fbf\u6c7a\u5b9a\u7684\u6578\u5b57\u3002\u4e5f\u8a31\u53ef\u4ee5\u8a08\u7b97\u51fa\u4e00\u500b\u66f4\u597d\u7684\u6578\u5b57\uff0c\u4f8b\u5982\u4e5f\u8a31\u5f9e 15 \u6a13\u4e1f\u6703\u66f4\u597d\u3002\u8981\u8a08\u7b97\u51fa\u6700\u597d\u7684\u6578\u5b57\u662f\u591a\u5c11\uff0c\u53ef\u4ee5\u8a08\u7b97\u5982\u679c\u4e00\u958b\u59cb\u5f9e n + 1 \u6a13\u958b\u59cb\uff0c\u4e26\u6bcf\u6b21\u63d0\u9ad8 n \u6a13\uff0c\u6700\u591a\u6703\u9700\u8981\u4e1f\u591a\u5c11\u6b21\uff1f<\/div>\n
<\/div>\n
\u5982\u679c\u7e3d\u6a13\u5c64\u6578\u662f N\uff0c\u90a3\u6700\u5dee\u7684\u60c5\u5f62\u662f\u8981\u5148\u4e1f N \/ n \u6b21\uff0c\u6700\u5f8c\u4e00\u6b21\u7834\u6389\uff0c\u56e0\u6b64\u518d\u52a0\u4e0a n – 1 \u6b21\uff0c\u5373<\/div>\n
<\/div>\n
N \/ n + n – 1<\/div>\n
<\/div>\n
\u8981\u6700\u4f73\u5316\u9019\u500b\u503c\uff0c\u53ef\u4ee5\u628a\u5b83\u5fae\u5206\uff0c\u5f97\u5230 -N \/ n2\u00a0+ 1 = 0\uff0c\u5373 n = sqrt(N)\u3002\u6240\u4ee5\uff0c\u5728 100 \u5c64\u6a13\u7684\u60c5\u5f62\uff0c\u525b\u597d\u662f\u4e00\u6b21\u8df3 10 \u5c64\u6a13\u6700\u597d\u3002<\/div>\n
<\/div>\n
\u4e0d\u904e\uff0c\u518d\u56de\u5230\u524d\u9762\u4e8c\u5206\u641c\u5c0b\u6cd5\u7684\u60f3\u6cd5\uff0c\u4f3c\u4e4e\u4e0d\u4e00\u5b9a\u8981\u6bcf\u6b21\u8df3\u4e00\u500b\u56fa\u5b9a\u7684\u6a13\u5c64\u6578\u3002\u7531\u65bc\u6bcf\u6b21\u4e1f\u4e00\u500b\u7403\u6c92\u7834\uff0c\u5c31\u7b49\u65bc\u591a\u6e2c\u8a66\u4e00\u6b21\uff0c\u6240\u4ee5\uff0c\u4e5f\u8a31\u53ef\u4ee5\u8003\u616e\u6bcf\u6b21\u8df3\u7684\u6a13\u5c64\u6578\u90fd\u6e1b\u4e00\u3002\u6bd4\u5982\u8aaa\uff0c\u4e00\u958b\u59cb\u5f9e 15 \u6a13\u4e1f\uff0c\u5982\u679c\u7834\u4e86\uff0c\u5c31\u8981\u518d\u4e1f 2 ~ 14 \u6a13\uff0c\u52a0\u8d77\u4f86\u5171 14 \u6b21\u3002\u6240\u4ee5\uff0c\u5982\u679c\u6c92\u7834\u7684\u8a71\uff0c\u4e0b\u6b21\u61c9\u8a72\u8981\u5728 15 + 13 = 28 \u6a13\u4e1f\u3002\u56e0\u70ba\u5982\u679c\u5f9e 28 \u6a13\u4e1f\u7834\u4e86\uff0c\u518d\u4e1f 16 ~ 27 \u6a13\uff0c\u52a0\u8d77\u4f86\u4e5f\u662f 14 \u6b21\u3002\u5982\u679c\u6c92\u7834\uff0c\u518d\u5f9e 28 + 12 = 40 \u6a13\u4e1f\uff0c\u4f9d\u6b64\u985e\u63a8\u3002<\/div>\n
<\/div>\n
\u9019\u6a23\u4e1f\u7684\u8a71\uff0c\u5982\u679c\u6709 N \u6a13\uff0c\u90a3\u9ebc\u4e00\u958b\u59cb\u4e1f\u7684\u6a13\u5c64\uff0c\u61c9\u8a72\u5c31\u662f\u8981\u9078\u64c7 1 + 2 + 3 + 4 + … + n >= N \u7684\u6a13\u5c64\u30021 + 2 + 3 + … + n = n (n+1) \/ 2\uff0c\u6240\u4ee5<\/div>\n
<\/div>\n
n (n + 1) \/ 2 >= N<\/div>\n
-> n2\u00a0+ n – 2N >= 0<\/div>\n
-> n >= (-1 + sqrt(1 + 8N)) \/ 2<\/div>\n
<\/div>\n
N = 100 \u7684\u6642\u5019\uff0cn >= 13.65\uff0c\u4e5f\u5c31\u662f\u61c9\u8a72\u5f9e 14+1 \u5373 15 \u6a13\u958b\u59cb\u3002\u9019\u6a23\u6700\u591a\u8981\u4e1f 14 \u6b21\u3002<\/div>\n
<\/div>\n
\u6709\u6c92\u6709\u53ef\u80fd\u505a\u5230\u66f4\u597d\u5462\uff1f\u770b\u8d77\u4f86\u4f3c\u4e4e\u662f\u4e0d\u592a\u53ef\u80fd\uff0c\u56e0\u70ba\u5982\u679c\u5f9e\u9ad8\u65bc 15 \u6a13\u958b\u59cb\u4e1f\uff08\u4f8b\u5982 16 \u6a13\uff09\uff0c\u90a3\u4e00\u958b\u59cb\u5c31\u7834\u6389\u7684\u8a71\uff0c\u5c31\u8981\u4e1f 2 ~ 15 \u6a13\uff0c\u90a3\u5c31\u8981\u4e1f 15 \u6b21\uff0c\u5c31\u8d85\u904e\u76ee\u524d\u6700\u4f73\u7684 14 \u6b21\u4e86\u3002\u53e6\u4e00\u65b9\u9762\uff0c\u5982\u679c\u5f9e\u4f4e\u65bc 15 \u6a13\uff08\u4f8b\u5982 14 \u6a13\uff09\u958b\u59cb\u4e1f\uff0c\u5f8c\u9762\u5c31\u7121\u6cd5\u300c\u88dc\u4e0a\u300d\u800c\u4e00\u5b9a\u6703\u8d85\u904e 14 \u6b21\u3002\u56e0\u6b64\uff0c\u9019\u61c9\u8a72\u662f\u6700\u4f73\u89e3\u4e86\u3002<\/div>\n
<\/div>\n
\u73fe\u5728\uff0c\u5169\u500b\u4fdd\u9f61\u7403\u7684\u554f\u984c\uff0c\u5df2\u7d93\u6709\u4e86\u597d\u7684\u89e3\u7b54\u3002\u90a3\u9ebc\uff0c\u5982\u679c\u6709\u4e09\u500b\uff0c\u6216\u66f4\u591a\u500b\u4fdd\u9f61\u7403\u6642\uff0c\u53c8\u6703\u5982\u4f55\u5462\uff1f<\/div>\n
<\/div>\n
\u5f88\u660e\u986f\u7684\uff0c\u5982\u679c\u5920\u591a\u500b\u4fdd\u9f61\u7403\uff0c\u5c31\u53ef\u4ee5\u76f4\u63a5\u4f7f\u7528\u4e8c\u5206\u641c\u5c0b\u6cd5\uff0c\u6700\u591a\u9700\u8981\u4e1f 7 \u6b21\uff0827\u00a0= 128 > 100\uff09\u3002\u9019\u6a23\u9700\u8981 7 \u500b\u4fdd\u9f61\u7403\u3002\u4f46\u662f\uff0c\u5982\u679c\u6c92\u9019\u9ebc\u591a\u500b\u4fdd\u9f61\u7403\uff0c\u8981\u600e\u9ebc\u8fa6\u5462\uff1f<\/div>\n
<\/div>\n
\u5047\u8a2d\u73fe\u5728\u6709\u4e09\u500b\u4fdd\u9f61\u7403\uff0c\u53ef\u4ee5\u6ce8\u610f\u5230\u4e00\u9ede\uff1a\u5047\u8a2d\u5f9e n \u6a13\u958b\u59cb\u4e1f\uff0c\u800c\u5b83\u7834\u4e86\u3002\u9019\u6642\uff0c\u5c31\u5269\u4e0b\u5169\u500b\u4fdd\u9f61\u7403\uff0c\u4e5f\u5c31\u662f\u8aaa\uff0c\u5c0d\u65bc\u5269\u4e0b\u7684\u6a13\u5c64\uff08n + 1 ~ 100 \u6a13\uff09\uff0c\u9019\u500b\u554f\u984c\u7b49\u65bc\u662f\u8b8a\u6210\u5169\u500b\u4fdd\u9f61\u7403\u7684\u554f\u984c\u3002\u5982\u679c\u5b83\u6c92\u7834\uff0c\u90a3\u9ebc\uff0c\u9019\u500b\u554f\u984c\u5c31\u6703\u8b8a\u6210 n – 1 \u6a13\u5c64\u7684\u4e09\u500b\u4fdd\u9f61\u7403\u7684\u554f\u984c\u3002\u4e5f\u5c31\u662f\u8aaa\uff0c\u5982\u679c\u8a2d F(m, N) \u662f m \u500b\u4fdd\u9f61\u7403\u5728 N \u5c64\u6a13\u7684\u60c5\u5f62\u4e0b\u6700\u591a\u9700\u8981\u4e1f\u7684\u6b21\u6578\uff0c\u90a3\u9ebc\uff0c\u5982\u679c\u4e00\u958b\u59cb\u5f9e n + 1 \u6a13\u958b\u59cb\u4e1f\uff0c\u5247<\/div>\n
<\/div>\n
F(m, N) = max( F(m, n – 1), F(m – 1, N – n) ) + 1<\/div>\n
<\/div>\n
\u8981\u627e\u5230\u300c\u6700\u4f73\u89e3\u300d\uff0c\u53ef\u4ee5\u628a n \u5f9e 1 \u8a66\u5230 N\uff0c\u627e\u51fa\u6700\u5c0f\u7684 F(m, N)\u3002\u9019\u500b\u554f\u984c\u53ef\u4ee5\u7528 dynamic programming \u4f86\u89e3\u3002\u56e0\u70ba\uff0c\u5df2\u7d93\u77e5\u9053 F(1, N) = N\uff0c\u800c\u4e14 F(m, 1) = 1\uff0c\u6240\u4ee5\u5c0d\u6bcf\u500b F(m, N)\uff0c\u53ef\u4ee5\u5f9e F(m, 2)\u3001F(m, 3)\u3001\u2026\u4e00\u76f4\u8a08\u7b97\u5230 F(m, N)\u3002<\/div>\n
<\/div>\n
\u8209\u500b\u4f8b\u5b50\u4f86\u8aaa\uff0c\u5047\u8a2d\u60f3\u8981\u8a08\u7b97 F(2, 2)\uff0c\u628a n \u5f9e 1 \u8a66\u5230 2\uff1a<\/div>\n
<\/div>\n
n = 1: F(2, 2) = max( F(2, 0), F(1, 1) ) + 1 = 2<\/div>\n
n = 2: F(2, 2) = max( F(2, 1), F(1, 0) ) + 1 = 2<\/div>\n
<\/div>\n
\u6709\u4e86 F(2, 2)\uff0c\u5c31\u53ef\u4ee5\u8a08\u7b97 F(2, 3)\uff1a<\/div>\n
<\/div>\n
n = 1: F(2, 3) = max( F(2, 0), F(1, 2) ) + 1 = 3<\/div>\n
n = 2: F(2, 3) = max( F(2, 1), F(1, 1) ) + 1 = 2<\/div>\n
n = 3: F(2, 3) = max( F(2, 2), F(1, 0) ) + 1 = 3<\/div>\n
<\/div>\n
\u6240\u4ee5\u53ef\u4ee5\u77e5\u9053 F(2, 3) = 2\u3002\u63a5\u8457\uff0c\u5c31\u53ef\u4ee5\u8a08\u7b97 F(2, 4)\uff1a<\/div>\n
<\/div>\n
n = 1: F(2, 4) = max( F(2, 0), F(1, 3) ) + 1 = 4<\/div>\n
n = 2: F(2, 4) = max( F(2, 1), F(1, 2) ) + 1 = 3<\/div>\n
n = 3: F(2, 4) = max( F(2, 2), F(1, 1) ) + 1 = 3<\/div>\n
n = 4: F(2, 4) = max( F(2, 3), F(1, 0) ) + 1 = 3<\/div>\n
<\/div>\n
\u4e5f\u5c31\u662f\u8aaa F(2, 4) = 3\u3002<\/div>\n
<\/div>\n
\u9019\u53ef\u4ee5\u5f88\u5bb9\u6613\u7684\u5beb\u4e00\u500b\u7a0b\u5f0f\u4f86\u89e3\u3002<\/div>\n
<\/div>\n
\u4e0d\u904e\uff0c\u9019\u6a23\u4f86\u89e3\u9019\u500b\u554f\u984c\uff0c\u4f3c\u4e4e\u9084\u4e0d\u662f\u6700\u7406\u60f3\u7684\u3002\u900f\u904e dynamic programming \u65b9\u5f0f\uff0c\u5982\u679c\u9047\u5230 N \u6216 m \u90fd\u975e\u5e38\u5927\u7684\u60c5\u6cc1\uff0c\u53ef\u80fd\u6703\u9700\u8981\u76f8\u7576\u9577\u7684\u6642\u9593\u624d\u80fd\u8a08\u7b97\u51fa\u7d50\u679c\u3002<\/div>\n
<\/div>\n
\u53e6\u4e00\u500b\u65b9\u6cd5\uff0c\u662f\u53cd\u904e\u4f86\u8003\u616e\uff1a\u5982\u679c\u6709 m \u500b\u4fdd\u9f61\u7403\uff0c\u6700\u591a\u4e1f n \u6b21\u7684\u60c5\u5f62\u4e0b\uff0c\u53ef\u4ee5\u300c\u61c9\u4ed8\u300d\u6700\u591a\u5230\u591a\u5c11\u6a13\u5c64\u5462\uff1f\u6bd4\u5982\u8aaa\uff0c\u5047\u8a2d\u5169\u500b\u4fdd\u9f61\u7403\u7684\u60c5\u5f62\uff0c\u6700\u591a\u4e1f 5 \u6b21\u7684\u8a71\uff0c\u90a3\u6700\u591a\u53ef\u4ee5\u6709\u5e7e\u6a13\uff1f\u9019\u53ef\u4ee5\u9019\u6a23\u4f86\u8003\u616e\uff1a\u9996\u5148\uff0c\u7b2c\u4e00\u6b21\u4e1f\uff0c\u5fc5\u7136\u662f\u5728 6 \u6a13\uff08\u5373\u4e94\u6a13\u7684\u6a13\u9802\uff09\uff0c\u56e0\u70ba\u5982\u679c 6 \u6a13\u4e1f\u800c\u7834\u4e86\uff0c\u90a3\u63a5\u4e0b\u4f86\u8981\u4e1f 2 ~ 5 \u6a13\uff0c\u52a0\u8d77\u4f86\u5171 5 \u6b21\u3002\u5982\u679c\u6c92\u7834\u7684\u8a71\uff0c\u5247\u5f9e\u516d\u6a13\u958b\u59cb\uff0c\u5c31\u662f\u9084\u6709\u5169\u500b\u7403\u7684\u60c5\u5f62\u4e0b\uff0c\u9084\u53ef\u4ee5\u518d\u4e1f 4 \u6b21\u3002\u56e0\u6b64\uff0c\u53ef\u4ee5\u628a\u5b83\u5beb\u6210\uff1a<\/div>\n
<\/div>\n
P(2, 5) = P(1, 4) + 1 + P(2, 4)<\/div>\n
<\/div>\n
\u6216\u662f\u4e00\u822c\u5316\u4f86\u8aaa\uff1a<\/div>\n
<\/div>\n
P(m, n) = P(m – 1, n – 1) + 1 + P(m, n – 1)<\/div>\n
<\/div>\n
\u9019\u540c\u6a23\u662f\u4e00\u500b\u905e\u5efb\u5f0f\uff0c\u4f46\u662f\u6bd4 dynamic programming \u7684\u65b9\u5f0f\u55ae\u7d14\u591a\u4e86\u3002\u7531\u65bc\u5df2\u7d93\u77e5\u9053 P(1, n) = n\uff08\u5373\u82e5\u53ea\u6709\u4e00\u500b\u7403\uff0c\u4e1f n \u6b21\u7684\u8a71\uff0c\u6700\u591a\u53ea\u80fd\u61c9\u4ed8\u5230 n \u6a13\u7684\u60c5\u5f62\uff09\uff0c\u6240\u4ee5<\/div>\n
<\/div>\n
P(2, n) = n – 1 + 1 + P(2, \u00a0n – 1)<\/div>\n
-> P(2, n) – P(2, n-1) = n<\/div>\n
<\/div>\n
\u6240\u4ee5 P(2, n) = n(n+1)\/2\uff0c\u4e5f\u5c31\u662f\u524d\u9762\u8a0e\u8ad6\u904e\u7684\u7d50\u679c\u3002<\/div>\n
<\/div>\n
\u540c\u7406\uff0c\u53ef\u4ee5\u63a8\u5c0e P(3, n):<\/div>\n
<\/div>\n
P(3, n) = P(2, n – 1) + 1 + P(3, n – 1)<\/div>\n
-> P(3, n) – P(3, n-1) \u00a0= n(n-1)\/2 + 1<\/div>\n
-> P(3, n) = (n-1)n(n+1)\/6 + n<\/div>\n
<\/div>\n
\u4ee5 100 \u5c64\u6a13\u7684\u554f\u984c\u4f86\u8aaa\uff0c\u56e0\u70ba P(3, 8) = 92 \u800c P(3, 9) = 129\uff0c\u56e0\u6b64\u53ef\u4ee5\u77e5\u9053\u4e09\u500b\u7403\u7684\u6642\u5019\u6700\u591a\u8981\u4e1f 9 \u6b21\u3002<\/div>\n
<\/div>\n
\u63a8\u5ee3\u4e0b\u53bb\uff0c\u53ef\u4ee5\u5f97\u5230<\/div>\n
<\/div>\n
P(m, n) = C(n + 1, m) + C(n + 1, m – 2) + C(n + 1, m – 4) + … – 1<\/div>\n
<\/div>\n
C(m, n) \u662f\u7d44\u5408\u6578\uff0c\u5373 C(m, n) = m!\/n!(m-n)!<\/div>\n
<\/div>\n
\u5f9e\u9019\u500b\u7d50\u679c\uff0c\u4e5f\u53ef\u4ee5\u63a8\u5c0e\u51fa\u4e00\u4e9b\u7d50\u8ad6\uff0c\u4f8b\u5982\uff1a<\/div>\n
<\/div>\n
\u5c0d\u6240\u6709 m >= n\uff0cP(m, n) = 2n\u00a0– 1<\/div>\n
<\/div>\n
\u8b49\u660e\u5982\u4e0b\uff1a<\/div>\n
<\/div>\n
\u4f7f\u7528\u6578\u5b78\u6b78\u7d0d\u6cd5\u3002\u8a2d m >= n = 1\uff0c\u5247 P(m, n) = P(m, 1) = 21\u00a0– 1 \u6210\u7acb\u3002<\/div>\n
\u73fe\u5728\u8a2d m >= n = k \u6642 P(m, n) = P(k, k) = 2k\u00a0– 1 \u6210\u7acb\uff0c\u5247<\/div>\n
m >= n = k + 1 \u6642\uff0cP(m, n) = P(k + 1, k + 1) = P(k, k) + 1 + P(k + 1, k) = 2k\u00a0– 1 + 1 + 2k\u00a0– 1 = 2k+1\u00a0– 1 \u4e5f\u6210\u7acb\u3002<\/div>\n
\u56e0\u6b64 m >= n \u6642\uff0cP(m, n) = 2n\u00a0– 1\u3002<\/div>\n
<\/div>\n
\u9019\u500b\u7d50\u679c\u5176\u5be6\u662f\u5341\u5206\u5408\u7406\u7684\uff0c\u56e0\u70ba\u7576\u4f7f\u7528\u4e8c\u5206\u641c\u5c0b\u6cd5\u6642\uff0c\u9032\u884c n \u6b21\u6bd4\u8f03\uff0c\u6700\u591a\u53ea\u80fd\u8655\u7406\u5230 2n\u00a0– 1 \u7b46\u8cc7\u6599\u3002\u5728\u9019\u500b\u554f\u984c\u4e2d\uff0c\u7576\u4fdd\u9f61\u7403\u6578\u76ee\u548c\u9700\u8981\u4e1f\u7684\u6b21\u6578\u4e00\u6a23\u6216\u66f4\u591a\u6642\uff08\u7403\u66f4\u591a\u986f\u7136\u4e0d\u6703\u6709\u4ec0\u9ebc\u5e6b\u52a9\uff09\uff0c\u7406\u8ad6\u4e0a\u53ef\u4ee5\u76f4\u63a5\u4f7f\u7528\u4e8c\u5206\u641c\u5c0b\u6cd5\uff0c\u56e0\u6b64\u6700\u591a\u53ea\u53ef\u4ee5\u61c9\u4ed8 2n\u00a0– 1 \u6a13\u5c64\u3002<\/div>\n
<\/div>\n

<\/a>\u5e73\u884c\u5316\u7248\u672c<\/h3>\n

\u5728\u4e0a\u9762\u7684\u554f\u984c\u4e2d\uff0c\u6211\u5011\u8003\u616e\u7684\u662f\u4e00\u6b21\u4e1f\u4e00\u500b\u7403\u3002\u4f46\u662f\uff0c\u5982\u679c\u540c\u6642\u53ef\u4ee5\u4e1f\u597d\u5e7e\u500b\u7403\uff0c\u90a3\u60c5\u5f62\u5c31\u6703\u4e0d\u592a\u4e00\u6a23\u4e86\u3002\u6bd4\u5982\u8aaa\uff0c\u5047\u8a2d\u6709\u5169\u500b\u4eba\uff0c\u548c\u5169\u500b\u4fdd\u9f61\u7403\uff0c\u6a13\u5c64\u6578\u662f\u5169\u5c64\u3002\u6309\u7167\u6b63\u5e38\u7684\u4e1f\u6cd5\uff0c\u9700\u8981\u4e1f\u5169\u6b21\uff1a2 \u6a13\u548c 3 \u6a13\u5404\u4e1f\u4e00\u6b21\uff0c\u9806\u5e8f\u5012\u6c92\u4ec0\u9ebc\u5dee\u5225\u3002\u4f46\u662f\uff0c\u6709\u5169\u500b\u4eba\u7684\u6642\u5019\uff0c\u5176\u5be6\u53ef\u4ee5\u540c\u6642\u5728 2 \u6a13\u548c 3 \u6a13\u4e1f\u3002\u5982\u679c\u9019\u6a23\u7b97\u662f\u300c\u4e00\u6b21\u300d\u7684\u8a71\uff0c\u90a3\u9ebc\u5c31\u6709\u53ef\u80fd\u9700\u8981\u4e1f\u7684\u6b21\u6578\u53ef\u4ee5\u6e1b\u5c11\u3002\u67d0\u500b\u89d2\u5ea6\u4f86\u8aaa\uff0c\u9019\u7b97\u662f\u539f\u554f\u984c\u7684\u300c\u5e73\u884c\u5316\u300d\u3002<\/p>\n

\u53ef\u4ee5\u540c\u6642\u4e1f\u5169\u500b\u7403\uff0c\u80fd\u5e36\u4f86\u591a\u5927\u5e6b\u52a9\u5462\uff1f\u9664\u4e86\u6700\u660e\u986f\u7684\u5169\u5c64\u6a13\u7684\u7248\u672c\u4e4b\u5916\uff0c\u5176\u5b83\u6a13\u5c64\u6578\u4e5f\u662f\u6703\u6709\u5e6b\u52a9\u7684\u3002\u4f8b\u5982\uff0c\u4e94\u5c64\u6a13\u7684\u60c5\u5f62\uff0c\u5982\u679c\u5169\u500b\u7403\u53ef\u4ee5\u540c\u6642\u4e1f\u7684\u8a71\uff0c\u6700\u591a\u53ea\u9700\u8981\u4e1f\u5169\u6b21\uff1a<\/p>\n

\u4e00\u958b\u59cb\uff0c\u4e1f 2 \u548c 4 \u6a13\u3002
\n\u5982\u679c 2 \u6a13\u7834\u4e86\uff08\u7576\u7136 4 \u6a13\u4e5f\u6703\u7834\uff09\uff0c\u5247\u8868\u793a\u5f9e 2 \u6a13\u4e1f\u5c31\u6703\u7834\u3002
\n\u5982\u679c 2 \u6a13\u6c92\u7834\uff0c\u4f46 4 \u6a13\u7834\u4e86\uff0c\u5c31\u5f9e 3 \u6a13\u4e1f\uff08\u53ea\u5269\u4e00\u9846\u7403\uff09\u3002
\n\u5982\u679c 2 \u6a13\u548c 4 \u6a13\u90fd\u6c92\u7834\uff0c\u5247\u540c\u6642\u4e1f 5 \u548c 6 \u6a13\u3002<\/p>\n

\u5229\u7528\u524d\u9762\u7684\u65b9\u6cd5\uff0c\u7576\u6709 m \u500b\u7403\u53ef\u4ee5\u540c\u6642\u4e1f\u7684\u6642\u5019\uff0c\u53ef\u4ee5\u5f97\u5230\uff1a<\/p>\n

R(m, 1) = m<\/p>\n

\u4e5f\u5c31\u662f\u53ea\u4e1f\u4e00\u6b21\u6642\uff0cm \u500b\u7403\u53ef\u4ee5\u61c9\u4ed8 m \u5c64\u6a13\uff08\u5373\u6bcf\u5c64\u6a13\u90fd\u540c\u6642\u4e1f\uff09\u3002<\/p>\n

\u53ef\u4ee5\u4e1f\u5169\u6b21\u6642\uff0c\u53ef\u4ee5\u9019\u6a23\u770b\uff1a<\/p>\n

2 \u6a13\u4e00\u5b9a\u8981\u4e1f\uff0c\u56e0\u70ba\u53ef\u80fd\u6bcf\u500b\u7403\u90fd\u6703\u7834\u3002
\n\u5982\u679c 2 \u6a13\u6c92\u7834\uff0c\u4f46\u5176\u5b83\u90fd\u7834\u4e86\uff0c\u5c31\u5269\u4e00\u500b\u7403\uff0c\u56e0\u6b64\u53ef\u4ee5\u300c\u7a7a\u4e00\u6a13\u300d\uff0c\u5373 3 \u6a13\u53ef\u4ee5\u5148\u4e0d\u4e1f\uff0c\u4e0b\u4e00\u500b\u7403\u61c9\u8a72\u5f9e 4 \u6a13\u4e1f\u3002
\n\u5982\u679c 4 \u6a13\u4e5f\u6c92\u7834\uff0c\u4f46\u5176\u5b83\u90fd\u7834\u4e86\uff0c\u90a3\u6703\u5269\u5169\u500b\u7403\uff0c\u56e0\u6b64\u53ef\u4ee5\u7a7a R(2, 1) \u6a13\u3002
\n\u4f9d\u6b64\u985e\u63a8\u2026<\/p>\n

\u6240\u4ee5\u53ef\u4ee5\u5f97\u5230<\/p>\n

R(m, 2) = 1 + R(1, 1) + 1 + R(2, 1) + 1 + R(3, 1) + 1 + … + R(m, 1)<\/p>\n

\u4f8b\u5982<\/p>\n

R(2, 2) = 1 + R(1, 1) + 1 + R(2, 1) = 1 + 1 + 1 + 2 = 5<\/p>\n

\u4e00\u822c\u5316\u7684\u8a71\uff0c\u5c31\u662f<\/p>\n

R(m, n) = 1 + R(1, n – 1) + 1 + R(2, n – 1) + 1 + R(3, n – 1) + 1 + … + R(m, n – 1)
\n-> R(m, n) = R(1, n – 1) + R(2, n – 1) + … + R(m, n – 1) + m<\/p>\n

\u9019\u88e1\u53ef\u4ee5\u770b\u5230\u4e00\u4ef6\u5f88\u6709\u610f\u601d\u7684\u4e8b\u60c5\uff1a<\/p>\n

R(m – 1, n) = R(1, n – 1) + R(2, n – 1) + … + R(m -1, n – 1) + m – 1<\/p>\n

\u6240\u4ee5<\/p>\n

R(m, n) = R(m – 1, n) + R(m, n – 1) + 1<\/p>\n

\u548c\u300c\u975e\u5e73\u884c\u7248\u300d\u7684\u905e\u5efb\u5f0f\u985e\u4f3c\uff0c\u4f46\u662f\u4e0d\u592a\u4e00\u6a23\u3002\u521d\u59cb\u689d\u4ef6\u7576\u7136\u4e5f\u4e0d\u592a\u4e00\u6a23\u3002<\/p>\n

\u7531\u65bc R(1, n) = n \u9019\u9ede\u4ecd\u4e0d\u8b8a\uff0c\u56e0\u6b64\uff1a<\/p>\n

R(2, n) = R(1, n) + R(2, n – 1) + 1
\n-> R(2, n) – R(2, n – 1) = n + 1
\n-> R(2, n) = (n + 1)(n + 2)\/2 – 1<\/p>\n

\u800c<\/p>\n

R(3, n) = R(2, n) + R(3, n – 1) + 1
\n-> R(3, n) – R(3, n – 1) = (n + 1)(n + 2)\/2 – 1 + 1 = (n + 1)(n + 2)\/2
\n-> R(3, n) = (n + 1)(n + 2)(n + 3)\/6 – 1<\/p>\n

\u63a8\u5c0e\u4e0b\u53bb\u53ef\u4ee5\u5f97\u5230<\/p>\n

R(m, n) = C(m + n, m) – 1<\/p>\n

\u4f8b\u5982\uff0c\u4e09\u500b\u7403\u53ef\u4ee5\u540c\u6642\u4e1f\u7684\u8a71\uff0c100 \u5c64\u6a13\u9700\u8981\u4e1f\u5e7e\u6b21\uff1f<\/p>\n

\u56e0\u70ba R(3, 6) = 83\uff0c\u800c R(3, 7) = 119\uff0c\u56e0\u6b64\u4e09\u500b\u7403\u53ef\u4ee5\u540c\u6642\u4e1f\u7684\u6642\u5019\uff0c\u6700\u591a\u53ea\u9700\u8981\u4e1f 7 \u6b21\u3002<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

\u4f86\u6e90 http:\/\/www.kimicat.com\/Home\/bowlingball \u5fc3\u5f97\uff1a\u5e38\u5e38\uff0c\u6211\u5011\u60f3\u8981\u53bb\u5c0b … \u95b1\u8b80\u5168\u6587\u3008[\u8f49]\u5169\u500b\u4fdd\u9f61\u7403\u7684\u6545\u4e8b\u3009<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.kuki.idv.tw\/index.php?rest_route=\/wp\/v2\/posts\/2358"}],"collection":[{"href":"https:\/\/www.kuki.idv.tw\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.kuki.idv.tw\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.kuki.idv.tw\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.kuki.idv.tw\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2358"}],"version-history":[{"count":1,"href":"https:\/\/www.kuki.idv.tw\/index.php?rest_route=\/wp\/v2\/posts\/2358\/revisions"}],"predecessor-version":[{"id":2359,"href":"https:\/\/www.kuki.idv.tw\/index.php?rest_route=\/wp\/v2\/posts\/2358\/revisions\/2359"}],"wp:attachment":[{"href":"https:\/\/www.kuki.idv.tw\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2358"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.kuki.idv.tw\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2358"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.kuki.idv.tw\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2358"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}