user6603599 user6603599 - 25 days ago 17
C++ Question

Base 10 number to Fibonacci number

What are the contents of a simple C++ program that transforms a base 10 number in a base Fibonacci number ?
This is how to write a number using only Fibonacci numbers:

#include <iostream>
using namespace std;
int n, a, b, c, i;
int main() {
cin >> n;
cout << n << " " << "=" << " ";
while(n > 0) {
a = 0;
b = 1;
c = 1;
while(c <= n) {
a = b;
b = c;
c = a + b;
}
if(b < n) cout << b << " " << "+" << " ";
else cout << b;
n = n - b;
}
return 0;
}

Answer

According to this website, you can write numbers in "base Fibonacci" as the sum of other Fibonacci numbers. Example:

10 = 8 + 2

where 8 is the 5th Fib number and 2 is the 2nd. So when you write out in "base Fibonacci", you write it like a binary number with the 5th and 2nd "bits" set:

10010 base fib = 10 base 10
^  ^
8  2

So this code creates an integer where each bit in the integer represents a fib number in sequence. Then is simply prints the number (I've used OP's code to find the Fib numbers that can be added together):

int n, a, b, c, i;
cin >> n;
cout << n << " " << "=" << " ";
bitset<32> bits;    // Use a bitset to store the digits
while(n > 0) {
    a = 0;
    b = 1;
    c = 1;
    int count = 0;  // "count" is the nth fib # calculated
    while(c <= n) {
        count += 1;
        a = b;
        b = c;
        c = a + b;
    }
    bits.set(count - 1);  // Set the bit
    if(b < n) cout << b << " " << "+" << " ";
    else cout << b;
    n = n - b;
}
cout << endl;

// Convert binary to string of 0s and 1s
const string str_bits = bits.to_string();
const auto first_digit = str_bits.find('1') ; // locate the first '1'

// if first_digit is NOT std::string::npos, we found the first 1 
if( first_digit != std::string::npos ) {  // found it; print the substring starting at the first '1'
    std::cout << str_bits.substr(first_digit) << endl; 
}
// Not found, so it's just 0
else {
    std::cout << "0" << endl ; // all the bits were zeroes
}

Note, according to the website, no two consecutive Fibonacci numbers can be used in the same sum. This code does not address that restriction.

Comments