Atcoder rc122-c Calculator 斐波那契

Atcoder rc122-c Calculator  斐波那契

传送门


题解


先说结论: 任意正整数可以拆分成若干个斐波那契数

斐波那契数列: 1 1 2 3 5 8 13 21 34
例 17 = 13 + 3 + 1
看上去是对的,怎么证明呢?
首先假如每一个斐波那契数可以重复多次,那么显然成立(因为可以重复使用\(1\)来构成)
进一步 因为\(f_{x} = f_{x-1} + f_{x-2}\), \(f_{x-1} > f_{x-2}\) 所以 \(f_{x} < 2f_{x-1}\)
假设我们使用了两次\(f_{x-1}\), 那么我们可以使用一次类似进位的操作把他进成\(f_{x}\)(剩下的递归构造)
这样一旦有重复的我们就进位,最后可以得到一个不重复的子数列

也就是说 任意正整数可以拆分成若干个斐波那契数的和
(我把这玩意称作斐波那契进制数?

好了,回到我们这道题目上来, 不难发现反复进行3,4操作实际上就是在计算斐波那契数列
那么问题来了我们可以通过这个方式来得到一个斐波那契数,但是怎么才能得到若干个斐波那契数的和呢
来看看,我们让第三个斐波那契数加1(其实就是在计算过程中使用1, 2操作

1 2 3 4 5 6 7 8 9 10
1 1 2 3 5 8 13 21 34 55
1 1 3 4 7 11 18 29 47 76
+0 +0 +1 +2 +3 +5 +8 +13 +21 +34

容易发现我们在第三项加一,后面增加的数又构成了斐波那契数列。
对, 就是你想的那样, 我们想要让x最终变成76 (55 + 34)的话, 就直接在第三项计算完之后调用操作1/2,让他加一,这样在计算到55时,就会加34, 也就是 55 + 34 = 76;

好了,剩下的就只有推式子和实现了。

void pre(){
	f[0]=0, f[1]=1;
	for(int i=2; i<=100; i++) f[i] = f[i-1] + f[i-2];
}

int main(){
	a=read();
	pre();
	
	n=100;
	while(f[n] > a) n--;
	
	for(int i=n; i>0; i--){
		if(a>=f[i]){
			v[n-i+1] = 1;
			a -= f[i];
		}
	}
	
	int ans = 0;
	cout << 130 << endl;
	
	int it = (n%2);
	for(int i=1; i<=n; i++){
		
		if(i != 1){
			ans++;
			cout << it?3:4 << endl; 
		}
		
		if(v[i]){
			ans++;
			cout << it?1:2 << endl;
		}
		it = !it;
	}
	
	for(int i=ans; i<130; i++) cout << 4 << endl;
	return 0;
} 
上一篇:Kong APIGateway 部署


下一篇:C语言风格的字符串