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;
}
``````

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;
}