Lotplace

二項式係數，即排列組合中常見的Cn取m。

\binom{n}{m} = \frac{n!}{m!(n-m)!}\ ,\ n >= m

思路:

1. Cn取0與Cn取n是1
2. 用加法公式作為遞迴關係式

加法公式

\binom{n}{m} = \binom{n-1}{m-1} + \binom{n-1}{m}

條件歸納

bin(n, m)=
\begin{cases}
1,\ where\ n = m\ ,or\ m=1\\
bin(n-1,m-1) + bin(n-1,m),\ otherwise
\end{cases}

Golang

遞迴版本:

package main

import "fmt"

//遞迴版本bin(n)
func bin(n, m int) int {
    if m == 0 || m == n {
        return 1
    }
    return bin(n-1, m-1) + bin(n-1, m)
}

func main() {
    fmt.Println("input n,m:")
    var n, m int
    fmt.Scanf("%d,%d", &n, &m)
    fmt.Printf("bin(%d, %d) = %d\n", n, m, bin(n, m))
}

用原式改寫成迭代版本:

func factorial(x int) int {
    y := 1
    for x > 1 {
        y *= x
        x--
    }
    return y
}

//迭代版本bin(n)
func bin(n, m int) int {
    return factorial(n) / (factorial(m) * factorial(n-m))
}

利用分子分母階乘抵銷的特性，寫出效能較佳的迭代版本:

package main

import "fmt"

func swap(x, y int) (int, int) {
    return y, x
}

//x到y之間整數相乘，也就是x!/y!
func factorial_to(x, y int) int {
    result := 1
    for x > y {
        result *= x
        x--
    }
    return result
}

//效能較佳的迭代版本bin(n)
func bin(n, m int) int {
    f1 := m
    f2 := n - m
    //f1取較大的值去跟n!相除，以減少算量
    if f1 < f2 {
        f1, f2 = swap(f1, f2)
    }
    return factorial_to(n, f1) / factorial_to(f2, 1)
}

func main() {
    fmt.Println("input n,m:")
    var n, m int
    fmt.Scanf("%d,%d", &n, &m)
    fmt.Printf("bin(%d, %d) = %d\n", n, m, bin(n, m))
}

Kidian Liu

好想ㄘ爆甜點RRR

Filed under: 演算法 - @ 2021 年 6 月 30 日 上午 11:59

標籤: algo, recursive