大學計算機基礎(chǔ) 課件 10.5.1算法分析

大學計算機基礎(chǔ)——基于計算思維（Windows10+Office2016）第10章算法思維與運用10.5.1算法分析10.5遞歸算法問題6遞歸算法年齡問題：5個人坐在一起論年齡。問第5個人多少歲，他說比第4個人大2歲。問第4個人多少歲，他說比第3個人大2歲。問第3個人多少歲，他說比第2個人大2歲。問第2個人多少歲，他說比第1個人大2歲。問第1個人多少歲，他說10歲。請問第5個人幾歲？問題7遞歸算法求n的階乘：f(n)=1*2*3*4*…*n1．問題分析遞歸算法問題6和7都可以借助循環(huán)結(jié)構(gòu)實現(xiàn)問題6兩個問題的特點age(n)=age(n-1)+2(n>1)問題7factorial(n)=factorial(n-1)*n(n>1)1．問題分析遞歸算法問題的定義直接或間接地出現(xiàn)其本身的引用遞歸定義大問題小問題小問題小問題小問題小問題小問題小問題小問題小問題直接求解1．問題分析遞歸算法①遞歸體就是遞歸求解時的遞推關(guān)系，或者簡稱為遞推式。遞歸模型②遞歸出口就是遞歸何時結(jié)束的條件，或者稱為初始條件。1．問題分析遞歸算法問題6的遞歸模型遞歸模型問題7的遞歸模型1．問題分析遞歸算法遞推階段遞歸算法的執(zhí)行過程分成遞推和回歸兩個階段:把比較復雜的問題（規(guī)模為n）的求解推到比原問題簡單一些的問題（規(guī)模小于n）的求解，直至遇到遞歸出口，分解過程結(jié)束。例如：age(n)age(n-1)age(n-2)age(1)101．問題分析遞歸算法回歸階段遞歸算法的執(zhí)行過程分成遞推和回歸兩個階段:當獲得最簡單情況的解后，逐級返回，依次得到稍復雜問題的解。例如：age(n)age(n-1)age(n-2)age(1)102．算法實現(xiàn)遞歸算法（1）設(shè)計遞歸模型子程序在創(chuàng)建遞歸模型子程序時，一般應(yīng)將問題規(guī)模n作為輸入?yún)?shù)，而且一定要有輸出參數(shù)保存每次回歸階段返回的值。2．算法實現(xiàn)遞歸算法（1）設(shè)計遞歸模型子程序①判斷是否達到遞歸出口條件（一般就是判斷問題規(guī)模n是否達到可求解規(guī)模）。遞歸子程序的設(shè)計思路一般是：2．算法實現(xiàn)遞歸算法（1）設(shè)計遞歸模型子程序②若遞歸出口條件成立，計算最簡單情況的解。遞歸子程序的設(shè)計思路一般是：2．算法實現(xiàn)遞歸算法（1）設(shè)計遞歸模型子程序③若遞歸出口條件不成立，則先要調(diào)用其自身，注意參數(shù)規(guī)模要變?。ㄏ喈斢谟嬎愠鲞f推公式中的子問題），然后再按遞推公式計算出本次規(guī)模的解。遞歸子程序的設(shè)計思路一般是：2．算法實現(xiàn)遞歸算法（2）設(shè)計遞歸main子圖一般在遞歸主程序中，用求解問題的實際規(guī)模作為實際的輸入?yún)?shù)調(diào)用遞歸子程序，然后輸出結(jié)果即可。年齡遞歸的main