大學(xué)計(jì)算機(jī)基礎(chǔ) 課件 10.5.1算法分析

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