斐波那契数列为 1,1,2,3,5,8,13,21,... 其元素产生的规则是前两个数为 ，从第三个数开始每个数等于它前面两个数之和。已知任意一个正整数可以表示为若干个互不相同的斐波那契数之和。
例如: $36=21+13+2$。
下面的程序是由键盘输入一个正整数 $n$ ，输出组成 $n$ 的互不相同的斐波那契数。
算法说明:
1. 寻找小于等于 $n$ 的最大斐波那契数 $a$ ，并以 $a$ 作为组成 $n$ 的一个数。
2. 若 $n \not{=} a$ ，则以 $n-a$ 作为 n 的新值，重复步骤(1)。
3. 若 $a=n$ ，则结束。
#include<iostream>
#include<cstdio>
using namespace std;
int n;
bool first;
int find(int n) {
int a, b, c;
a = 1;
b = 1;
do{
c = a + b;
___(1)___;
} while (b < n);
if (___(2)___)
return b;
else
___(3)___;
}
void p(int n) {
int a;
a = find(n);
if (first) {
printf("%4d", a);
first = false;
} else
___(4)___;
if (a < n) ___(5)___;
}
int main() {
cin >> n;
first = true;
printf("%5d = ", n);
p(n);
cout << endl;
return 0;
}
1. B。
2. B。
3. B。
4. C。
5. D。
关于算法思路，题目中已经写的很明白了。在代码中，是通过 p 函数来进行递归的，在每次递归中通过 `find(int n)` 函数来找最大的小于 n 的斐波那契数，并将其返回。在 `find` 函数中，要注意的是这里采用三变量的方法来滚动地求解斐波那契数。