{"id":8,"date":"2010-06-13T15:20:11","date_gmt":"2010-06-13T19:20:11","guid":{"rendered":"http:\/\/hw.minilinux.net\/?p=8"},"modified":"2024-09-08T13:44:35","modified_gmt":"2024-09-08T17:44:35","slug":"%e6%af%8f%e6%97%a55%e9%a2%98-0612","status":"publish","type":"post","link":"https:\/\/hw.minilinux.net\/?p=8","title":{"rendered":"\u6bcf\u65e55\u9898–0612"},"content":{"rendered":"

1. \u5982\u679c\u7528\u6700\u5c11\u7684\u6bd4\u8f83\u6b21\u6570\u627e\u51fa \u4e00\u4e2a\u6570\u7ec4\u7684\u6700\u5927\u548c\u6b21\u5927\u7684\u6570?<\/strong><\/p>\n

2. 50\u4e2a\u9ed1\u740350\u4e2a\u767e\u7403\uff0c2\u4e2a\u7f50\uff0c\u8981\u6c42\u4f60\u653e\u8fd9100\u4e2a\u7403\u5728\u8fd92\u4e2a\u7f50\uff0c\u4f7f\u5f97\u522b\u4eba\u968f\u673a\u4ece2\u4e2a
\n\u7f50\u4e2d\u4efb\u610f\u62ff\u4e00\u4e2a\u7403\u662f\u9ed1\u7403\u7684\u51e0\u7387\u8fbe\u5230\u6700\u5927\u3002<\/strong><\/p>\n

3. 2\u4e2a\u4eba\u5546\u91cf\u597d\u7b56\u7565\uff0c\u7136\u540e\u4e00\u4e2a\u4ece52\u5f20\u724c\u91cc\u9762\u968f\u673a\u62bd5\u5f20\uff0c\u770b\u724c\uff0c\u8003\u8651\u3002\u3002\u3002\u7136\u540e\u6392\u5728
\n\u684c\u4e0a\uff0c\u644a\u5f00\u524d4\u5f20\uff0c\u7b2c5\u5f20\u9762\u671d\u4e0b\uff0c\u7531\u7b2c\u4e8c\u4e2a\u4eba\u5224\u65ad\u7b2c5\u5f20\u724c\u3002 \u95ee\u8fd9\u4e2a\u7b56\u7565\u3002<\/strong><\/p>\n

4.\u5199atoi\u51fd\u6570<\/strong><\/p>\n

5.\u53e4\u8001\u7684\u4e09\u89d2\u5f62\u95ee\u9898\uff1a\u8f93\u51653\u8fb9\uff0c\u770b\u662f\u4ec0\u4e48\u4e09\u89d2\u5f62\u3002<\/strong><\/p>\n

1. Brute Force\u5f53\u7136\u53ef\u4ee5\u7b97\u51fa\u6765, \u8fd9\u6837\u627e\u5230\u6700\u5927\u7684 \u9700\u8981\u6bd4\u8f83 (n-1)\u6b21, \u7136\u540e\u5728(n-1)\u4e2a\u6570\u91cc\u9762\u627e\u5230\u6700\u5927\u7684
\n\u8981(n-2)\u6b21, \u603b\u5171\u6bd4\u8f83n-1+n-2 = 2*n-3\u6b21<\/p>\n

\u7136\u540e\u53ef\u4ee5Divide and Conquer, \u5982\u679cn\u4e2a\u6570, \u5206\u62102\u7ec4, \u6bcf\u7ec4\u7684\u6700\u5927,\u6b21\u5927\u90fd\u627e\u5230\u4e86,
\nM1 M2
\nN1 N2
\n\u90a3\u4e48\u53ea\u8981M1\u548cM2\u6bd4\u4e00\u6b21, \u627e\u51fa\u5373\u662f\u6700\u5927\u7684\u6570, \u7136\u540e\u5982\u679cM1\u5927, N1 \u548c M2\u518d\u6bd4\u4e00\u6b21\u5c31\u597d\u4e86,
\n\u6240\u4ee5\u6211\u4eec\u6709 T(n) = 2*T(n\/2) + 2;
\n\u800c\u4e14\u56e0\u4e3a T(2) = 1;
\nT(n) = 1.5*n – 2;<\/p>\n

\u4f46\u662f\u8fd8\u6709\u66f4\u597d\u7684\u65b9\u6cd5, \u53d1\u73b0\u6bcf\u6b21\u6211\u4eec\u5206\u7ec4\u4e4b\u540e\u5176\u5b9e\u53ea\u8981\u628a\u6700\u5927\u503c\u6bd4\u8f83\u51fa\u6765\u5c31\u597d, \u7136\u540e\u628a\u6bd4\u8f83\u4e2d\u5c0f\u7684
\n\u90a3\u4e2a\u6570\u653e\u5165\u4e00\u4e2agroup\u4e2d, \u6700\u540e\u6211\u4eec\u6bd4\u8f83\u51fa\u6765\u4e4b\u540e\u5c31\u627e\u5230\u6700\u5927\u7684\u6570\u4e86, \u7136\u540e\u5728\u90a3\u4e2agroup\u4e2d\u627e\u5230\u6700\u5927
\n\u7684\u6570\u5c31\u662f\u6574\u4e2a\u7ebf\u6027\u5217\u7684\u6b21\u5927\u6570\u4e86<\/p>\n

\u8fd9\u6837\u627e\u5230\u6700\u5927\u7684\u6570 T(n) = 2*T(n\/2) +1 T(n) = n-1;(\u8fd9\u662f\u5e9f\u8bdd\u62c9,\u627e\u5230\u6700\u5927\u7684\u6570\u6700\u5c11\u4e5f\u8981n-1\u6b21)
\n\u7136\u540e\u5de7\u5999\u7684\u662fgroup\u4e2d\u53ea\u6709log(n)\u4e2a\u5143\u7d20, \u6bd4\u8f83log(n) -1 \u5c31\u597d\u4e86
\n\u6240\u4ee5\u603b\u5171 T(n) = (n-1)+(log(n)-1) = log(n) +n-2;<\/p>\n

\u6211\u4eec\u53ef\u4ee5\u8bc1\u660elog(n) < 0.5*n, \u6240\u4ee5 T(n) = long(n) + n-2\u662f\u4e0a\u8ff0\u4e2d\u6700\u597d\u7684\u65b9\u6cd5<\/p>\n

2. \u6700\u597d\u7684\u65b9\u6cd5\u5e94\u8be5\u662f \u4e00\u4e2a\u9ed1\u7403\u653e\u5728A\u7f50, 49\u4e2a\u9ed1\u7403\u548c50\u4e2a\u767d\u7403\u653e\u5728B\u7f50<\/p>\n

3. \u8001\u5b9e\u8bf4\u6ca1\u770b\u61c2..<\/p>\n

4. \u8fd9\u4e2a\u5f88\u76f4\u89c2, char* -> int, \u4f46\u662f\u9700\u8981\u8003\u8651\u5f88\u591a\u8fb9\u754c\u6761\u4ef6, \u6bd4\u5982\u8f93\u5165\u7684\u5b57\u7b26\u4e32\u91cc\u9762\u51fa\u73b0\u4e86\u975e\u6cd5\u5b57\u7b26
\n\u600e\u4e48\u529e, \u6bd4\u5982\u8f93\u5165\u7684\u662fNULL\u600e\u4e48\u529e;
\n\u8fd8\u6709\u4e00\u70b9\u5173\u952e\u7684\u7684\u662f \u6709\u53ef\u80fd\u5b57\u7b26\u4e32\u91cc\u9762\u5f00\u59cb\u9636\u6bb5\u6709\u5f88\u591a\/space, \/tab(\u8fd9\u4e2a\u90fd\u662f\u5141\u8bb8\u7684, \u8fd9\u4e2a\u6bd4\u8f83
\n\u5bb9\u6613\u5fd8\u8bb0), \u7136\u540e\u6709\u53ef\u80fd\u6709sign\u7b26\u53f7(“+”\u6216\u8005 “-“)<\/p>\n

int atoi(char *p)\n{\nint index = 0, sign = 1, s =0;\nif(!p)  exit(1);\nwhile(p[index]==' '||p[index]=='\\t')\n\tindex++;\nif(p[index] == '+') \n\tindex++;\nelse if(p[index] == '-') \n\t{ sign = -1; index++;}\nwhile(p[index]!='\\0'&&p[index]<='9'&&p[index]>='0')\n\ts = s*10 + (p[index++]-'0');\nif(p[index]!='\\0')   exit(2);  \/\/illegal character examined\nelse return (sign*s);\n}<\/pre>\n
\u8fd8\u6709\u4e00\u4e2a\u503c\u5f97\u8ba8\u8bba\u7684\u95ee\u9898, \u5f53\u8f93\u5165\u7684\u5b57\u7b26\u5927\u4e8eint\u7684\u6700\u5927\u8303\u56f4(-2^31–2^31-1), \u5982\u679c\u6bcf\u6b21\u90fd\u8981\u5224\u65ad
\n\u611f\u89c9\u5f88\u9ebb\u70e6,<\/p>\n
5. \u5927\u6982\u5c31\u662f\u628avector\u6c42\u51fa\u6765, \u7136\u540e\u5229\u7528 a*b = |a|*|b|*cos(theta);
\n\u628a\u89d2\u5ea6\u7684\u4f59\u7384\u7b97\u51fa\u6765,\u5c31\u597d\u4e86<\/p>\n","protected":false},"excerpt":{"rendered":"
1. \u5982\u679c\u7528\u6700\u5c11\u7684\u6bd4\u8f83\u6b21\u6570\u627e\u51fa \u4e00\u4e2a\u6570\u7ec4\u7684\u6700\u5927\u548c\u6b21\u5927\u7684\u6570? 2. 50\u4e2a\u9ed1\u740350\u4e2a\u767e\u7403\uff0c2\u4e2a\u7f50\uff0c\u8981\u6c42\u4f60\u653e\u8fd9100\u4e2a\u7403\u5728\u8fd92\u4e2a\u7f50\uff0c\u4f7f\u5f97\u522b\u4eba\u968f\u673a\u4ece2\u4e2a \u7f50\u4e2d\u4efb\u610f\u62ff\u4e00\u4e2a\u7403\u662f\u9ed1\u7403\u7684\u51e0\u7387\u8fbe\u5230\u6700\u5927\u3002 3. 2\u4e2a\u4eba\u5546\u91cf\u597d\u7b56\u7565\uff0c\u7136\u540e\u4e00\u4e2a\u4ece52\u5f20\u724c\u91cc\u9762\u968f\u673a\u62bd5\u5f20\uff0c\u770b\u724c\uff0c\u8003\u8651\u3002\u3002\u3002\u7136\u540e\u6392\u5728 \u684c\u4e0a\uff0c\u644a\u5f00\u524d4\u5f20\uff0c\u7b2c5\u5f20\u9762\u671d\u4e0b\uff0c\u7531\u7b2c\u4e8c\u4e2a\u4eba\u5224\u65ad\u7b2c5\u5f20\u724c\u3002 \u95ee\u8fd9\u4e2a\u7b56\u7565\u3002 4.\u5199atoi\u51fd\u6570 5.\u53e4\u8001\u7684\u4e09\u89d2\u5f62\u95ee\u9898\uff1a\u8f93\u51653\u8fb9\uff0c\u770b\u662f\u4ec0\u4e48\u4e09\u89d2\u5f62\u3002 1. Brute Force\u5f53\u7136\u53ef\u4ee5\u7b97\u51fa\u6765, \u8fd9\u6837\u627e\u5230\u6700\u5927\u7684 \u9700\u8981\u6bd4\u8f83 (n-1)\u6b21, \u7136\u540e\u5728(n-1)\u4e2a\u6570\u91cc\u9762\u627e\u5230\u6700\u5927\u7684 \u8981(n-2)\u6b21, \u603b\u5171\u6bd4\u8f83n-1+n-2 = 2*n-3\u6b21 \u7136\u540e\u53ef\u4ee5Divide and Conquer, \u5982\u679cn\u4e2a\u6570, \u5206\u62102\u7ec4, \u6bcf\u7ec4\u7684\u6700\u5927,\u6b21\u5927\u90fd\u627e\u5230\u4e86, M1 M2 N1 N2 \u90a3\u4e48\u53ea\u8981M1\u548cM2\u6bd4\u4e00\u6b21, \u627e\u51fa\u5373\u662f\u6700\u5927\u7684\u6570, \u7136\u540e\u5982\u679cM1\u5927, N1 \u548c M2\u518d\u6bd4\u4e00\u6b21\u5c31\u597d\u4e86, \u6240\u4ee5\u6211\u4eec\u6709 T(n) = 2*T(n\/2) + 2; \u800c\u4e14\u56e0\u4e3a T(2) = 1; T(n) = 1.5*n – 2; \u4f46\u662f\u8fd8\u6709\u66f4\u597d\u7684\u65b9\u6cd5, … Continue reading “\u6bcf\u65e55\u9898–0612”<\/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":[11],"class_list":["post-8","post","type-post","status-publish","format-standard","hentry","category-programming-and-algorithm","tag-11"],"_links":{"self":[{"href":"https:\/\/hw.minilinux.net\/index.php?rest_route=\/wp\/v2\/posts\/8","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=8"}],"version-history":[{"count":22,"href":"https:\/\/hw.minilinux.net\/index.php?rest_route=\/wp\/v2\/posts\/8\/revisions"}],"predecessor-version":[{"id":637,"href":"https:\/\/hw.minilinux.net\/index.php?rest_route=\/wp\/v2\/posts\/8\/revisions\/637"}],"wp:attachment":[{"href":"https:\/\/hw.minilinux.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=8"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/hw.minilinux.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=8"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/hw.minilinux.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=8"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}