27 lines
748 B
Plaintext
27 lines
748 B
Plaintext
fn hofq(q: &mut Vec<u32>, x : u32) -> u32 {
|
|
let cur_len=q.len()-1;
|
|
let i=x as usize;
|
|
if i>cur_len {
|
|
// extend storage
|
|
q.reserve(i+1);
|
|
for j in (cur_len+1)..(i+1) {
|
|
let qj=(q[j-q[j-1] as usize]+q[j-q[j-2] as usize]) as u32;
|
|
q.push(qj);
|
|
}
|
|
}
|
|
q[i]
|
|
}
|
|
|
|
fn main() {
|
|
let mut q_memo: Vec<u32>=vec![0,1,1];
|
|
let mut q=|i| {hofq(&mut q_memo, i)};
|
|
for i in 1..11 {
|
|
println!("Q({})={}", i, q(i));
|
|
}
|
|
println!("Q(1000)={}", q(1000));
|
|
let q100001=q(100_000); // precompute all
|
|
println!("Q(100000)={}", q100000);
|
|
let nless=(1..100_000).fold(0,|s,i|{if q(i+1)<q(i) {s+1} else {s}});
|
|
println!("Term is less than preceding term {} times", nless);
|
|
}
|