Created
March 1, 2018 18:53
-
-
Save NoahTheDuke/7182f6da4bc6d0a019cc96c86dd214bd to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
extern crate time; | |
use time::PreciseTime; | |
fn main() { | |
let m = 3; | |
for n in 20..31 { | |
println!("n: {}", n); | |
let s = PreciseTime::now(); | |
let res = a_opt(m, n); | |
let e = PreciseTime::now(); | |
println!("opt -> {} took {}", res, s.to(e)); | |
} | |
} | |
#[derive(Clone, Debug)] | |
struct Record { | |
f: u64, | |
s: u64, | |
t: Option<Box<Record>>, | |
} | |
impl Record { | |
fn new(f: u64, s: u64, t: Option<Box<Record>>) -> Record { | |
Record { f: f, s: s, t: t } | |
} | |
} | |
fn a_opt(i: u64, n: u64) -> u64 { | |
let mut v = Record::new(1, 0, None); | |
for k in 1..(i + 1) { | |
v = a_use_p(k - 1, 1, v) | |
} | |
for j in 1..(n + 1) { | |
v = a_use_p(i, j, v) | |
} | |
v.f | |
} | |
fn a_use_p(i: u64, n: u64, r_use: Record) -> Record { | |
if i == 0 { | |
Record::new(n + 1, 0, None) | |
} else if n == 0 { | |
let mut v = Record::new(1, 0, None); | |
for k in 1..(i + 1) { | |
v = a_use_p(k - 1, 1, v); | |
} | |
v | |
} else if n - 1 == 0 { | |
let v11 = r_use.f; | |
let mut v2 = r_use.clone(); | |
for k in 2..(r_use.f + 1) { | |
v2 = a_use_p(i - 1, k, v2); | |
} | |
Record::new(v2.f, v11, Some(Box::new(v2))) | |
} else { | |
let v11 = r_use.f; | |
let mut v2 = *r_use.t.unwrap(); | |
for k in (r_use.s + 1)..(r_use.f + 1) { | |
v2 = a_use_p(i - 1, k, v2); | |
} | |
Record::new(v2.f, v11, Some(Box::new(v2))) | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment