[理學(xué)]計(jì)算機(jī)算法基礎(chǔ)第一章-資料下載頁(yè)
2025-01-21 13:29本頁(yè)面
【正文】 用的返回地址。 ⑵ 將標(biāo)號(hào) L1附于第一條可執(zhí)行語(yǔ)句。然后對(duì)于每一處遞歸調(diào)用都用一組執(zhí)行下列規(guī)則的指令來(lái)代替。 ? 處理遞歸調(diào)用語(yǔ)句 ⑶ 將所有參數(shù)和局部變量的值存入棧。 棧頂指針 可作為一個(gè)全程變量來(lái)看待。 ⑷ 建立第 i個(gè)新標(biāo)號(hào) Li，并將 i存入棧。這個(gè)標(biāo)號(hào)的 i值將用來(lái)計(jì)算返回地址。 此標(biāo)號(hào)放在規(guī)則⑺所描述的程序段中。 ⑸ 計(jì)算這次調(diào)用的各實(shí)在參數(shù)（可能是表達(dá)式）的值，并把這些值賦給相應(yīng)的形式參數(shù)。 ⑹ 插入一條無(wú)條件轉(zhuǎn)向語(yǔ)句轉(zhuǎn)向過(guò)程的開(kāi)始部分： Goto L1 ? 對(duì)遞歸嵌套調(diào)用的處理 ⑺ 如果這過(guò)程是函數(shù)，則對(duì)遞歸過(guò)程中含有此次函數(shù)調(diào)用的那條語(yǔ)句做如下處理：將該語(yǔ)句的此次函數(shù)調(diào)用部分用從棧頂取回該函數(shù)值的代碼來(lái)代替，其余部分的代碼按原描述方式照抄，并將⑷中建立的標(biāo)號(hào)附于這條語(yǔ)句上。 如果此過(guò)程不是函數(shù)，則將⑷中建立的標(biāo)號(hào)附于⑹所產(chǎn)生的轉(zhuǎn)移語(yǔ)句后面的那條語(yǔ)句。 以上步驟實(shí)現(xiàn)消去過(guò)程中的遞歸調(diào)用。下面對(duì)過(guò)程中出現(xiàn) return語(yǔ)句 進(jìn)行處理（純過(guò)程結(jié)束處的 end可看成是一條沒(méi)有值與之聯(lián)系的 return語(yǔ)句）。 ? 對(duì)每個(gè)有 return語(yǔ)句的地方，執(zhí)行下述規(guī)則 ： ⑻ 如果棧為 空 ，則執(zhí)行 正常返回 。 ⑼ 否則，將所有輸出參數(shù)（帶有返回值的出口參數(shù)， out/inout型）的當(dāng)前值賦給棧頂上的那些對(duì)應(yīng)的變量。 ⑽ 如果棧中有返回地址標(biāo)號(hào)的下標(biāo)，就插入一條此下標(biāo)從棧中退出的代碼，并把這個(gè)下標(biāo)賦給一個(gè)未使用的變量。 ⑾ 從棧中退出所有局部變量和參數(shù)的值并把它們賦給對(duì)應(yīng)的變量。 ⑿ 如果這個(gè)過(guò)程是函數(shù)，則插入以下指令，這些指令用來(lái)計(jì)算緊接在 return后面的表達(dá)式并將結(jié)果值存入棧頂。 ⒀ 用返回地址標(biāo)號(hào)的下標(biāo)實(shí)現(xiàn)對(duì)該標(biāo)號(hào)的轉(zhuǎn)向。 例 遞歸調(diào)用示例 求數(shù)組元素中的最大值 算法 遞歸求取數(shù)組元素的最大值 procedure MAX1(i) // 查找數(shù)組 A中最大值元素，并返回該元素的最大下標(biāo)。 // global integer n,A(1:n),j,k integer i if in then j←MAX1(i+1) //遞歸調(diào)用 // if A(i) A(j) then k←i else k←j endif else k←n endif return(k) //遞歸調(diào)用的返回 // end MAX1 ? 消去上例中的遞歸 ? 算法 使用上述的規(guī)則消去例 procedure MAX2(i) local integer j,k。 global integer n, A(1:n) integer I integer STACK(1:2*n) top←0 //規(guī)則 1，聲明棧的代碼，并初始化為空 // L1: if in //規(guī)則 2，將標(biāo)號(hào) L1賦于第一條可執(zhí)行語(yǔ)句前 // then top ←top + 1。 STACK(top)← i。 // 規(guī)則 3，參數(shù)或局 部變量的值入棧 // top ←top +1。 STACK(top)← 2。 // 規(guī)則 4，建立新的 標(biāo)號(hào) 2，并入棧 // i ← i+1 // 規(guī)則 5， 計(jì)算參數(shù)值 // goto L1 //規(guī)則 6， 無(wú)條件轉(zhuǎn)向算法的開(kāi)始部分 // L2: j ←STACK(top)。 top ←top 1。 // 規(guī)則 7， 處理函數(shù)調(diào)用，并將標(biāo)號(hào) 2賦于該語(yǔ)句上 // if A(i) A(j) then k ←I else k ←j endif else k ←n endif if top = 0 then return(k) // 規(guī)則 8， 如果?？?，則正常返回 // else addr ←STACK(top)。top ←top 1。 // 規(guī)則 10， 從 棧中退出返回標(biāo)號(hào) // i ←STACK(top)。top ←top 1。 // 規(guī)則 11， 從棧中退 出局部變量和參數(shù)的值 // top ←top+1。STACK(top) ← k。 // 規(guī)則 12， 計(jì)算返 回值，并將之入棧 // if addr = 2 then goto L2 endif // 規(guī)則 13， 用返回 地址標(biāo)號(hào)的下標(biāo)實(shí)現(xiàn)對(duì)該標(biāo)號(hào)的轉(zhuǎn)向 // endif end MAX2 ? 進(jìn)一步優(yōu)化和簡(jiǎn)化經(jīng)過(guò)消去遞歸產(chǎn)生的迭代程序。 算法 算法 procedure MAX3(A,n) integer i,k,n。 i ←k ←n while i1 do i ←i 1 if A(i) A(k) then k ←i endif repeat return(k) end MAX3 不必死套 13條規(guī)則，應(yīng)具體情況具體分析 procedure GCD1(a,b) // 約定 ab // L1: if b=0 then return(a) else t ←b。b ←a mod b。a ←t。go to L1 endif end GCD1 整理后得 ： procedure GCD2(a,b) while b≠ 0 do t ←b。b ←a mod b。a ←t repeat return(a) end GCD2
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1