user6603599 - 1 year ago 71

C++ Question

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 Source

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.