【一级讲解】斐波那契的拆分——栈与贪心

斐波那契的拆分

提交2.55k

通过1.18k

时间限制1.00s

内存限制125.00MB

提交答案

题目描述

已知任意一个正整数都可以拆分为若干个斐波纳契数，现在，让你求出n的拆分方法

输入格式

一个数t，表示有t组数据

接下来t行，每行一个数n（如题）

输出格式

t行，每行一个字符串，表示拆分方法（格式:n=a1+a2+a3+…+an），要求从小到大输出

输入输出样例

输入 #1

1
1

输出 #1

1=1

输入 #2

1
10

输出 #2

10=2+8

说明/提示

若有多组数据，以个数最小的为准，若仍有多组，输出右边尽量大的一组

对于100%的数据 t<=1000 1<=n<=10^9

---

问题分析：

既然你要拆分成若干个斐波那契数，那首先你要先有这个数字才行呀~所以一眼看过去肯定是要先打表把10^9以内的斐波那契数给记录下来。因此我们得到一个子任务

任务一：把10^9以内的斐波那契数给记录下来

const int N 10000000000;
bool mark[N];

int main()
{
	int fibo[45];
	fibo[1]=fibo[2]=1;
	
	int i;
	for ( i=3; ; ++i )
	{
		fibo[i] = fibo[i-1]+fibo[i-2];
		if ( fibo[i] > N )
			break;
		mark[fibo[i]]=1;
	}
	
}

好了，我们现在已经有e9以内的斐波那契数了，那么如何拼凑呢?

任务二：如何将任意一个正整数都可以拆分为若干个斐波纳契数

其实这个问题是同年级的一个同学问我的，当时他问如何才能不重复地又能刚好选到我需要的斐波那契数呢？

一开始我想到的解决方案是拆分法，即把你要求的正整数n拆分成n个1，然后用这n个1凑成一个个斐波那契数，但后来我又自己否定了自己的这个方法，因为它没有随机性，更没有可操作性。

emmmm，可能很多人都卡在这一个问题，但我觉得思维不要太局限，当你在一个思路卡很久解决不了问题的时候，不妨换个思路想想。然后我想的是用树的结构，左边放的数值比右边的大，从树根一直检索到树叶，从树根加起，如果加上两边都大于n，则选小的那一边再检索，直到和为n。

上面那个是完整版，有点乱，我做完剪枝后如下图，这样就满足了随机性和不重复性。

现在问题就来了，如何用代码实现呢？

		stack<int> f;
		if ( mark[n] )
			f.push(n);
		else
		{
			for ( i=n-1; i>=1; --i )
			{
				if ( mark[i] && n>0 )
				{
					f.push(i);
					n -= i;
					i = n+1;
				}	
				if ( n==0 )	break;
			}
		}

再结合题目的要求，我采用的栈的方式来实现（数组也行，只不过后面要倒序输出）

---

AC代码：

#include <bits/stdc++.h>
using namespace std;

const int N=1000000000;
bool mark[N];

int main()
{
	int fibo[45];
	fibo[1]=fibo[2]=1;
	mark[1]=1;
	
	int i;
	for ( i=3; ; ++i )
	{
		fibo[i] = fibo[i-1]+fibo[i-2];
		if ( fibo[i] > N )
			break;
		mark[fibo[i]]=1;
	}
	
	int t;
	cin >> t;
	while ( t-- )
	{
		int n;
		cin>>n;
		cout << n << "=";
		
		stack<int> f;
		if ( mark[n] )
			f.push(n);
		else
		{
			for ( i=n-1; i>=1; --i )
			{
				if ( mark[i] && n>0 )
				{
					f.push(i);
					n -= i;
					i = n+1;
				}	
				if ( n==0 )	break;
			}
		}
		
		cout << f.top();
		f.pop();
		int len=f.size();
		for ( i=1; i<=len; ++i )
		{
			cout << "+" << f.top();
			f.pop();
		}
		putchar('\n');
	}
	
	return 0;
}