斐波南希数列

今天emm扔了个一些数给我:1 2 3 5 8 13 21,叫我列出个公式,我鼓捣了半天,才恍然想起这是个数列,由数列我又发散性的想到数学归纳等初等数学方法并为之激动不已--我tm也算个读书人呀,当然高等数学概念自然不会浮现于我的脑海,因为它们从来就没有进过我的脑袋。
憋了半天,我终于惊喜的发现这个数列的规律,从第三个数起,每个数是前两个数之和,于是我列出了这样的公式:

(n = 1) f(n) = 1
(n = 2) f(n) = 2
(n > 2) f(n) = f(n - 1) + f(n - 2)

写完了有点不放心,于是把这列数copy到google搜索栏里,结果出来一个似曾相识的名词:Fibonacci数列,仔细看了下描述确定我的公式的正确性,迫不及待的发给emm,并为自己用f(n)这样的很专业的写法而窃喜,这个公式编程实现肯定没问题了,递归好了,结果emm偏偏不要递归,嫌效率太低,于是我们上网找非递归的通项公式,结果找到个很bt的,我看了下用那个通项公式循环还未必用这个递归的效率高,于是劝emm作罢,可他执意要个循环的,于是我想了个用空间换时间的办法:

int nums[] = new int[n];
nums[0] = 1;
nums[1] = 2;

for ( i = 2 ; i < n ; i ++ )
{
    nums[i] = nums[i-1] + nums[i - 2];
}

emm又嫌n大的时候太浪费内存,正在我又陷入思考时,emm职业习惯性的冒了一句:用寄存器就不会浪费了。我恍然,鼓捣了半天发过去:

mov ecx, n
cacl:
mov eax, 1
mov ebx, 2
xor edx, edx
add edx, eax
add edx, ebx
push edx
push loc... -&gt; "%d,"
call printf
mov eax, ebx
mov ebx, edx
loop cacl

发过去突然想起来printf是lib c函数,要自己恢复堆栈,于是忙补上一句:'错了,printf要恢复堆栈' 。emm汗……
他很快他搞出了这个完整实现:

__asm
{
 pushad
 mov ebx,N

 inc ebx
 xor ecx, ecx
 xor eax, eax
 mov esi, 1
 mov edi, 2

 mov ecx, 2
fa:  
 inc ecx
 cmp ecx, ebx
 je  fEND

 mov eax, esi
 add eax, edi
 mov esi, edi
 mov edi, eax
 jmp fa

fEND:
 mov M, eax
 popad
}

感叹了下,觉得用汇编在优化算法的时候果然很有用,貌似以前我只用它来搞搞逆向,了解了解流程。
后来我们又嘲笑了下一个连什么是通项公式都不知道的牛人,笑罢我指出我们是在五十步笑百步,emm再汗……

原文地址:https://www.cnblogs.com/luoluo/p/349502.html