計(jì)算機(jī)編程 已知An為整數(shù)數(shù)組試寫(xiě)出實(shí)現(xiàn)下列運(yùn)算的遞歸算法

5-1已知A[n]為整數(shù)數(shù)組，試寫(xiě)出實(shí)現(xiàn)下列運(yùn)算的遞歸算法： (1)求數(shù)組A中的最大整數(shù)。 (2)求n個(gè)整數(shù)的和。 (3)求n個(gè)整數(shù)的平均值?！窘獯稹?#include<iostream.h>

classRecurveArray{ //數(shù)組類聲明

private:

int*Elements; //數(shù)組指針

intArraySize; //數(shù)組尺寸intCurrentSize; //當(dāng)前已有數(shù)組元素個(gè)數(shù)

public: RecurveArray(intMaxSize=10):ArraySize(MaxSize),Elements(newint[MaxSize]){}

~RecurveArray(){delete[]Elements;}

voidInputArray(); //輸入數(shù)組的內(nèi)容

intMaxKey(intn); //求最大值

intSum(intn); //求數(shù)組元素之和 floatAverage(intn); //求數(shù)組元素的平均值};voidRecurveArray::InputArray(){ //輸入數(shù)組的內(nèi)容 cout<<"InputthenumberofArray:\n"; for(inti=0;i<ArraySize;i++)cin>>Elements[i];}intRecurveArray::MaxKey(intn){ //遞歸求最大值 if(n==1)returnElements[0]; inttemp=MaxKey(n-1); if(Elements[n-1]>temp)returnElements[n-1]; elsereturntemp;}intRecurveArray::Sum(intn){ //遞歸求數(shù)組之和 if(n==1)returnElements[0]; elsereturnElements[n-1]+Sum(n-1);}floatRecurveArray::Average(intn){ //遞歸求數(shù)組的平均值 if(n==1)return(float)Elements[0]; elsereturn((float)Elements[n-1]+(n-1)*Average(n-1))/n;}intmain(intargc,char*argv[]){

intsize=-1; cout<<"No.oftheElements:"; while(size<1)cin>>size; RecurveArrayra(size); ra.InputArray(); cout<<"\nThemaxis:"<<ra.MaxKey(ra.MaxSize)<<endl; cout<<"\nThesumis:"<<ra.Sum(ra.MaxSize)<<endl; cout<<"\ntheavris:"<<ra.Average(ra.MaxSize)<<endl; return0;}5-2已知Ackerman函數(shù)定義如下： (1)根據(jù)定義，寫(xiě)出它的遞歸求解算法； (2)利用棧，寫(xiě)出它的非遞歸求解算法?！窘獯稹?1)已知函數(shù)本身是遞歸定義的，所以可以用遞歸算法來(lái)解決： unsignedakm(unsignedm,unsignedn){ if(m==0)returnn+1; //m==0 elseif(n==0)returnakm(m-1,1); //m>0,n==0 elsereturnakm(m-1,akm(m,n-1)); //m>0,n>0 }為了將遞歸算法改成非遞歸算法，首先改寫(xiě)原來(lái)的遞歸算法，將遞歸語(yǔ)句從結(jié)構(gòu)中獨(dú)立出來(lái)： unsignedakm(unsignedm,unsignedn){ unsignedv;if(m==0)returnn+1; //m==0 if(n==0)returnakm(m-1,1); //m>0,n==0v=akm(m,n-1)); //m>0,n>0 returnakm(m-1,v); }計(jì)算akm(2,1)的遞歸調(diào)用樹(shù)如圖所示：

akm(2,1)akm(2,1)akm=5v=3akm=5v=3akm=5akm(1,3)v=akmakm=5akm(1,3)v=akm(2,0)v=4v=4akm=3akm(0,4)=5v=akm(1,2)akmakm=3akm(0,4)=5v=akm(1,2)akm(1,1)v=3akm(0,3)=4v=akm(1,1)akm(0,2)=3v=akm(1,0)v=3akm(0,3)=4v=akm(1,1)akm(0,2)=3v=akm(1,0)v=2akm(0,2)=3akm(0,1)=2v=akmv=2akm(0,2)=3akm(0,1)=2v=akm(1,0)v=2akmv=2akm(0,1)=2vmvnvmvnvmvnvmvnvmvnvmvn用到一個(gè)棧記憶每次遞歸調(diào)用時(shí)的實(shí)參值，每個(gè)結(jié)點(diǎn)兩個(gè)域{vm,vn}。對(duì)以上實(shí)例，棧的變化如下：vmvnvmvnvmvnvmvnvmvnvmvn1001100120111111022011111102改akm改akm(m-1,1)改akm(m-1,1)v=n+1=2改akm(m-1,v)改akm(m-1,v)v=n+1=3212121212113vmvnvmvnvmvnvmvnvmvnvmvnvmvnvmvnvmvnvmvnvmvnvmvn1111111102100112121201212120313131313131304改改akm(m-1,1)v=n+1=2改akm(m-1,v)改akm(m-1,v)改akm(m-1,v)棧空,返回v=5 v=n+1=3v=n+1=4v=n+1=5 相應(yīng)算法如下#include<iostream.h> #include“stack.h” #definemaxSize3500;unsignedakm(unsignedm,unsignedn){ structnode{unsignedvm,vn;} stack<node>st(maxSize);nodew;unsignedv; w.vm=m;w.vn=n;st.Push(w); do{ while(st.GetTop().vm>0){ //計(jì)算akm(m-1,akm(m,n-1)) while(st.GetTop().vn>0) //計(jì)算akm(m,n-1),直到akm(m,0) {w.vn--;st.Push(w);} w=st.GetTop();st.Pop(); //計(jì)算akm(m-1,1) w.vm--;w.vn=1;st.Push(w); } //直到akm(0,akm(1,*)) w=st.GetTop();st.Pop(); v=w.vn++; //計(jì)算v=akm(1,*)+1 if(st.IsEmpty()==0) //如果棧不空,改棧頂為(m-1,v){w=st.GetTop();st.Pop();w.vm--;w.vn=v;st.Push(w);} }while(st.IsEmpty()==0); returnv; } 5-3【背包問(wèn)題】設(shè)有一個(gè)背包可以放入的物品的重量為s，現(xiàn)有n件物品，重量分別為w[1],w[2],…,w[n]。問(wèn)能否從這n件物品中選擇若干件放入此背包中，使得放入的重量之和正好為s。如果存在一種符合上述要求的選擇，則稱此背包問(wèn)題有解(或稱其解為真)；否則稱此背包問(wèn)題無(wú)解(或稱其解為假)。試用遞歸方法設(shè)計(jì)求解背包問(wèn)題的算法。（提示：此背包問(wèn)題的遞歸定義如下：） 【解答】 根據(jù)遞歸定義，可以寫(xiě)出遞歸的算法。 enumboolean{False,True}booleanKnap(ints,intn){ if(s==0)returnTrue; if(s<0||s>0&&n<1)returnFalse; if(Knap(s–W[n],n-1)==True) {cout<<W[n]<<‘,’;returnTrue;} returnKnap(s,n-1); } 若設(shè)w={0,1,2,4,8,16,32}，s=51,n=6。則遞歸執(zhí)行過(guò)程如下遞歸Knap(51,6)returnTrue,完成Knap(51-32,5)returnTrue,打印32Knap(19-16,4)returnTrue,打印16Knap(3-8,3)returnFalseKnap(3,3)returnTrue,無(wú)動(dòng)作s=-5<0returnFalseKnap(3-4,4)returnFalseKnap(3,2)returnTrue,無(wú)動(dòng)作s=-1<0returnFalseKnap(3-2,1)returnTrue,打印2Knap(1-1,0)returnTrue,打印1s=0returnTrue5-4【八皇后問(wèn)題】設(shè)在初始狀態(tài)下在國(guó)際象棋棋盤上沒(méi)有任何棋子(皇后)。然后順序在第1行，第2行，…。第8行上布放棋子。在每一行中有8個(gè)可選擇位置，但在任一時(shí)刻，棋盤的合法布局都必須滿足3個(gè)限制條件，即任何兩個(gè)棋子不得放在棋盤上的同一行、或者同一列、或者同一斜線上。試編寫(xiě)一個(gè)遞歸算法，求解并輸出此問(wèn)題的所有合法布局。(提示：用回溯法。在第n行第j列安放一個(gè)棋子時(shí)，需要記錄在行方向、列方向、正斜線方向、反斜線方向的安放狀態(tài)，若當(dāng)前布局合法，可向下一行遞歸求解，否則可移走這個(gè)棋子，恢復(fù)安放該棋子前的狀態(tài)，試探本行的第j+1列。)【解答】此為典型的回溯法問(wèn)題。1#次對(duì)角線0#次對(duì)角線1#次對(duì)角線0#次對(duì)角線01232#次對(duì)角線01232#次對(duì)角線3#次對(duì)角線4#次對(duì)角線3#次對(duì)角線4#次對(duì)角線5#次對(duì)角線6#次對(duì)角線5#次對(duì)角線6#次對(duì)角線0#主對(duì)角線0#主對(duì)角線1#主對(duì)角線01231#主對(duì)角線01233#主對(duì)角線2#主對(duì)角線3#主對(duì)角線2#主對(duì)角線4#主對(duì)角線6#主對(duì)角線4#主對(duì)角線6#主對(duì)角線5#主對(duì)角線5#主對(duì)角線在解決8皇后時(shí)，采用回溯法。在安放第i行皇后時(shí)，需要在列的方向從1到n試探(j=1,…,n)：首先在第j列安放一個(gè)皇后，如果在列、主對(duì)角線、次對(duì)角線方向有其它皇后，則出現(xiàn)攻擊，撤消在第j列安放的皇后。如果沒(méi)有出現(xiàn)攻擊，在第j列安放的皇后不動(dòng)，遞歸安放第i+1行皇后。 解題時(shí)設(shè)置4個(gè)數(shù)組：col[n]：col[i]標(biāo)識(shí)第i列是否安放了皇后md[2n-1]：md[k]標(biāo)識(shí)第k條主對(duì)角線是否安放了皇后sd[2n-1]：sd[k]標(biāo)識(shí)第k條次對(duì)角線是否安放了皇后q[n]：q[i]記錄第i行皇后在第幾列利用行號(hào)i和列號(hào)j計(jì)算主對(duì)角線編號(hào)k的方法是k=n+i-j-1；計(jì)算次對(duì)角線編號(hào)k的方法是k=i+j。n皇后問(wèn)題解法如下：voidQueen(inti){ for(intj=0;j<n;j++){ if(col[j]==0&&md[n+i-j-1]==0&&sd[i+j]==0){ //第i行第j列沒(méi)有攻擊col[j]=md[n+i-j-1]=sd[i+j]=1;q[i]=j; //在第i行第j列安放皇后if(i==n){ //輸出一個(gè)布局for(j=0;j<n;j++)cout<<q[j]<<‘,’;cout<<endl;}else{Queen(i+1); //在第i+1行安放皇后 col[j]=md[n+i-j-1]=sd[i+j]=0;q[i]=0; //撤消第i行第j列的皇后 } }}5-5已知f為單鏈表的表頭指針,鏈表中存儲(chǔ)的都是整型數(shù)據(jù)，試寫(xiě)出實(shí)現(xiàn)下列運(yùn)算的遞歸算法： (1)求鏈表中的最大整數(shù)。 (2)求鏈表的結(jié)點(diǎn)個(gè)數(shù)。 (3)求所有整數(shù)的平均值。【解答】#include<iostream.h> //定義在頭文件"RecurveList.h"中classList; classListNode{ //鏈表結(jié)點(diǎn)類friendclassList;private: intdata; //結(jié)點(diǎn)數(shù)據(jù) ListNode*link; //結(jié)點(diǎn)指針 ListNode(constintitem):data(item),link(NULL){} //構(gòu)造函數(shù)};classList{ //鏈表類private: ListNode*first,current; intMax(ListNode*f); intNum(ListNode*f); floatAvg(ListNode*f,int&n);public: List():first(NULL),current(NULL){} //構(gòu)造函數(shù) ~List(){} //析構(gòu)函數(shù) ListNode*NewNode(constintitem); //創(chuàng)建鏈表結(jié)點(diǎn),其值為item voidNewList(constintretvalue); //建立鏈表,以輸入retvalue結(jié)束 voidPrintList(); //輸出鏈表所有結(jié)點(diǎn)數(shù)據(jù) intGetMax(){returnMax(first);} //求鏈表所有數(shù)據(jù)的最大值 intGetNum(){returnNum(first);} //求鏈表中數(shù)據(jù)個(gè)數(shù) floatGetAvg(){returnAvg(first);} //求鏈表所有數(shù)據(jù)的平均值}; ListNode*List::NewNode(constintitem){ //創(chuàng)建新鏈表結(jié)點(diǎn) ListNode*newnode=newListNode(item); returnnewnode;}voidList::NewList(constintretvalue){ //建立鏈表,以輸入retvalue結(jié)束 first=NULL;intvalue;ListNode*q; cout<<"Inputyourdata:\n"; //提示 cin>>value; //輸入while(value!=retvalue){ //輸入有效 q=NewNode(value); //建立包含value的新結(jié)點(diǎn) if(first==NULL)first=current=q; //空表時(shí),新結(jié)點(diǎn)成為鏈表第一個(gè)結(jié)點(diǎn)else{current->link=q;current=q;} //非空表時(shí),新結(jié)點(diǎn)鏈入鏈尾 cin>>value; //再輸入 } current->link=NULL; //鏈尾封閉} voidList::PrintList(){ //輸出鏈表 cout<<"\nTheListis:\n"; ListNode*p=first; while(p!=NULL){ cout<<p->data<<'';p=p->link; } cout<<‘\n’;} intList::Max(ListNode*f){ //遞歸算法:求鏈表中的最大值 if(f->link==NULL)returnf->data; //遞歸結(jié)束條件 inttemp=Max(f->link); //在當(dāng)前結(jié)點(diǎn)的后繼鏈表中求最大值 if(f->data>temp)returnf->data; //如果當(dāng)前結(jié)點(diǎn)的值還要大,返回當(dāng)前檢點(diǎn)值 elsereturntemp; //否則返回后繼鏈表中的最大值}intList::Num(ListNode*f){ //遞歸算法:求鏈表中結(jié)點(diǎn)個(gè)數(shù) if(f==NULL)return0; //空表,返回0 return1+Num(f->link); //否則,返回后繼鏈表結(jié)點(diǎn)個(gè)數(shù)加1}floatList::Avg(ListNode*f,int&n){ //遞歸算法:求鏈表中所有元素的平均值 if(f->link==NULL) //鏈表中只有一個(gè)結(jié)點(diǎn),遞歸結(jié)束條件{n=1;return(float)(f->data);} else{floatSum=Avg(f->link,n)*n;n++;return(f->data+Sum)/n;}}#include"RecurveList.h" //定義在主文件中intmain(intargc,char*argv[]){ Listtest;intfinished;cout<<“輸入建表結(jié)束標(biāo)志數(shù)據(jù)：”;cin>>finished; //輸入建表結(jié)束標(biāo)志數(shù)據(jù) test.NewList(finished); //建立鏈表 test.PrintList(); //打印鏈表cout<<"\nTheMaxis:"<<test.GetMax(); cout<<"\nTheNumis:"<<test.GetNum(); cout<<"\nTheAveis:"<<test.GetAve()<<'\n'; printf("HelloWorld!\n"); return0;}5-6畫(huà)出下列廣義表的圖形表示和它們的存儲(chǔ)表示： (1)D(A(c),B(e),C(a,L(b,c,d))) (2)J1(J2(J1,a,J3(J1)),J3(J1))【解答】(1)D(A(c),B(e),C(a,L(b,c,d))) (2)J1(J2(J1,a,J3(J1)),J3(J1))J1J1J2J2J3CBADJ3CBADccbaeLbaeLadcadc0J122∧J1∧A0B∧B0J122∧J1∧A0B∧B0A1e0A1e2∧20DD1c22∧20DD1c2J2∧1a20J22J2∧1a20J220C21aC∧0C21aC∧∧0J3J32∧0J3J32∧0L1d1c1bL∧0L1d1c1bL5-7利用廣義表的head和tail操作寫(xiě)出函數(shù)表達(dá)式，把以下各題中的單元素banana從廣義表中分離出來(lái)： (1)L1(apple,pear,banana,orange) (2)L2((apple,pear),(banana,orange)) (3)L3(((apple),(pear),(banana),(orange))) (4)L4((((apple))),((pear)),(banana),orange) (5)L5((((apple),pear),banana),orange) (6)L6(apple,(pear,(banana),orange))【解答】 (1)Head(Tail(Tail(L1))) (2)Head(Head(Tail(L2))) (3)Head(Head(Tail(Tail(Head(L3))))) (4)Head(Head(Tail(Tail(L4)))) (5)Head(Tail(Head(L5))) (6)Head(Head(Tail(Head(Tail(L6)))))5-8廣義表具有可共享性，因此在遍歷一個(gè)廣義表時(shí)必需為每一個(gè)結(jié)點(diǎn)增加一個(gè)標(biāo)志域mark，以記錄該結(jié)點(diǎn)是否訪問(wèn)過(guò)。一旦某一個(gè)共享的子表結(jié)點(diǎn)被作了訪問(wèn)標(biāo)志，以后就不再訪問(wèn)它。 (1)試定義該廣義表的類結(jié)構(gòu)； (2)采用遞歸的算法對(duì)一個(gè)非遞歸的廣義表進(jìn)行遍歷。 (3)試使用一個(gè)棧，實(shí)現(xiàn)一個(gè)非遞歸算法，對(duì)一個(gè)非遞歸廣義表進(jìn)行遍歷?！窘獯稹?1)定義廣義表的類結(jié)構(gòu) 為了簡(jiǎn)化廣義表的操作，在廣義表中只包含字符型原子結(jié)點(diǎn)，并用除大寫(xiě)字母外的字符表示數(shù)據(jù)，表頭結(jié)點(diǎn)中存放用大寫(xiě)字母表示的表名。這樣，廣義表中結(jié)點(diǎn)類型三種：表頭結(jié)點(diǎn)、原子結(jié)點(diǎn)和子表結(jié)點(diǎn)。 classGenList; //GenList類的前視聲明 classGenListNode{ //廣義表結(jié)點(diǎn)類定義 friendclassGenlist; private: intmark,utype; //utype＝0/1/2,mark是訪問(wèn)標(biāo)記,未訪問(wèn)為0GenListNode*tlink; //指向同一層下一結(jié)點(diǎn)的指針 union{ //聯(lián)合 charlistname; //utype=0,表頭結(jié)點(diǎn)情形：存放表名charatom; //utype=1,存放原子結(jié)點(diǎn)的數(shù)據(jù)GenListNode*hlink; //utype=2,存放指向子表的指針}value; public:GenListNode(inttp,charinfo):mark(0),utype(tp),tlink(NULL) //表頭或原子結(jié)點(diǎn)構(gòu)造函數(shù){if(utype==0)value.listname=info;elsevalue.atom=info;} GenListNode(GenListNode*hp) //子表構(gòu)造函數(shù) :mark(0),utype(2),value.hlink(hp){} charInfo(GenListNode*elem) //返回表元素elem的值{return(utype==0)?elem->value.listname:elem->value.atom;} }; classGenList{ //廣義表類定義 private:GenListNode*first; //廣義表頭指針voidtraverse(GenListNode*ls); //廣義表遍歷voidRemove(GenListNode*ls); //將以ls為表頭結(jié)點(diǎn)的廣義表結(jié)構(gòu)釋放 public:Genlist(char&value); //構(gòu)造函數(shù),value是指定的停止建表標(biāo)志數(shù)據(jù)~GenList(); //析構(gòu)函數(shù)voidtraverse(); //遍歷廣義表 }(2)廣義表遍歷的遞歸算法voidGenList::traverse(){ //共有函數(shù)

traverse(first);}#include<iostream.h>voidGenList::traverse(GenListNode*ls){ //私有函數(shù),廣義表的遍歷算法 if(ls!=NULL){ls->mark=1; if(ls->utype==0)cout<<ls->value.listname<<‘(’; //表頭結(jié)點(diǎn)elseif(ls->utype==1){ //原子結(jié)點(diǎn)cout<<ls->value.atom; if(ls->tlink!=NULL)cout<<‘,’;}elseif(ls->utype==2){ //子表結(jié)點(diǎn)if(ls->value.hlink->mark==0)traverse(ls->value.hlink); //向表頭搜索elsecout<<ls->value.hlink->value.listname;if(ls->tlink!=NULL)cout<<‘,’; }traverse(ls->tlink); //向表尾搜索 }∧elsecout<<‘)’;∧}0000A02020202∧01∧01a00C∧∧∧01e∧01e0200D020101y01x00E對(duì)上圖所示的廣義表進(jìn)行遍歷，得到的遍歷結(jié)果為A(C(E(x,y),a),D(E,e))。利用?？蓪?shí)現(xiàn)上述算法的非遞歸解法。棧中存放回退時(shí)下一將訪問(wèn)的結(jié)點(diǎn)地址。#include<iostream.h>#include“stack.h”voidGenList::traverse(GenListNode*ls){Stack<GenListNode<Type>*>st;while(ls!=NULL){ls->mark=1;if(ls->utype==2){ //子表結(jié)點(diǎn)if(ls->value.hlink->mark==0) //該子表未訪問(wèn)過(guò){st.Push(ls->tlink); ls=ls->value.hlink;} //暫存下一結(jié)點(diǎn)地址,訪問(wèn)子表else{cout<<ls->value.hlink->value.listname; //該子表已訪問(wèn)過(guò),僅輸出表名if(ls->tlink!=NULL){cout<<‘,’;ls=ls->tlink;}} }else{if(ls->utype==0)cout<<ls->value.listname<<‘(’; //表頭結(jié)點(diǎn)elseif(ls->utype==1){ //原子結(jié)點(diǎn)cout<<ls->value.atom;if(ls->tlink!=NULL)cout<<‘,’;}if(ls->tlink==NULL){ //子表訪問(wèn)完,子表結(jié)束處理cout>>‘)’;if(st.IsEmpty()==0){ //棧不空l(shuí)s=st.GetTop();st.Pop(); //退棧if(ls!=NULL)cout<<‘,’;elsecout<<‘)’;}}elsels=ls->tlink; //向表尾搜索 }}}(4)廣義表建立操作的實(shí)現(xiàn) #include<iostream.h> #include<ctype.h>#include“stack.h”constintmaxSubListNum=20; //最大子表個(gè)數(shù)GenList::GenList(char&value){Stack<GenListNode*>st(maxSubListNum); //用于建表時(shí)記憶回退地址SeqList<char>Name(maxSubListNum); //記憶建立過(guò)的表名SeqList<GenListNode*>Pointr(maxSubListNum); //記憶對(duì)應(yīng)表頭指針GenListNode*p,q,r; Typech;intm=0,ad,br; //m為已建表計(jì)數(shù),br用于對(duì)消括號(hào)cout<<“廣義表停止輸入標(biāo)志數(shù)據(jù)valu