Windows汇编语言程序设计同步练习大全
Windows汇编语言程序设计同步练习大全
;《Windows汇编语言程序设计教程》p170习题7:
;用递归子程序显示Fibonacci数列,Fibonacci数列Fn定义为:F0=0,F1=1,F2=1,Fn=Fn-2+Fn-3(n>=3)。
;2006-12-15 高玉涵
;程序不考虑处理负数与溢出。
.386
.model flat,stdcall
option casemap:none
includelib /masm32/lib/msvcrt.lib
printf PROTO C :dword, :vararg
scanf PROTO C :dword, :vararg
.data
dVar dword 6
szMsg1 byte '请输入一个大于2的整数:', 0
szMsg3 byte 'F%d = %d', 0ah, 0
szMsg4 byte 'ebx=%d', 0ah, 0
szInputFmt byte '%d', 0
.code
Fibonacci proc C n:dword
local dret:dword ;存放子程序的返回值。
local dvar:dword ;存放n值(中间计算)。
cmp n, 2
jle exitrecurse ;n<=2
push n
pop dvar ;dvar=n
dec dvar ;n-1
invoke Fibonacci, dvar ;Fibonacci(n-1)
mov dret, eax ;保存上次调用的返回值。
dec dvar ;相当于n-2
invoke Fibonacci, dvar ;Fibonacci(n-2)
add eax, dret ;eax子程序返回值,eax=n-1+n-2。
ret
exitrecurse:
mov eax, 1 ;保存子程序返回值。
ret
Fibonacci endp
start proc
invoke printf, offset szMsg1 ;提示。
invoke scanf, offset szInputFmt, offset dVar ;获取用户输入的值。
cmp dVar, 2
jle exitrecurse ;dVar<=2,退出。
mov ecx, dVar
lop:
push ecx ;保存ecx值。
invoke Fibonacci, ecx
invoke printf, offset szMsg3, ecx, eax
pop ecx ;还原ecx值。
loop lop
exitrecurse:
ret
start endp
end start
程序运行结果:
请输入一个大于2的整数:7
F7 = 13
F6 = 8
F5 = 5
F4 = 3
F3 = 2
F2 = 1
F1 = 1
注:
程序中有一个陷阱:它使用递归步骤计算Fibonacci(n-1)和Fibonacci(n-2),但是,在计算Fibonacci(n-1)时也将计算Fibonacci(n-2),这个额外的计算代价有多大呢?
答案是:它的代价远远不止一个冗余计算:每个递归调用都触发另外两个递归调用,而这两个调用的任何一个还将触发两个递归调用,再接下去的调用也是如此。这样,冗余计算数量增长得非常快。例如:在递归计算Fibonacci(10)时,Fibonacci(3)的值被计算了21次。但是,在递归计算Fibonacci(30)时,Fibonacci(3)的值被计算了317,811次。当然,这317,811次计算所产生的结果是完全一样的,除了其中之一外,其余的纯属浪费。这个额外的开销真是相当恐怖!