【習題課】第1-3章課件_第1頁
【習題課】第1-3章課件_第2頁
【習題課】第1-3章課件_第3頁
【習題課】第1-3章課件_第4頁
【習題課】第1-3章課件_第5頁
已閱讀5頁,還剩119頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

第1-3章習題.第1-3章習題.1作業(yè)1-5

試用ADL語言編寫一個算法,判斷任一整數(shù)n是否為素數(shù)。.作業(yè)1-5試用ADL語言編寫一個算法,判斷任一整數(shù)n2考察知識點判斷素數(shù)素數(shù)——大于1的自然數(shù)中,除了1和此整數(shù)自身外,不能被其他自然數(shù)整除的數(shù)。判斷:對于指定的n,如果[2,n-1]內的整數(shù)都不能整除n,則n為素數(shù)。ADL語言寫算法算法證明很難,可以使用邊界條件和特殊數(shù)據(jù),人工模擬算法執(zhí)行過程。.考察知識點判斷素數(shù).3完成情況思想——基本正確,對素數(shù)定義的理解:1?算法——特殊情況處理:n1?算法輸出;ADL語言的使用:運算符號:MOD(模),DIV(除數(shù)),/(除);

,(取整);%?sqrt?fabs()?

輸入輸出參數(shù):設置返回值;中間用“.”分隔;條件語句:ifthenelse;

fori=1tonstep1(i=i+1?)

賦值語句:.完成情況思想——基本正確,對素數(shù)定義的理解:1?.4參考答案算法S(n.flag)/*判斷整數(shù)n是否為素數(shù),將結果保存到變量flag*/S1[n≤1?]IF(n≤1)THEN(flag←false.RETURN.)S2[初始化]i←2.flag←true.S3[求余判斷]WHILE(i≤n-1)DO(IF(nMODi)=0THEN(flag←false.RETURN.)i←i+1.)▌.參考答案算法S(n.flag).5正確性驗證:假定n=7,模擬執(zhí)行過程,對i=2,3,4,5,6時,分別判斷(7modi)的取值是否為0。改進:n-1?——n/2、n1/2n=ab,a≥2,b≤n/2,…a,…b,…n/2a≤n1/2,b≥n1/2,…a,…n1/2,…b…

.正確性驗證:.6參考答案2算法S(n.flag)/*判斷整數(shù)n是否為素數(shù),將結果保存到變量flag*/S1[n≤1?]IF(n≤1)THEN(flag←false.RETURN.)S2[初始化]i←2.flag←true.S3[求余判斷]WHILE(i≤

n/2)DO(IF(nMODi)=0THEN(flag←false.RETURN.)i←i+1.)▌.參考答案2算法S(n.flag).7作業(yè)1-8若A(n)=amnm+…+a1n+a0是關于n的m次多項式,證明A(n)=O(nm)。設f(n)和g(n)是正整數(shù)集到正實數(shù)集的函數(shù),稱f(n)是O(g(n))當且僅當存在正常數(shù)C和n0,使得對任意的nn0,有f(n)Cg(n)。完成情況:令n0=1,C=am+…+a1+a0,

amnm+…+a1n+a0Cnm

注意:當ai0時,ainiainm不一定成立。.作業(yè)1-8若A(n)=amnm+…+a1n+a0是關于n的m8證明:對于所有的n≥1,有:

A(n)=i=0,…,maini≤i=0,…,m|ai|ni≤

nmi=0,…,m|ai|ni-m

nmi=0,…,m|ai|

令C=i=0,…,m|ai|,有A(n)≤

Cnm

所以,

A(n)=O(nm)。參考答案.證明:對于所有的n≥1,有:參考答案.9作業(yè)1-11

證明對正整數(shù)n≥3,算法BS的元素比較次數(shù)T(n)≤5n/3-2。已知:0n=1T(n)=1n=2T(n/2)+T(n/2)+2n>2.作業(yè)1-11證明對正整數(shù)n≥3,算法BS的元素比較次數(shù)T(10考察知識點:數(shù)學歸納法基礎歸納:n=c(初值)時,命題是正確的;歸納步驟:如果n=k-1時,命題成立,則n=k時,命題也成立。完成情況:利用結論T(n)=3n/2-2,需要注意前提條件——當n是2的冪時;由n=k反推n=k-1時的情況。.考察知識點:數(shù)學歸納法.110n=1

T(n)=1n=2

T(n/2)+T(n/2)+2n>2n=3時,T(3)=T(1)+T(2)+2=3,53/3-2=3,命題成立。假設n<=k時命題成立,需證明n=k+1時成立。

當k≥3時,有(k+1)>(k+1)/2≥(k+1)/2

,即k≥(k+1)/2≥(k+1)/2

所以:T((k+1)/2)≤5((k+1)/2)/3-2,

(1)

T((k+1)/2)≤5((k+1)/2)/3-2

(2)T(k+1)=T((k+1)/2)+T((k+1)/2)+2≤[5((k+1)/2)/3-2]+[5((k+1)/2)/3-2]+2=5((k+1)/2+(k+1)/2)/3-2//k+1=(k+1)/2+(k+1)/2

=5(k+1)/3-2綜上,命題得證。.012作業(yè)1-12給出算法BS的非遞歸算法,并說明算法最多需要多大的輔助空間。.作業(yè)1-12給出算法BS的非遞歸算法,并說明算法最多需要多大13算法SM(A,n.max,min)

SM1[初始化]max←min←A[1].

SM2[比較]

FORI=2TOnDO

//求最大和最小元素

(IFA[I]>maxTHENmax←A[I].IFA[I]<minTHENmin←A[I]).

▌.算法SM(A,n.max,min).14BS算法算法BS(A,i,j.fmax,fmin)//在數(shù)組A的第i個元素到第j個元素之間尋找最大和最//小元素,已知ij。BS1[遞歸出口]IFi=jTHEN(fmax←fmin←A[i].RETURN.)IFi=j1THEN

(IFA[i]<A[j]THEN(fmax←A[j].fmin←A[i]). ELSE(fmax←A[i].fmin←A[j]).RETURN)..BS算法算法BS(A,i,j.fmax,fmin)15BS2[取中值] mid←(i+j)/2BS3[遞歸調用]BS(A,i,mid.gmax,gmin)

BS(A,mid+1,j.hmax,hmin).BS4[合并] fmax←max{gmax,hmax}. fmin←min{gmin,hmin}.■

.BS2[取中值].16完成情況做的很少SM方法;(沒有體現(xiàn)分治思想)依次對比鄰近的兩個元素,找到較大較小者,不斷更新全局最大最小值;依次對比,用數(shù)組存放每對的最大最小值;兩個棧分別存放當前起始和終止元素下標;一個棧存儲中間值,另一個存放最大最小值。(沒法確定起始和終止元素的下標).完成情況做的很少.17輔助空間:因為采用某種特殊結構,而增加占用的空間;占用空間:算法運行所需要的空間;方法3:數(shù)組;方法4:棧.輔助空間:因為采用某種特殊結構,而增加占用的空間;.18方法4基本思想:創(chuàng)建兩個棧,一個存放起始元素的下標,一個存放終止元素的下標。每次從棧中彈出一對下標,若兩者相等或相差為1,則找到最大最小值,否則找到中間下標,形成兩對新的下標,壓入棧內。.方法4基本思想:.19示例數(shù)組A=[3,9,21,15,8,19]16初始:壓入起始和結束下標1和6;循環(huán):彈出元素1和6;兩者不相等、相差不為1;取中值(1+6)/2=3;形成兩對新的下標,(1,3)和(4,6);壓入棧;彈出4和6,兩者不相等、相差不為1;取中值(4+6)/2=5;形成兩對新的下標,(4,5)和(6,6);壓入棧內;1346134566.示例數(shù)組A=[3,9,21,15,8,19]16初始:壓入起20A=[3,9,21,15,8,19]134566彈出(6,6),相等,元素值為19,則fmaxmax{fmax,19}=19,fminmin{fmin,19}=19;彈出(4,5),相差為1,元素值為15和8,則fmaxmax{19,15,8}=19,fminmin{19,15,8}=8;13.A=[3,9,21,15,8,19]134566彈出(6,621參考答案算法f(A,i,j.fmax,fmin)f1.[初始化]fmaxfminA[i].Lstack<int>left;Lstack<int>right;//存儲起始和終止下標left.push(i).right.push(j).f2.[求最大、最小值]While(!left.IsEmpty())DO(lleft.pop().rright.pop().

.參考答案算法f(A,i,j.fmax,fmin).22IFl=rTHEN//相等(fmaxmax{fmax,A[l]}.fminmin{fmin,A[l]}.)ELSE(IFr-l=1//相差為1THEN(fmaxmax{fmax,A[l],A[r]}.fminmin{fmin,A[l],A[r]}.)ELSE(mid=(i+j)/2.left.push(l).left.push(mid+1).right.push(mid).Right.push(r).))).IFl=rTHEN//23輔助空間:棧nn/2n/2n/4n/4…1log2n.輔助空間:棧nn/2n/2n/4n/4…1log2n.24作業(yè)2-1編寫算法Reverse(A[],n),將順序存儲的線性表A=(a1,a2,…,an)轉換為A=(an,…,a2,a1),要求轉換過程中使用盡可能少的輔助空間。關鍵點:限制輔助空間的使用如果沒有這個限制,則可以有多種方法:輔助數(shù)組;雙下標同時向中間移動.作業(yè)2-1編寫算法Reverse(A[],n),將順25分析只需從線性表的第一個數(shù)據(jù)元素開始,將第i個數(shù)據(jù)元素與第n-i+1個數(shù)據(jù)元素相交換即可。i的變化范圍是1到n/2。a1a2…an-1ananan-1…a2a11+n2+(n-1)…(n-1)+2n+1.分析只需從線性表的第一個數(shù)據(jù)元素開始,將第i個數(shù)據(jù)元素與第n26參考答案算法Reverse(A,n.A)Reverse1.[元素互換]FORi=1TOn/2DOA[i]←→A[n-i+1].▌.參考答案算法Reverse(A,n.A).27作業(yè)2-8在單鏈表類SLIST中添加一個成員函數(shù),將單鏈表中元素的次序完全顛倒。.作業(yè)2-8在單鏈表類SLIST中添加一個成員函數(shù),將單鏈表中28利用堆棧;從表頭刪除,插入表尾;(不推薦)換數(shù)據(jù)域的取值,p1和p2向中間移動,更換數(shù)據(jù)域的取值。…h(huán)eadp1p2.利用堆棧;…h(huán)eadp1p2.29方法4思想:從左向右,依次更換鄰近結點的指針方向。初始設置,第一個元素需要被放到表尾,指向空指針,p1=null,p2=next(head)//第一個元素headp22p3345p1nullp11p26P3next(p2)next(P2)P1. //反轉P1P2.P2P3..方法4思想:從左向右,依次更換鄰近結點的指針方向。headp30參考答案算法Reverse(head.head)/*將指針head所指向的鏈表倒置*/RV1[空鏈表和1個節(jié)點鏈表]IF(next(head)=NULL)RETURN.RV2[指針初始化] //P1,P2分別指向兩個連續(xù)的節(jié)點

P1NULL. P2next(head)..參考答案算法Reverse(head.head).31RV3[反轉鏈表] WHILE(P2≠NULL)DO (P3next(p2) next(P2)P1. //反轉節(jié)點指針

P1P2.P2P3.//移動3個指針 )RV4[head指向反轉鏈表]

next(head)P1.

▌p1p2.RV3[反轉鏈表]p1p2.32作業(yè)2-11已知線性表中的元素以data值遞增有序排列,并以單鏈表做存儲結構。試寫一高效的算法,刪除表中所有值大于mink且小于maxk的元素,同時釋放被刪結點空間,并分析算法的時間復雜度。鏈表是有序的:找到區(qū)間特殊情況的處理:表為空,元素都大于maxk(第一個元素大于maxk);元素都小于mink(最后一個元素小于mink)。.作業(yè)2-11已知線性表中的元素以data值遞增有序排列,并以33主要思想:找到大于mink的第一個元素,刪除操作,直至元素大于maxk。時間復雜度:比較為基本運算最好:空,元素都大于maxk(找不到)//O(1)最壞:元素都小于mink(找不到),

元素都小于maxk,O(n);.主要思想:.34算法LD(L,mink,maxk)LD1.[特殊情況]IF

minkmaxkTHEN(RETURN.)LD2.[初始化]p←head.prev←p.p←next(p)LD3.[找]WHILE(pNULLANDdata(p)<maxk)DO(IF(data(p)mink)THEN(prev←p.p←next(p))//向后移動ELSE(next(prev)←next(p).q←p.p←next(p).AVAILq.))//刪除qRETURN.prevheadpPprevp.算法LD(L,mink,maxk)LD1.[特殊情況35作業(yè)2-17對于順序堆棧和鏈式堆棧s,分別編寫函數(shù)SelectItem(Stack&s,intn),要求在堆棧中查找元素n在棧中第一次出現(xiàn)的位置,并將該位置元素移至棧頂,同時其他元素次序不變。(注意:用int匹配堆棧的模板).作業(yè)2-17對于順序堆棧和鏈式堆棧s,分別編寫函數(shù)Selec36基本思想:取棧頂元素,若不匹配,則進行彈棧操作;找到(或無法找到)后恢復原來的元素次序。關鍵點:記錄彈出的順序,后彈出的元素能夠先被壓回原來的棧,因此需要使用一個輔助堆棧。.基本思想:.37示例105112shelpStack5173n=515112105173751511210377351.示例105112shelpStack5173n=51511238參考答案intSelectItem(Stack<int>&s,intn){AStack<int>temp(100);//順序堆棧,輔助棧

//LStack<int>temp;//鏈式堆棧

boolflag=false;//是否存在元素nintloc=0;//記錄n所在的位置

while(!s.isEmpty()&&s.Peek()!=n

){temp.Push(s.Pop());loc++;}棧非空且當前元素不等于n.參考答案intSelectItem(Stack<int>39if(!s.isEmpty()){s.Pop();flag=true;}//彈出nwhile(!temp.isEmpty())//將輔助棧中元素壓入原棧

{s.Push(temp.Pop());}if(flag)thens.Push(n);

elseloc=-1;returnloc;}因為找到元素而跳出循環(huán).if(!s.isEmpty())因為找到元素40作業(yè)2-25編寫并實現(xiàn)雙端隊列類,雙端隊列是可進行如下操作的線性表。(1)push(item)--item插入到隊列的前端;(2)pop(item)--刪除前端元素且賦給item;(3)inject(item)--item插入尾端;(4)eject(item)--刪除尾端元素且賦給item.作業(yè)2-25編寫并實現(xiàn)雙端隊列類,雙端隊列是可進行如下操作的41結點結構SLNode:數(shù)據(jù)域和指針域;類成員:隊首和隊尾的SLNode類型指針、指示元素個數(shù)的整型變量;Push(item插入隊列前端)

若空,則加入一個以item為數(shù)據(jù)域的結點,元素個數(shù)為1;否則,temp記錄原隊首指針front;

創(chuàng)建以item為數(shù)據(jù)域的新結點,作為新的隊首,賦值給front;front的指針域指向temp,元素個數(shù)加1。.結點結構SLNode:數(shù)據(jù)域和指針域;.42Pop(刪除前端元素,并賦值item)若空,則錯誤;否則,temp記錄原隊首指針front;

隊首后移,即frontnext(front);

返回temp的數(shù)據(jù)域;

刪除temp結點,元素個數(shù)減1;

若大小為零,則隊尾指針rear賦值為NULL。.Pop(刪除前端元素,并賦值item).43Inject(item插入隊尾)若空,則加入一個以item為數(shù)據(jù)域的結點,元素個數(shù)為1;否則,創(chuàng)建以item為數(shù)據(jù)域的新結點temp,作為新的隊尾,即next(rear)temp;隊尾指針后移,即rearnext(rear);元素個數(shù)加1。.Inject(item插入隊尾).44Eject(刪除隊尾元素并賦值給item)若空,則出錯;否則,

找到隊尾指針的前驅指針tempfront.IF(temprear)THEN(WHILE(next(temp)rear)DO(tempnext(temp))隊尾指針更新,即reartemp,

要刪除結點是next(temp),返回數(shù)據(jù)域,刪除結點,元素個數(shù)減1。

若大小為零,front和rear賦值為NULL。.Eject(刪除隊尾元素并賦值給item).45作業(yè)3-10設稀疏矩陣Mmn中有t個非零元素,用三元組表的方式存儲.請設計一個算法,計算矩陣M的轉置矩陣N,且算法的時間復雜性為O(n+t).注意,書中給出的算法的復雜性為O(nt)。.作業(yè)3-10設稀疏矩陣Mmn中有t個非零元素,用三元組表的46M=500001002000000-300-605N=50100-3000000200-6000050050a[0]1010a[1]1220a[2]30-30a[3]32-60a[4]335a[5]0050b[0]0110b[1]03-30b[2]2120b[3]23-60b[4]335b[5]算法的關鍵是求出a中元素在b中的位置.M=50000N=501047Bindex=0;FORj=0TOn-1DO

FORk=0TOt-1DOIFcol(A[k])=jThen (row(B[Bindex])=j. col(B[Bindex])=row(A[k]). value(B[Bindex])=Value(A[k]).

Bindex++)a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30j=0,k=0,a[0],列坐標=0;存儲j=0;k=1;a[1],列坐標=0;存儲j=0;k=2;a[2],列坐標=2;j=0;k=3;a[3],列坐標=0;存儲j=0;k=4;j=0;k=5;j=1;k=0005030-301010.Bindex=0;a[0]0050212001103352348a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30005030-301010j=1,k=0,a[0],列坐標=0j;j=1,k=1;列坐標1j=1,k=2;j=1,k=3;j=1,k=4;j=1,k=5;j=2,k=0;j=2,k=1;j=2,k=2,列坐標=2=jFORj=0TOn-1DO

FORk=0TOt-1DOIFcol(A[k])=jThen2201.a[0]00502120011033523-6003-30049005030-30101033532-601220a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30b[2]a[x]b[y]?y=列坐標小于col(a[x])的元素個數(shù)+

列坐標等于col(a[x])且在a[x]之前的元素個數(shù).005030-30101033532-601220a[0]050a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30基本思想:

數(shù)組num存儲a中每列非零元素個數(shù);數(shù)組pos存儲a中每列第一個非零元素在b的三元組表中的位置;

302101230123num0335pos.a[0]00502120011033523-6003-30基51算法:TRANSPOSE(A.B)TP1[初始化]

n←Rows(B)←Cols(A).//B的行數(shù)等于A的列數(shù),B的列數(shù)等于A的行數(shù)

Cols(B)←Rows(A).

t←Count(B)←Count(A).//B中非0元素的個數(shù)等于A中非0元素的個數(shù)TP2[定義數(shù)組num]

FORi←0TOn-1DO

num[i]←0.

FORi←0TOt-1DO(

j←col(A

[i]). num[j]←num[j]+1.)//A中每列非零元素個數(shù)

pos[0]

←0//定義數(shù)組pos

FORi←1TOn-1DO(pos[i]←pos[i-1]+num[i-1]).算法:TRANSPOSE(A.B).52a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-3003102231num00132335pos005030-30101033532-601220b[0]b[1]b[2]b[3]b[4]b[5].a[0]00502120011033523-6003-30053TP3[處理三元組表]FORi←0TOt-1DO(p←col(A[i]).//列坐標k←pos[p].//該列坐標的元素在b中的位置col(B[k])←row(A[i]).row(B[k])←col(A[i]).val(B[k])←val(A[i]).

pos[p]←pos[p]+1).a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-300335pos0050.TP3[處理三元組表]a[0]00502120011033554TP3[處理三元組表]FORi←0TOt-1DO(p←col(A[i]).k←pos[p].col(B[k])←row(A[i]).row(B[k])←col(A[i]).val(B[k])←val(A[i]).pos[p]←pos[p]+1).a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-301335pos00501010.TP3[處理三元組表]a[0]00502120011033555TP3[處理三元組表]FORi←0TOt-1DO(p←col(A[i]).k←pos[p].col(B[k])←row(A[i]).row(B[k])←col(A[i]).val(B[k])←val(A[i]).pos[p]←pos[p]+1).a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-302335pos005010101220.TP3[處理三元組表]a[0]00502120011033556TP3[處理三元組表]FORi←0TOt-1DO(p←col(A[i]).k←pos[p].col(B[k])←row(A[i]).row(B[k])←col(A[i]).val(B[k])←val(A[i]).pos[p]←pos[p]+1).a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-302345pos005030-3010101220.TP3[處理三元組表]a[0]00502120011033557TP3[處理三元組表]FORi←0TOt-1DO(p←col(A[i]).k←pos[p].col(B[k])←row(A[i]).row(B[k])←col(A[i]).val(B[k])←val(A[i]).pos[p]←pos[p]+1).a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-303345pos005030-30101032-601220.TP3[處理三元組表]a[0]00502120011033558TP3[處理三元組表]FORi←0TOt-1DO(p←col(A[i]).k←pos[p].col(B[k])←row(A[i]).row(B[k])←col(A[i]).val(B[k])←val(A[i]).pos[p]←pos[p]+1).a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-303355pos005030-30101033532-601220.TP3[處理三元組表]a[0]00502120011033559TP3[處理三元組表]FORi←0TOt-1DO(p←col(A[i]).k←pos[p].col(B[k])←row(A[i]).row(B[k])←col(A[i]).val(B[k])←val(A[i]).pos[p]←pos[p]+1).a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-303356pos005030-30101033532-601220.TP3[處理三元組表]a[0]00502120011033560f(j)abcabcacabca-1-1-10123-10123作業(yè)2-15.f(j)abcabca61abcaabbabcab…..abcaabb62第1-3章習題.第1-3章習題.63作業(yè)1-5

試用ADL語言編寫一個算法,判斷任一整數(shù)n是否為素數(shù)。.作業(yè)1-5試用ADL語言編寫一個算法,判斷任一整數(shù)n64考察知識點判斷素數(shù)素數(shù)——大于1的自然數(shù)中,除了1和此整數(shù)自身外,不能被其他自然數(shù)整除的數(shù)。判斷:對于指定的n,如果[2,n-1]內的整數(shù)都不能整除n,則n為素數(shù)。ADL語言寫算法算法證明很難,可以使用邊界條件和特殊數(shù)據(jù),人工模擬算法執(zhí)行過程。.考察知識點判斷素數(shù).65完成情況思想——基本正確,對素數(shù)定義的理解:1?算法——特殊情況處理:n1?算法輸出;ADL語言的使用:運算符號:MOD(模),DIV(除數(shù)),/(除);

,(取整);%?sqrt?fabs()?

輸入輸出參數(shù):設置返回值;中間用“.”分隔;條件語句:ifthenelse;

fori=1tonstep1(i=i+1?)

賦值語句:.完成情況思想——基本正確,對素數(shù)定義的理解:1?.66參考答案算法S(n.flag)/*判斷整數(shù)n是否為素數(shù),將結果保存到變量flag*/S1[n≤1?]IF(n≤1)THEN(flag←false.RETURN.)S2[初始化]i←2.flag←true.S3[求余判斷]WHILE(i≤n-1)DO(IF(nMODi)=0THEN(flag←false.RETURN.)i←i+1.)▌.參考答案算法S(n.flag).67正確性驗證:假定n=7,模擬執(zhí)行過程,對i=2,3,4,5,6時,分別判斷(7modi)的取值是否為0。改進:n-1?——n/2、n1/2n=ab,a≥2,b≤n/2,…a,…b,…n/2a≤n1/2,b≥n1/2,…a,…n1/2,…b…

.正確性驗證:.68參考答案2算法S(n.flag)/*判斷整數(shù)n是否為素數(shù),將結果保存到變量flag*/S1[n≤1?]IF(n≤1)THEN(flag←false.RETURN.)S2[初始化]i←2.flag←true.S3[求余判斷]WHILE(i≤

n/2)DO(IF(nMODi)=0THEN(flag←false.RETURN.)i←i+1.)▌.參考答案2算法S(n.flag).69作業(yè)1-8若A(n)=amnm+…+a1n+a0是關于n的m次多項式,證明A(n)=O(nm)。設f(n)和g(n)是正整數(shù)集到正實數(shù)集的函數(shù),稱f(n)是O(g(n))當且僅當存在正常數(shù)C和n0,使得對任意的nn0,有f(n)Cg(n)。完成情況:令n0=1,C=am+…+a1+a0,

amnm+…+a1n+a0Cnm

注意:當ai0時,ainiainm不一定成立。.作業(yè)1-8若A(n)=amnm+…+a1n+a0是關于n的m70證明:對于所有的n≥1,有:

A(n)=i=0,…,maini≤i=0,…,m|ai|ni≤

nmi=0,…,m|ai|ni-m

nmi=0,…,m|ai|

令C=i=0,…,m|ai|,有A(n)≤

Cnm

所以,

A(n)=O(nm)。參考答案.證明:對于所有的n≥1,有:參考答案.71作業(yè)1-11

證明對正整數(shù)n≥3,算法BS的元素比較次數(shù)T(n)≤5n/3-2。已知:0n=1T(n)=1n=2T(n/2)+T(n/2)+2n>2.作業(yè)1-11證明對正整數(shù)n≥3,算法BS的元素比較次數(shù)T(72考察知識點:數(shù)學歸納法基礎歸納:n=c(初值)時,命題是正確的;歸納步驟:如果n=k-1時,命題成立,則n=k時,命題也成立。完成情況:利用結論T(n)=3n/2-2,需要注意前提條件——當n是2的冪時;由n=k反推n=k-1時的情況。.考察知識點:數(shù)學歸納法.730n=1

T(n)=1n=2

T(n/2)+T(n/2)+2n>2n=3時,T(3)=T(1)+T(2)+2=3,53/3-2=3,命題成立。假設n<=k時命題成立,需證明n=k+1時成立。

當k≥3時,有(k+1)>(k+1)/2≥(k+1)/2

,即k≥(k+1)/2≥(k+1)/2

所以:T((k+1)/2)≤5((k+1)/2)/3-2,

(1)

T((k+1)/2)≤5((k+1)/2)/3-2

(2)T(k+1)=T((k+1)/2)+T((k+1)/2)+2≤[5((k+1)/2)/3-2]+[5((k+1)/2)/3-2]+2=5((k+1)/2+(k+1)/2)/3-2//k+1=(k+1)/2+(k+1)/2

=5(k+1)/3-2綜上,命題得證。.074作業(yè)1-12給出算法BS的非遞歸算法,并說明算法最多需要多大的輔助空間。.作業(yè)1-12給出算法BS的非遞歸算法,并說明算法最多需要多大75算法SM(A,n.max,min)

SM1[初始化]max←min←A[1].

SM2[比較]

FORI=2TOnDO

//求最大和最小元素

(IFA[I]>maxTHENmax←A[I].IFA[I]<minTHENmin←A[I]).

▌.算法SM(A,n.max,min).76BS算法算法BS(A,i,j.fmax,fmin)//在數(shù)組A的第i個元素到第j個元素之間尋找最大和最//小元素,已知ij。BS1[遞歸出口]IFi=jTHEN(fmax←fmin←A[i].RETURN.)IFi=j1THEN

(IFA[i]<A[j]THEN(fmax←A[j].fmin←A[i]). ELSE(fmax←A[i].fmin←A[j]).RETURN)..BS算法算法BS(A,i,j.fmax,fmin)77BS2[取中值] mid←(i+j)/2BS3[遞歸調用]BS(A,i,mid.gmax,gmin)

BS(A,mid+1,j.hmax,hmin).BS4[合并] fmax←max{gmax,hmax}. fmin←min{gmin,hmin}.■

.BS2[取中值].78完成情況做的很少SM方法;(沒有體現(xiàn)分治思想)依次對比鄰近的兩個元素,找到較大較小者,不斷更新全局最大最小值;依次對比,用數(shù)組存放每對的最大最小值;兩個棧分別存放當前起始和終止元素下標;一個棧存儲中間值,另一個存放最大最小值。(沒法確定起始和終止元素的下標).完成情況做的很少.79輔助空間:因為采用某種特殊結構,而增加占用的空間;占用空間:算法運行所需要的空間;方法3:數(shù)組;方法4:棧.輔助空間:因為采用某種特殊結構,而增加占用的空間;.80方法4基本思想:創(chuàng)建兩個棧,一個存放起始元素的下標,一個存放終止元素的下標。每次從棧中彈出一對下標,若兩者相等或相差為1,則找到最大最小值,否則找到中間下標,形成兩對新的下標,壓入棧內。.方法4基本思想:.81示例數(shù)組A=[3,9,21,15,8,19]16初始:壓入起始和結束下標1和6;循環(huán):彈出元素1和6;兩者不相等、相差不為1;取中值(1+6)/2=3;形成兩對新的下標,(1,3)和(4,6);壓入棧;彈出4和6,兩者不相等、相差不為1;取中值(4+6)/2=5;形成兩對新的下標,(4,5)和(6,6);壓入棧內;1346134566.示例數(shù)組A=[3,9,21,15,8,19]16初始:壓入起82A=[3,9,21,15,8,19]134566彈出(6,6),相等,元素值為19,則fmaxmax{fmax,19}=19,fminmin{fmin,19}=19;彈出(4,5),相差為1,元素值為15和8,則fmaxmax{19,15,8}=19,fminmin{19,15,8}=8;13.A=[3,9,21,15,8,19]134566彈出(6,683參考答案算法f(A,i,j.fmax,fmin)f1.[初始化]fmaxfminA[i].Lstack<int>left;Lstack<int>right;//存儲起始和終止下標left.push(i).right.push(j).f2.[求最大、最小值]While(!left.IsEmpty())DO(lleft.pop().rright.pop().

.參考答案算法f(A,i,j.fmax,fmin).84IFl=rTHEN//相等(fmaxmax{fmax,A[l]}.fminmin{fmin,A[l]}.)ELSE(IFr-l=1//相差為1THEN(fmaxmax{fmax,A[l],A[r]}.fminmin{fmin,A[l],A[r]}.)ELSE(mid=(i+j)/2.left.push(l).left.push(mid+1).right.push(mid).Right.push(r).))).IFl=rTHEN//85輔助空間:棧nn/2n/2n/4n/4…1log2n.輔助空間:棧nn/2n/2n/4n/4…1log2n.86作業(yè)2-1編寫算法Reverse(A[],n),將順序存儲的線性表A=(a1,a2,…,an)轉換為A=(an,…,a2,a1),要求轉換過程中使用盡可能少的輔助空間。關鍵點:限制輔助空間的使用如果沒有這個限制,則可以有多種方法:輔助數(shù)組;雙下標同時向中間移動.作業(yè)2-1編寫算法Reverse(A[],n),將順87分析只需從線性表的第一個數(shù)據(jù)元素開始,將第i個數(shù)據(jù)元素與第n-i+1個數(shù)據(jù)元素相交換即可。i的變化范圍是1到n/2。a1a2…an-1ananan-1…a2a11+n2+(n-1)…(n-1)+2n+1.分析只需從線性表的第一個數(shù)據(jù)元素開始,將第i個數(shù)據(jù)元素與第n88參考答案算法Reverse(A,n.A)Reverse1.[元素互換]FORi=1TOn/2DOA[i]←→A[n-i+1].▌.參考答案算法Reverse(A,n.A).89作業(yè)2-8在單鏈表類SLIST中添加一個成員函數(shù),將單鏈表中元素的次序完全顛倒。.作業(yè)2-8在單鏈表類SLIST中添加一個成員函數(shù),將單鏈表中90利用堆棧;從表頭刪除,插入表尾;(不推薦)換數(shù)據(jù)域的取值,p1和p2向中間移動,更換數(shù)據(jù)域的取值?!環(huán)eadp1p2.利用堆棧;…h(huán)eadp1p2.91方法4思想:從左向右,依次更換鄰近結點的指針方向。初始設置,第一個元素需要被放到表尾,指向空指針,p1=null,p2=next(head)//第一個元素headp22p3345p1nullp11p26P3next(p2)next(P2)P1. //反轉P1P2.P2P3..方法4思想:從左向右,依次更換鄰近結點的指針方向。headp92參考答案算法Reverse(head.head)/*將指針head所指向的鏈表倒置*/RV1[空鏈表和1個節(jié)點鏈表]IF(next(head)=NULL)RETURN.RV2[指針初始化] //P1,P2分別指向兩個連續(xù)的節(jié)點

P1NULL. P2next(head)..參考答案算法Reverse(head.head).93RV3[反轉鏈表] WHILE(P2≠NULL)DO (P3next(p2) next(P2)P1. //反轉節(jié)點指針

P1P2.P2P3.//移動3個指針 )RV4[head指向反轉鏈表]

next(head)P1.

▌p1p2.RV3[反轉鏈表]p1p2.94作業(yè)2-11已知線性表中的元素以data值遞增有序排列,并以單鏈表做存儲結構。試寫一高效的算法,刪除表中所有值大于mink且小于maxk的元素,同時釋放被刪結點空間,并分析算法的時間復雜度。鏈表是有序的:找到區(qū)間特殊情況的處理:表為空,元素都大于maxk(第一個元素大于maxk);元素都小于mink(最后一個元素小于mink)。.作業(yè)2-11已知線性表中的元素以data值遞增有序排列,并以95主要思想:找到大于mink的第一個元素,刪除操作,直至元素大于maxk。時間復雜度:比較為基本運算最好:空,元素都大于maxk(找不到)//O(1)最壞:元素都小于mink(找不到),

元素都小于maxk,O(n);.主要思想:.96算法LD(L,mink,maxk)LD1.[特殊情況]IF

minkmaxkTHEN(RETURN.)LD2.[初始化]p←head.prev←p.p←next(p)LD3.[找]WHILE(pNULLANDdata(p)<maxk)DO(IF(data(p)mink)THEN(prev←p.p←next(p))//向后移動ELSE(next(prev)←next(p).q←p.p←next(p).AVAILq.))//刪除qRETURN.prevheadpPprevp.算法LD(L,mink,maxk)LD1.[特殊情況97作業(yè)2-17對于順序堆棧和鏈式堆棧s,分別編寫函數(shù)SelectItem(Stack&s,intn),要求在堆棧中查找元素n在棧中第一次出現(xiàn)的位置,并將該位置元素移至棧頂,同時其他元素次序不變。(注意:用int匹配堆棧的模板).作業(yè)2-17對于順序堆棧和鏈式堆棧s,分別編寫函數(shù)Selec98基本思想:取棧頂元素,若不匹配,則進行彈棧操作;找到(或無法找到)后恢復原來的元素次序。關鍵點:記錄彈出的順序,后彈出的元素能夠先被壓回原來的棧,因此需要使用一個輔助堆棧。.基本思想:.99示例105112shelpStack5173n=515112105173751511210377351.示例105112shelpStack5173n=515112100參考答案intSelectItem(Stack<int>&s,intn){AStack<int>temp(100);//順序堆棧,輔助棧

//LStack<int>temp;//鏈式堆棧

boolflag=false;//是否存在元素nintloc=0;//記錄n所在的位置

while(!s.isEmpty()&&s.Peek()!=n

){temp.Push(s.Pop());loc++;}棧非空且當前元素不等于n.參考答案intSelectItem(Stack<int>101if(!s.isEmpty()){s.Pop();flag=true;}//彈出nwhile(!temp.isEmpty())//將輔助棧中元素壓入原棧

{s.Push(temp.Pop());}if(flag)thens.Push(n);

elseloc=-1;returnloc;}因為找到元素而跳出循環(huán).if(!s.isEmpty())因為找到元素102作業(yè)2-25編寫并實現(xiàn)雙端隊列類,雙端隊列是可進行如下操作的線性表。(1)push(item)--item插入到隊列的前端;(2)pop(item)--刪除前端元素且賦給item;(3)inject(item)--item插入尾端;(4)eject(item)--刪除尾端元素且賦給item.作業(yè)2-25編寫并實現(xiàn)雙端隊列類,雙端隊列是可進行如下操作的103結點結構SLNode:數(shù)據(jù)域和指針域;類成員:隊首和隊尾的SLNode類型指針、指示元素個數(shù)的整型變量;Push(item插入隊列前端)

若空,則加入一個以item為數(shù)據(jù)域的結點,元素個數(shù)為1;否則,temp記錄原隊首指針front;

創(chuàng)建以item為數(shù)據(jù)域的新結點,作為新的隊首,賦值給front;front的指針域指向temp,元素個數(shù)加1。.結點結構SLNode:數(shù)據(jù)域和指針域;.104Pop(刪除前端元素,并賦值item)若空,則錯誤;否則,temp記錄原隊首指針front;

隊首后移,即frontnext(front);

返回temp的數(shù)據(jù)域;

刪除temp結點,元素個數(shù)減1;

若大小為零,則隊尾指針rear賦值為NULL。.Pop(刪除前端元素,并賦值item).105Inject(item插入隊尾)若空,則加入一個以item為數(shù)據(jù)域的結點,元素個數(shù)為1;否則,創(chuàng)建以item為數(shù)據(jù)域的新結點temp,作為新的隊尾,即next(rear)temp;隊尾指針后移,即rearnext(rear);元素個數(shù)加1。.Inject(item插入隊尾).106Eject(刪除隊尾元素并賦值給item)若空,則出錯;否則,

找到隊尾指針的前驅指針tempfront.IF(temprear)THEN(WHILE(next(temp)rear)DO(tempnext(temp))隊尾指針更新,即reartemp,

要刪除結點是next(temp),返回數(shù)據(jù)域,刪除結點,元素個數(shù)減1。

若大小為零,front和rear賦值為NULL。.Eject(刪除隊尾元素并賦值給item).107作業(yè)3-10設稀疏矩陣Mmn中有t個非零元素,用三元組表的方式存儲.請設計一個算法,計算矩陣M的轉置矩陣N,且算法的時間復雜性為O(n+t).注意,書中給出的算法的復雜性為O(nt)。.作業(yè)3-10設稀疏矩陣Mmn中有t個非零元素,用三元組表的108M=500001002000000-300-605N=50100-3000000200-6000050050a[0]1010a[1]1220a[2]30-30a[3]32-60a[4]335a[5]0050b[0]0110b[1]03-30b[2]2120b[3]23-60b[4]335b[5]算法的關鍵是求出a中元素在b中的位置.M=50000N=5010109Bindex=0;FORj=0TOn-1DO

FORk=0TOt-1DOIFcol(A[k])=jThen (row(B[Bindex])=j. col(B[Bindex])=row(A[k]). value(B[Bindex])=Value(A[k]).

Bindex++)a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30j=0,k=0,a[0],列坐標=0;存儲j=0;k=1;a[1],列坐標=0;存儲j=0;k=2;a[2],列坐標=2;j=0;k=3;a[3],列坐標=0;存儲j=0;k=4;j=0;k=5;j=1;k=0005030-301010.Bindex=0;a[0]00502120011033523110a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30005030-301010j=1,k=0,a[0],列坐標=0j;j=1,k=1;列坐標1j=1,k=2;j=1,k=3;j=1,k=4;j=1,k=5;j=2,k=0;j=2,k=1;j=2,k=2,列坐標=2=jFORj=0TOn-1DO

FORk=0TOt-1DOIFcol(A[k])=jThen2201.a[0]00502120011033523-6003-300111005030-30101033532-601220a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30b[2]a[x]b[y]?y=列坐標小于col(a[x])的元素個數(shù)+

列坐標等于col(a[x])且在a[x]之前的元素個數(shù).005030-30101033532-601220a[0]0112a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30基本思想:

數(shù)組num存儲a中每列非零元素個數(shù);數(shù)組pos存儲a中每列第一個非零元素在b的三元組表中的位置;

302101230123num0335pos.a[0]00502120011033523-6003-30基113算法:TRANSPOSE(A.B)TP

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論