Fibonacci进制
题目描述
Fibonacci数是非常有名的一个数列,它的公式为 f(n)=f(n-1)+f(n-2),f(0)=1,f(1)=2。 我们可以把任意一个数x表示成若干不相同的Fibonacci数的和， 比如说14 = 13+1 = 8+5+1 = 8+3+2+1。 如果把Fibonacci数列作为数的位权，即f(i)作为第i位的位权，每位的系数只能是0或者1，从而得到一个01串。 比如14可以表示成 100001，11001，10111。 我们再把这个01串看成2进制，再转成10进制以后就变成了 33，25，23。 为了避免歧义，我们将使用最小的那个值23。 请按照这个过程计算一下10进制整数通过上述转换过程得到的10进制整数。
输入
第一行是一个整数T(1 ≤ T ≤ 10000)，表示样例的个数。 以后每行一个样例，为一个十进制正整数x(1 ≤ x ≤ 109)。
输出
每行输出一个样例的结果。
样例
输入
5
1
10
100
1000
1000000000
输出
1
14
367
10966
4083305275263
题意
贪心问题， 直接讲前缀和求出，然后暴力枚举即可
AC代码
#include <cstring>
#include <iostream>
using namespace std;
int fib[
46];
bool b[
46];
int main()
{
long long ans, tem;
fib[
0] =
0;
fib[
1] =
1;
fib[
2] =
2;
for (
int i =
3; i <
45; i++)
fib[i] = fib[i -
1] + fib[i -
2];
int t, n, p;
scanf(
"%d", &t);
while (t--)
{
ans =
0LL;
tem =
1LL;
memset(b,
0,
sizeof b);
scanf(
"%d", &n);
for (p =
44; p && n; p--)
{
if (n >= fib[p])
{
n -= fib[p];
b[p] =
true;
}
}
for (
bool isChange =
true; isChange;)
{
isChange =
false;
for (
int i =
3; i <
45; i++)
if (b[i] && !b[i -
1] && !b[i -
2])
{
b[i] =
false;
isChange = b[i -
1] = b[i -
2] =
true;
}
}
for (
int i =
1; i <
45; i++)
{
if (b[i])
ans += tem;
tem *=
2;
}
printf(
"%lld\n", ans);
}
return 0;
}
