一楼防被吞

都知道怎么写求GCD(最大公约数)和Fibonacci数列的算法，那么我先给出我的方法:
int Eculid(double x，double y)
{
if((x/y)%1==0)
return x/y;
else
Eculid(y，x%y);
}
//上面的算法是简化过的
long long Fib(int x)
{
if(x==1||x==2)
return 1;
else
return Fib(x-1)+Fib(x-2);
}
//同样，也是简化过的
//
那么就提出一个证明:
如果Ecuclid算法需要k步来计算两个数的GCD，那么这两个数之中较小的一个必然大于等于Fibonacci数列的第k项。

翻了一下SICP才找到比较简略的证明:证明如下:
设存在数对序列(ak，bk)//k是脚码，其中ak＞bk，假设欧几里得算法在第k步结束。
首先证明一个基础定理:若(ak+1，bk+1)，(ak，bk)，(ak-1，bk-1)是规约数列中连续的三个数对，那么必有bk+1≥bk+bk-1。//再次声明，式中出现的k，k-1，k+1都是脚码
假设上述定理成立，由算法可知，b≥1，那么当k(算法结束所需步骤)为一时结论成立，因为此时Fib(1)=1
接下来假设所有小于k的整数都成立，那么设法建立对k+1的结果。
令(ak+1，bk+1)，(ak，bk)，(ak-1，bk-1)是归约数对连续三个数对，我们有 bk≥Fib(k)和bk-1≥Fib(k-1)，这样，应用已证明的定理和Fibonacci的定义，可以给出bk+1≥bk+bk-1≥Fib(k+1)，这就完成了拉密定理的证明

如何证明基础的定理呢，证明如下:
我们需要注意到，这里的每个归约步骤都是通过应用变换ak-1=bk，bk-1=ak除以bk的余数。第二个等式意味着ak=qbk+bk-1，其中q是某个正整数，因为q至少是一，所以应该有ak=qbk+bk-1≥bk+bk-1，但前面有一个归约步骤bk+1=ak，因而bk+1=ak≥bk+bk-1，便证明了上述定理

O.O不明觉厉，算法纯小白路过，”算法导论”至今放家沾灰

我们学校的各种竞赛资格都属于重点班的学生（实际上他们怎么会有空）。我成绩不算重点