草稿

f(n)=1+1/(1+f(n1))f(n) = 1 + 1/(1 + f(n-1))
f(0)=1f(0) = 1
p57.rs
use algorithms::math::lcm::lcm2;
use num_bigint::{BigInt, ToBigInt};

pub fn solution_of_p57() -> usize {
    let mut s = 0;
    let mut curr_frac = continued_fraction(0);
    for _i in 1..=1000 {
        curr_frac = next_continued_fraction(&curr_frac);
        let f_num = curr_frac.numerator.to_string().len();
        let f_deno = curr_frac.denominator.to_string().len();
        if f_num > f_deno {
            s += 1;
        }
    }
    return s;
}

fn next_continued_fraction(curr_frac: &Fraction) -> Fraction {
    let inner_deno = continued_fraction(0).add(curr_frac.clone());
    let inner_frac = continued_fraction(0).add(inner_deno.reciprocal());
    return inner_frac;
}

fn continued_fraction(n: usize) -> Fraction {
    if n == 0 {
        return Fraction::new(BigInt::from(1), BigInt::from(1));
    }
    let mut i = 0;
    let mut result = Fraction::new(BigInt::from(1), BigInt::from(1));
    while i < n {
        let inner_deno = continued_fraction(0).add(result.clone());
        let inner_frac = continued_fraction(0).add(inner_deno.reciprocal());
        result = inner_frac;
        i += 1;
    }
    return result;
}

#[derive(Clone)]
pub struct Fraction {
    pub numerator: BigInt,
    pub denominator: BigInt,
}

impl Fraction {
    pub fn new(numerator: BigInt, denominator: BigInt) -> Self {
        Fraction {
            numerator,
            denominator,
        }
    }

    pub fn add(&self, adder: Fraction) -> Fraction {
        let new_deno = lcm2(
            self.denominator.to_bigint().unwrap(),
            adder.denominator.to_bigint().unwrap(),
        );
        let new_self_num = (new_deno.clone() / self.denominator.clone()) * self.numerator.clone();
        let new_adder_num = (new_deno.clone() / adder.denominator) * adder.numerator;
        let new_num = new_self_num + new_adder_num;
        Fraction {
            numerator: new_num,
            denominator: new_deno,
        }
    }

    pub fn reciprocal(&self) -> Fraction {
        Fraction {
            numerator: self.denominator.clone(),
            denominator: self.numerator.clone(),
        }
    }
}

Last updated