數(shù)據(jù)結(jié)構(c)--遞歸-資料下載頁
2025-07-25 09:07本頁面
【正文】 6/44 定義兩個變量 pre1和 pre2，分別記錄上述遞推關系中兩個子問題的解，即 pre1=p(i2,x)， pre2=p(i1,x)， 且 pre1和 pre2的值始終隨著 i的值的改變而發(fā)生變化：每當新求出第 i階多項式的值后， i的值要增加 1，而在此之前應該 修改 pre1和 pre2的值，用 pre1記錄 pre2當前 的值，而用 pre2記錄 新求出 的多項式的值，直至 i=n。 float p ( int n, float x ) { float pre1,pre2,a,b,valuep。 int i。 if (n==0) return()。 else if (n==1) return(x)。 37/44 else { pre1=。 pre2=x。 for (i=2。i=n。++i) { a=2*i1。 b=i1。 valuep=(a*pre2*xb*pre1)/i。 pre1=pre2。 pre2=valuep。 } return(valuep)。 } } 勒讓德多項式的非遞歸算法 38/44 復雜遞歸程序到非遞歸程序的轉(zhuǎn)換 ? 復雜遞歸問題在求解的過程中無法保證求解動作一直向前， 往往需要設置一些回溯點 ，當求解無法進行下去或當前處理的工作已經(jīng)完成時，必須退回到所設置的回溯點，繼續(xù)問題的求解。因此，在使用非遞歸方式實現(xiàn)一個復雜遞歸問題的算法時，經(jīng)常使用 棧 來記錄和管理所設置的回溯點。 39/44 ? 按中點優(yōu)先的順序遍歷線性表問題： ? 已知線性表 list以順序存儲方式存儲，要求按以下順序輸出 list中所有結(jié)點的值：首先輸出線性表 list中點位置上的元素值，然后輸出中點左部所有元素的值，再輸出中點右部所有元素的值；而無論輸出中點左部所有元素的值還是輸出中點右部所有元素的值，也均應遵循以上規(guī)律。 例如： 40/44 例如， 已知數(shù)組 list中元素的值為： 18 32 04 09 26 06 10 30 12 08 45 則 list中元素按中點優(yōu)先順序遍歷的輸出結(jié)果為： 06 04 18 32 09 26 12 10 30 08 45 試采用遞歸和非遞歸算法實現(xiàn)該遍歷問題。 left mid1 mid mid+1 right 41/44 define MAXSIZE 20 typedef int listarr[MAXSIZE]。 void listorder(listarr list, int left, int right) { int mid。 if (left=right) { mid=(left+right)/2。 coutlist[mid]“ ”。 listorder(list,left,mid1)。 listorder(list,mid+1,right)。 } } 遞歸實現(xiàn)算法 42/44 define MAXSIZE 20 typedef int listarr[MAXSIZE]。 void listorder(listarr list, int left, int right) { typedef struct { int l。 /*存放待處理數(shù)組段的起點下標 */ int r。 /*存放待處理數(shù)組段的終點下標 */ } stacknode。 /*棧中每個元素的類型 */ stacknode stack[MAXSIZE]。 int top, i, j, mid。 /*top為棧頂指針 */ 非遞歸實現(xiàn)算法 43/44 if (left=right) /*數(shù)組段不為空 */ { top= 1。 i=left。 j=right。 while (i=j || top!=1) { /*當前正在處理的數(shù)組段非空或棧非空 */ if (i=j) { mid=(i+j)/2。 coutlist[mid]“ ”。 ++top。 stack[top].l=mid+1。 stack[top].r=j。 j=mid1。 } else { /*當前正在處理的數(shù)組段為空時進行回溯 */ i=stack[top].l。 j=stack[top].r。 top 。 } } } } 44/44
公司管理相關推薦
鄂ICP備17016276號-1