TalkGo 算法之美第七期

数学是计算机的重要基础,算法题中常常会用到数学知识,尤其是离散、具体的数学,以数论、排列组合、概率期望、多项式为代表,可以出现在几乎任何类别的题目中,所有题目涉及到的数学知识点都已标出,建议去oi-wiki 学习。

强烈建议小伙伴先尝试用非数学的常规解法思考以下题目(也许会更简单更好理解),再用数学的解法。

第一周

5月3日

5月5日

  • 超级丑数 做这题之前先学习求质数的几种方法 (强烈建议掌握),之后只需要思考如何求出第n个即可.
  • 石子游戏 经典的石子游戏肯定是不能错过的,建议先用动态规划解一遍。

5月7日

1赞

关于第一题斐波那契数列,我之前做了一个ppt,大家可以参考下。

我也有一篇矩阵相关的题解 矩阵+快速幂求解递推问题

斐波那契数列

func fib(n int) int {
	if n < 2 {
		return n
	}

	p, q, r := 0, 1, 1
	for i := 2; i <= n; i++ {
		r = (p + q) % (1e9 + 7)
		p = q
		q = r
	}

	return r
}



pub struct Solution;

impl Solution {
    pub fn multiply(a: [[i64; 2]; 2], b: [[i64; 2]; 2]) -> [[i64; 2]; 2] {
        let mut c:[[i64; 2]; 2] = [[0,0],[0,0]];
        for i in 0..2 {
            for j in 0..2 {
                c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) % (1000000007)
            }
        }

        c
    }

    pub fn pow(mut a :[[i64;2];2], n:i32)-> [[i64; 2]; 2] {

        let mut c:[[i64; 2]; 2]= [[1,0],[0,1]];
        let mut n = n;
        while n>0{
            if n&1 ==1{
                c = Self::multiply(c, a);
            }

            a = Self::multiply(a, a);
            // println!("{:?}",a);
            n = n>>1;
        }

        c
    }

    pub fn fib(n: i32) -> i32 {
        if n <2{
            return n;
        }

        let r:[[i64; 2]; 2] = Self::pow([[1,1],[1,0]], n-1);
        return r[0][0] as i32

    }
}

#[cfg(test)]
mod tests {
    use crate::Solution;
    #[test]
    fn it_works() {
        assert_eq!(Solution::fib(5),5);
        assert_eq!(Solution::fib(48),807526948);
        assert_eq!(Solution::fib(6),8);
    }
}

1赞