fork download 
  1. use std::io::{self, BufRead};
  2.  
  3. fn main() {
  4.     let stdin = io::stdin();
  5.     for line in stdin.lock().lines() {
  6.         if line.is_ok() {
  7.             let content = line.unwrap();
  8.             let number: u64 = content.parse().unwrap();
  9.             let zeckendorf = zeckendorf_repr(number);
  10.  
  11.             print!("{} = ", number);
  12.             for (i, fib) in zeckendorf.iter().enumerate() {
  13.                 if i < zeckendorf.len() - 1 {
  14.                     print!("{} + ", fib);
  15.                 } else {
  16.                     println!("{}", fib);
  17.                 }
  18.             }
  19.         }
  20.     }
  21. }
  22.  
  23. pub fn gen_fibs_to(limit: u64) -> Vec<u64> {
  24.     let mut fibs: Vec<u64> = vec![1, 2];
  25.  
  26.     while fibs[fibs.len()-1] <= limit {
  27.         let next_fib = fibs[fibs.len() - 1] + fibs[fibs.len() - 2];
  28.         fibs.push(next_fib);
  29.     }
  30.     fibs.pop();
  31.  
  32.     fibs
  33. }
  34.  
  35. pub fn zeckendorf_repr(n: u64) -> Vec<u64> {
  36.     let fibs = gen_fibs_to(n);
  37.     let mut repr: Vec<u64> = Vec::new();
  38.     let mut curr_sum: u64 = 0;
  39.  
  40.     for fib in fibs.iter().rev() {
  41.         if fib + curr_sum > n {
  42.             continue;
  43.         }
  44.  
  45.         repr.push(*fib);
  46.         curr_sum = curr_sum + *fib;
  47.  
  48.         if curr_sum == n {
  49.             break;
  50.         }
  51.     }
  52.  
  53.     repr
  54. }
Success #stdin #stdout 0s 11120KB
comments ()
stdin 
4
100
30
5
120
34
88
90
320
stdout 
4 = 3 + 1
100 = 89 + 8 + 3
30 = 21 + 8 + 1
5 = 5
120 = 89 + 21 + 8 + 2
34 = 34
88 = 55 + 21 + 8 + 3 + 1
90 = 89 + 1
320 = 233 + 55 + 21 + 8 + 3
https://ideone.com/iwQiBX
language:
Rust (rust 1.56)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!