迭代算法與遞歸算法

選修一：數(shù)據(jù)結構探究一：寫一段程序實現(xiàn)求n！迭代是重復反饋過程的活動，其目的通常是為了使結果符合目標要求n=5result=n#第一次迭代result=n*4#第二次迭代result=n*3#第三次迭代result=n*2#第四次迭代result=n*1#第五次迭代迭代關系式探究一：迭代的概念迭代算法：①重復反饋的過程②迭代過程：對迭代過程的重復③每一次迭代結果會被用來作為下一次迭代的初始值探究一：迭代的概念迭代算法解決問題過程：①確定迭代變量。迭代算法處理的問題時，由舊值遞推出新值的變量稱為迭代變量。②建立迭代關系式（數(shù)值關系）。從變量的前一個值推出其下一個值的公式（或關系）。③控制迭代過程（結束條件）。迭代過程在經過若干次重復執(zhí)行以后要能結束，因此，要設定迭代結束的條件。探究二：迭代算法求a的平方根迭代算法：①確定迭代變量②建立迭代關系式③控制迭代過程

探究二：迭代算法求a的平方根迭代算法：①確定迭代變量②建立迭代關系式③控制迭代過程每次迭代結果將作為下一次迭代的初始值1（n=1）n*fac(n-1)（n≠1）fac(n)探究三：遞歸算法求n！遞歸：大問題中嵌套小問題，通過調用自身，不斷降低問題的規(guī)模，進而求解n=55！=5*4！4！=4*3！3！=3*2！2！=2*1！1！=1遞推：分解問題回歸：代值求解fac(4)4*fac(3)第1次調用第2次調用3*fac(2)第3次調用2*fac(1)第4次調用1返回值1返回值1返回值2返回值6探究三：遞歸過程探究三：遞歸算法求n！遞歸：大問題中嵌套小問題，通過調用自身，不斷降低問題的規(guī)模，進而求解1（n=1）n*fac(n-1)（n≠1）fac(n)設計遞歸算法：確定遞歸公式和遞歸結束條件探究四：如何用棧實現(xiàn)遞歸1*fac(0)2*fac(1)3*fac(2)4*fac(3)5*fac(4)fac(1)fac(2)fac(3)fac(4)fac(5)通過不斷的調用自己縮小問題規(guī)模，進而求解?？臻g復雜度大探究五：辨析迭代與遞歸迭代：由舊值不斷推出新值的過程。它包括三個方面：①確定迭代變量；②建立迭代關系式；③控制迭代過程，使程序能夠停止下來。遞歸：是一種縮小問題規(guī)模，進而構造出整個問題解的思想方法。①遞推

②回歸迭代難點：建立正確的迭代公式，通常要借助循環(huán)語句。遞歸難點：思想比較難以理解，遞歸程序的效率相對不高。探究五：辨析迭代與遞歸斐波那契數(shù)列是這樣一個數(shù)列：1,1,2,3,5,8,13,21,34，…，其定義如下：f(0)=0，f(1)=1，f(n)=f(n-1)+f(n-2)(n>=2)。編程求f(40)的值迭代程序f0=0f1=1n=2whilen<=40:f=f1+f0f0=f1f1=fn=n+1print(f1)遞歸程序deffib(n):ifn<1:return0elifn==1: