Rust:Fibonacci - halmk/Library GitHub Wiki

Fibonacci

Overview

フィボナッチ数列の様々な書き方をまとめる

Code

  • メイン関数
fn main(){
    let n:i32 = read();
    let res:i32 = fib(n);

    println!("{}", res);
}
  • O(2^n)：愚直な実装
fn fib(x: i32) -> i32 {
    match x {
        0 => 1,
        1 => 1,
        _ => fib(x-2) + fib(x-1),
    }
}
  • O(n)：fib(x-1)+fib(x-2)->fib(x)のボトムアップ
fn fib(x: i32) -> i32 {
    fn func(a: i32, b: i32, c: i32) -> i32 {
        if c < 2 { return a; }
        func(a+b, a, c-1)
    }
    func(1, 1, x)
}
  • O(n)：動的計画法
fn fib(x: i32) -> i32 {
    let mut f1 = 1;
    let mut f2 = 1;
    let mut tmp = 0;
    for _ in 0..x-1 {
        tmp = f1 + f2;
        f1 = f2;
        f2 = tmp;
    }
    tmp
}
  • O(n)：メモ化再帰
const MAX: usize = 100000;

fn fib(x: usize, memo: &mut Vec<usize>) -> usize {
    if x < 2 { return 1; }
    if memo[x] != 0 {
        return memo[x];
    }
    memo[x] = fib(x-1,memo) + fib(x-2,memo);
    return memo[x];
}
fn main(){
    let n:usize = read();

    let mut memo: Vec<usize> = vec![0;MAX];
    let res = fib(n, &mut memo);

    println!("{}", res);
}

Detail

⚠️ **GitHub.com Fallback** ⚠️