{"id":110,"date":"2021-06-30T11:59:25","date_gmt":"2021-06-30T03:59:25","guid":{"rendered":"https:\/\/aisumura.net\/blog\/?p=110"},"modified":"2021-06-30T11:59:25","modified_gmt":"2021-06-30T03:59:25","slug":"%e5%af%a6%e4%bd%9c%e9%81%9e%e8%bf%b44-binomial-coefficent","status":"publish","type":"post","link":"https:\/\/aisumura.net\/blog\/2021\/06\/30\/%e5%af%a6%e4%bd%9c%e9%81%9e%e8%bf%b44-binomial-coefficent\/","title":{"rendered":"\u5be6\u4f5c\u905e\u8ff4(4) – Binomial Coefficent"},"content":{"rendered":"\n

\u4e8c\u9805\u5f0f\u4fc2\u6578\uff0c\u5373\u6392\u5217\u7d44\u5408\u4e2d\u5e38\u898b\u7684Cn\u53d6m\u3002<\/p>\n\n\n\n

\n
\n
\\binom{n}{m} = \\frac{n!}{m!(n-m)!}\\ ,\\ n >= m<\/pre><\/div>\n<\/div>\n\n\n\n
<\/div>\n<\/div>\n\n\n\n
\u601d\u8def:<\/h4>\n\n\n\n
  1. Cn\u53d60\u8207Cn\u53d6n\u662f1<\/li>
  2. \u7528\u52a0\u6cd5\u516c\u5f0f\u4f5c\u70ba\u905e\u8ff4\u95dc\u4fc2\u5f0f<\/li><\/ol>\n\n\n\n
    \u52a0\u6cd5\u516c\u5f0f<\/h4>\n\n\n\n
    \n
    \n
    \\binom{n}{m} = \\binom{n-1}{m-1} + \\binom{n-1}{m}<\/pre><\/div>\n<\/div>\n\n\n\n
    <\/div>\n<\/div>\n\n\n\n
    \u689d\u4ef6\u6b78\u7d0d<\/h4>\n\n\n\n
    \n
    \n
    bin(n, m)=\n\\begin{cases}\n1,\\ where\\ n = m\\ ,or\\ m=1\\\\\nbin(n-1,m-1) + bin(n-1,m),\\ otherwise\n\\end{cases}<\/pre><\/div>\n<\/div>\n\n\n\n
    <\/div>\n<\/div>\n\n\n\n
    Golang<\/h4>\n\n\n\n
    \u905e\u8ff4\u7248\u672c:<\/p>\n\n\n\n
    package main\n\nimport \"fmt\"\n\n\/\/\u905e\u8ff4\u7248\u672cbin(n)\nfunc bin(n, m int) int {\n    if m == 0 || m == n {\n        return 1\n    }\n    return bin(n-1, m-1) + bin(n-1, m)\n}\n\nfunc main() {\n    fmt.Println(\"input n,m:\")\n    var n, m int\n    fmt.Scanf(\"%d,%d\", &n, &m)\n    fmt.Printf(\"bin(%d, %d) = %d\\n\", n, m, bin(n, m))\n}<\/code><\/pre>\n\n\n\n
    \u7528\u539f\u5f0f\u6539\u5beb\u6210\u8fed\u4ee3\u7248\u672c:<\/p>\n\n\n\n
    func factorial(x int) int {\n    y := 1\n    for x > 1 {\n        y *= x\n        x--\n    }\n    return y\n}\n\n\/\/\u8fed\u4ee3\u7248\u672cbin(n)\nfunc bin(n, m int) int {\n    return factorial(n) \/ (factorial(m) * factorial(n-m))\n}<\/code><\/pre>\n\n\n\n
    \u5229\u7528\u5206\u5b50\u5206\u6bcd\u968e\u4e58\u62b5\u92b7\u7684\u7279\u6027\uff0c\u5beb\u51fa\u6548\u80fd\u8f03\u4f73\u7684\u8fed\u4ee3\u7248\u672c:<\/p>\n\n\n\n
    package main\n\nimport \"fmt\"\n\nfunc swap(x, y int) (int, int) {\n    return y, x\n}\n\n\/\/x\u5230y\u4e4b\u9593\u6574\u6578\u76f8\u4e58\uff0c\u4e5f\u5c31\u662fx!\/y!\nfunc factorial_to(x, y int) int {\n    result := 1\n    for x > y {\n        result *= x\n        x--\n    }\n    return result\n}\n\n\/\/\u6548\u80fd\u8f03\u4f73\u7684\u8fed\u4ee3\u7248\u672cbin(n)\nfunc bin(n, m int) int {\n    f1 := m\n    f2 := n - m\n    \/\/f1\u53d6\u8f03\u5927\u7684\u503c\u53bb\u8ddfn!\u76f8\u9664\uff0c\u4ee5\u6e1b\u5c11\u7b97\u91cf\n    if f1 < f2 {\n        f1, f2 = swap(f1, f2)\n    }\n    return factorial_to(n, f1) \/ factorial_to(f2, 1)\n}\n\nfunc main() {\n    fmt.Println(\"input n,m:\")\n    var n, m int\n    fmt.Scanf(\"%d,%d\", &n, &m)\n    fmt.Printf(\"bin(%d, %d) = %d\\n\", n, m, bin(n, m))\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
    \u4e8c\u9805\u5f0f\u4fc2\u6578\uff0c\u5373\u6392\u5217\u7d44\u5408\u4e2d\u5e38\u898b\u7684Cn\u53d6m\u3002 \u601d\u8def: Cn\u53d60\u8207Cn\u53d6n\u662f1 \u7528\u52a0\u6cd5\u516c\u5f0f\u4f5c\u70ba\u905e\u8ff4\u95dc\u4fc2\u5f0f \u52a0\u6cd5\u516c\u5f0f  […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[9],"tags":[6,8],"_links":{"self":[{"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/posts\/110"}],"collection":[{"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/comments?post=110"}],"version-history":[{"count":3,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/posts\/110\/revisions"}],"predecessor-version":[{"id":114,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/posts\/110\/revisions\/114"}],"wp:attachment":[{"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/media?parent=110"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/categories?post=110"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/tags?post=110"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}