1、5-A中的最大整數(shù)。n 個整數(shù)的和。n#include class RecurveArray publicRecurveArray/MaxSize=10 ) ArraySize(MaxSize),5-A中的最大整數(shù)。n 個整數(shù)的和。n#include class RecurveArray publicRecurveArray/MaxSize=10 ) ArraySize(MaxSize),Elements(RecurveArray() delete Elements;MaxSize)void/MaxKeySumn n /和 n /voidRecurveArray: InputArray( /c

2、outInputthenumberofArray: fori =0;iRecurveArray:MaxKeyn )/if(n=1)returnElements0; temp = MaxKey ( n -1 );if(Elementsn-1 temp)returnElementsn-elsereturnRecurveArray: Sumn ) /if(n=1) returnelsereturnElementsn-1+Sum(n-floatRecurveArray:Averagen ) /if(n =1) return(float)elsereturn(float)Elementsn-1 +(n-

3、1)*elsereturn(float)Elementsn-1 +(n-1)*Average(n -1)/mainsize=-argc, char*argv)coutNo.oftheElements:; while ( size size; RecurveArray ra ( size ); coutnThemaxis: ra.MaxKey(ra.MaxSize)endl; cout nThe sum is: ra.Sum ( ra.MaxSize ) endl; cout nthe avr is: ra.Average ( ra.MaxSize ) 0, n =/ m0, n (2) 為了將

4、遞歸算法改成非遞歸算法，首先改寫原來的遞歸算法，將遞歸語句從unsignedakm( unsignedm,unsignedn) unsignedif(m=0 ) returnif(n=0)returnakm(m-1,1); v = akm ( m, n-1 ) );returnakm( m-1,v/m=/ m0, n / m0, n ：akm=v =akm=v=akm=v=v=v=vm vm vm akm(m-akm(m-v=n+1= v = n+1 = 3akm(m-vm vm vm akm(m-v=n+1 =akm(m-1,v) akm(m-1,v) akm(m-?？? vv=n+1 =v

5、=n+1 =v=n+1 =#include #include “stack.h” #definemaxSize3500;unsignedakm(unsignedm,unsignedn) struct node unsigned vm, vn; stackst(maxSize); akm=v =akm=v=akm=v=v=v=vm vm vm akm(m-akm(m-v=n+1= v = n+1 = 3akm(m-vm vm vm akm(m-v=n+1 =akm(m-1,v) akm(m-1,v) akm(m-?？? vv=n+1 =v=n+1 =v=n+1 =#include #includ

6、e “stack.h” #definemaxSize3500;unsignedakm(unsignedm,unsignedn) struct node unsigned vm, vn; stackst(maxSize); nodew; w.vm= m; w.vn = n; st.Push (w); do while(st.GetTop().vm0) while(st.GetTop().vn0unsigned/akm(m-1akm(mn-1/akm(mn-1), akm(mw.vn-; st.Push( w);w=st.GetTop(); st.Pop(w.vm-; w.vn=1; st.Pus

7、h(w/akm(m-103021201111210112100122121212121akm(0,2) =v= akm(1,akm(0,1) =akm(0,3) =v= akm(1,akm(0,2) =v=akm(1,akm(0,1) =akm(0,4) =v= akm(1,akm(1,v=akm(2,akm(1,akm(2,w=st.GetTop(); st.Pop(); v=w.vn+; if ( st.IsEmpty( ) = 0 )/akm0akm1, */vakm1, */如果棧不空, 改棧頂為( m-1vw=w=st.GetTop(); st.Pop(); v=w.vn+; if

8、( st.IsEmpty( ) = 0 )/akm0akm1, */vakm1, */如果棧不空, 改棧頂為( m-1vw=st.GetTop(); st.Pop(); w.vm-; w.vn=v; st.Push(w);while(st.IsEmpty()=0 return5-3 sn 件物品，重量分別為 w1w2, wnn件物品中選擇若干件放入此背包中，使得放入的重量之則稱此背包問題無解(或稱其解為假)（s s s 0且ns 0且n物品件數(shù)不能為負KNAP(s,n) KNAP(sn1)False,Truen )if(s=0 ) returnif(s0 &n1)returnFalse; if

9、 ( Knap ( s Wn, n-1 ) = True )coutWn,; returnTrue;returnKnap(s,n-1w0,1,2,4,8,1632，s51,n6 Knap(51,returnTrue, Knap(51-32,returnTrue, Knap(19-16,returnTrue, Knap(3-8,returnKnap(3,returnTrue, s= -5 returnKnap(3-4,returnKnap(3,returnTrue, s= -1 returnKnap(3-2,returnTrue, Knap(1-1,returnTrue, s=return j+

10、1 列。)0# 1# 2# 01233# 4# 01235# 6# 0# 1# 2# 3# 4# 5# 6# 8 i 1 n 試探j j+1 列。)0# 1# 2# 01233# 4# 01235# 6# 0# 1# 2# 3# 4# 5# 6# 8 i 1 n 試探j1,nj j j i+1行皇后。解題時設置 4 個數(shù)組：coln ：coli i md2n-1 ：mdk k sd2n-1 ：sdk k qn i ij計算主對角線ki+j。nvoidi ) k forj =0; j n; j+)if(colj =0 &mdn+i-j-1=0 &sdi+j =0) colj=mdn+i-j-1=

11、sdi+j=1; qi=j; if ( i = n ) for(j=0;jn;j+)coutqj,; cout endl;else Queen (i+1colj =mdn+i-j-1 =sdi+j =0; qi =/第 i j /在第 i j /i+1 /撤消第 i j 5-5 f為單鏈表的表頭指針#includeiostreamclassclass ListNode friendclassList; ListNode *link; ListNode( classList/定義在頭文件RecurveList5-5 f為單鏈表的表頭指針#includeiostreamclassclass Lis

12、tNode friendclassList; ListNode *link; ListNode( classList/定義在頭文件RecurveListh/itemdata(itemlink(NULL) /ListNode , Max(ListNode *f); Num( ListNode *ffloatAvg(ListNode&n List() (NULL),current(NULL) List () /創(chuàng)建鏈表結(jié)點, /建立鏈表, retvalue/ListNode*NewNode( item voidNewList(voidPr List ( retvalue GetMax ( ) re

13、turn Max ( GetNum() returnNumfloatGetAvg()returnAvg); ); ); ListNode*List :NewNode( item) /ListNode*newnode=new ListNodereturnvoidList:NewList( retvalue ) /建立鏈表, retvalue=value; ListNode cout value;while(value!=retvalue ) q=NewNode(value/value/空表時, /非空表時, cout value;while(value!=retvalue ) q=NewNode

14、(value/value/空表時, /非空表時, /if =NULL=current =current=q; else current-link=cincurrent-link=/voidList :Pr List ( ) coutnThe Listis : /ListNode*p;while(p != NULL) cout data coutlink; List:Max(ListNode *f )if(f-link= NULL)return f -temp =Max ( f-linkif(f-datatemp)returnf-data; else return temp;/: /如果當前結(jié)點

15、的值還要大, /List:Num(ListNode*f) if(f=NULL) returnreturn1+Num( f-link/: /空表, /否則, ist:Avg(ListNode*fif( f-link=NULL&n ) /: /鏈表中只有一個結(jié)點, n =1; return( float)(f-data); else floatSum=Avg( f-link,n )*n; return( f -data+Sum) /n; #include/mainargc,char*argv)Listcoutcin finished; test.NewList(finished); test.Pr

16、 List ( );cout nThe Max is : test.GetMax ( ); coutnTheNumis:test.GetNum();coutnTheAveis:test.GetAve() finished; test.NewList(finished); test.Pr List ( );cout nThe Max is : test.GetMax ( ); coutnTheNumis:test.GetNum();coutnTheAveis:test.GetAve()value.listname:elem-value.atom;classGenList GenListNode

17、/;/lsvoidtraverse(GenListNode *ls voidRemove( GenListNode*lsGenlist(char&valueGenList ( ); voidtraverse();(2) voidGenList :traverse() /構(gòu)造函數(shù)value/traverse#includeiostreamvoidGenList:traverse(GenListNode*lsGenlist(char&valueGenList ( ); voidtraverse();(2) voidGenList :traverse() /構(gòu)造函數(shù)value/traverse#in

18、cludemark=/私有函數(shù), if(ls-utype=0)coutvalue.listnameutype = 1 ) couttlink!=NULL) coututype=2 ) if(ls-value.hlink-mark=0)traverse(ls-value.hlink); else cout value hlink-value.listname;if(ls-tlink!=NULL) couttlink/elsecout對上圖所示的廣義表進行遍歷，得到的遍歷結(jié)果為A(C(E(x,yaD(E,e)(3) #includeiostream#include“stackvoidGenList

19、:traverse(GenListNode *ls) 01y01x00E01e0200D01a0200C020200AStackGenListNode*st; while ( ls != NULL ) ls-mark=if(ls-utype=2 ) if(StackGenListNode*st; while ( ls != NULL ) ls-mark=if(ls-utype=2 ) if(ls-valuehlink-mark=0 st.Push(ls-tlink); ls=ls-valuehlink; else coutvalue.hlink-if(ls-tlink!=NULL)couttl

20、ink;elseif(ls-utype=0)coutvalue.listnameutype = 1 ) couttlink!=NULL) couttlink=NULL) cout );if(st.IsEmpty()=0) ls=st.GetTop(); st.Pop(if(ls!=NULL)cout,; else cout );elsels= ls-/過/暫存下一結(jié)點地址/該子表過, 僅輸出表/子完, 子表結(jié)束處/(4) #include #include #include “stack h”maxSubListNum=/GenList:GenList(char&value) Stackst(maxSubListNum); SeqList Name (maxSubListNum);SeqListPo r /GenListNode*p,q,m=0, ad,/m為已建表計數(shù), br coutcout開始輸入廣義表數(shù)據(jù), A(C(E(xyaD(E(xyecin=q = new GenListNode(0,ch /if(chcout開始輸入廣義表數(shù)據(jù), A(C(E(xyaD(E(xyecin=q = new GenListNode(0,ch /if(ch!=value)Name.Insert(ch,m); else retur