算法設(shè)計(jì)與分析課后習(xí)題解答

算法設(shè)計(jì)與分析課后習(xí)題解答

算法設(shè)計(jì)與分析基礎(chǔ)課后練習(xí)答案

習(xí)題1.1

4.設(shè)計(jì)一個(gè)計(jì)算錯(cuò)誤！未找到引用源。的算法，n是任意正整數(shù)。除

了賦值和比較運(yùn)算，該算法只能用到基本的四則運(yùn)算操作。

算法求錯(cuò)誤！未找到引用源。

〃輸入：一個(gè)正整數(shù)n錯(cuò)誤！未找到引用源。2

〃輸出：。

stepl:a=l；

st叩2:若a*a<n轉(zhuǎn)step3,否則輸出a；

step3:a=a+l轉(zhuǎn)step2；

5.a.用歐幾里德算法求gcd(31415,14142)0

b.用歐幾里德算法求gcd(31415,14142)，比檢查min{m,n)和

gcd(m,

n)間連續(xù)整數(shù)的算法快多少倍？請(qǐng)估算一下。

a.gcd(31415,14142)=gcd(14142,3131)=gcd(3131,1618)=gcd(1618,

1513)=gcd(1513,105)=gcd(1513,105)=gcd(105,43)=gcd(43,19)=gcd(19,

5)=gcd(5,4)=gcd(4,1)=gcd(l,0)=1.

b.有a可知計(jì)算gcd(31415,14142)歐幾里德算法做了11次除法。

連續(xù)整數(shù)檢測(cè)算法在14142每次迭代過程中或者做了一次除法，或者

兩次除法，因此這個(gè)算法做除法的次數(shù)鑒于1?14142和2?14142之間,

所以歐幾里德算法比此算法快1?14142/11.1300與2?14142/11.

2600倍之間。

6.證明等式gcd(m,n)=gcd(n,mmodn)對(duì)每一對(duì)正整數(shù)m,n都成立.

Hint:

根據(jù)除法的定義不難證明：

?如果d整除u和v,那么d一定能整除u±v;

?如果d整除u,那么d也能夠整除u的任何整數(shù)倍ku.

對(duì)于任意一對(duì)正整數(shù)m,n,若d能整除m和n,那么d一定能整除n和

r=mmodn=m-qn；顯然，若d能整除n和r,也一定能整除m=r+qn和n。

數(shù)對(duì)(m,n)和(n,r)具有相同的公約數(shù)的有限非空集，其中也包括了最大

公約數(shù)。故gcd(m,n)=gcd(n,r)

7.對(duì)于第一個(gè)數(shù)小于第二個(gè)數(shù)的一對(duì)數(shù)字，歐幾里得算法將會(huì)如何處

理?該算法在處理這種輸入的過程中,上述情況最多會(huì)發(fā)生幾次？

Hint:

對(duì)于任何形如0<=m<n的一對(duì)數(shù)字,Euclid算法在第一次疊代時(shí)交

換m和n,即

gcd(m,n)=gcd(n,m)

并且這種交換處理只發(fā)生一次.

8a對(duì)于所有l(wèi)〈m,nW10的輸入,Euclid算法最少要做幾次除法?(1次)

b,對(duì)于所有l(wèi)Wm,nW10的輸入,Euclid算法最多要做幾次除法?(5次)

gcd(5,8)

習(xí)題1.2

L(農(nóng)夫過河)

P—農(nóng)夫W—狼G一山羊C—白菜

2.(過橋問題

)

1,2,5,10—分別代表4個(gè)人,f一手電筒

4.對(duì)于任意實(shí)系數(shù)a,b,c,某個(gè)算法能求方程axA2+bx+c=0的實(shí)根，寫出

上述算法的偽代碼(可以假設(shè)sqrt(x)是求平方根的函數(shù))

算法Quadratic(a,b,c)

〃求方程axA2+bx+c=0的實(shí)根的算法

〃輸入:實(shí)系數(shù)a,b,c

〃輸出:實(shí)根或者無解信息

IfaWO

D—b*b-4*a*c

IfD>O

temp-2*a

xl-(-b+sqrt(D))/temp

x2-(-b-sqrt(D))/temp

returnxl,x2

elseifD=0return-b/(2*a)

elsereturn“norealroots”

else//a=0

ifbWOreturn-c/b

else//a=b=O

ifc=0return“norealnumbers“elsereturn“norealrootsz/

5.描述將十進(jìn)制整數(shù)表達(dá)為二進(jìn)制整數(shù)的標(biāo)準(zhǔn)算法

a.用文字描述

b.用偽代碼描述

解答：

a.將十進(jìn)制整數(shù)轉(zhuǎn)換為二進(jìn)制整數(shù)的算法

輸入：一個(gè)正整數(shù)n

輸出：正整數(shù)n相應(yīng)的二進(jìn)制數(shù)

第一步:用n除以2,余數(shù)賦給Ki(i=0,l,2...),商賦給n

第二步：如果n=0,則到第三步，否則重復(fù)第一步

第三步：將Ki按照i從高到低的順序輸出

b.偽代碼

算法DectoBin(n)

〃將十進(jìn)制整數(shù)n轉(zhuǎn)換為二進(jìn)制整數(shù)的算法

〃輸入：正整數(shù)n

〃輸出：該正整數(shù)相應(yīng)的二進(jìn)制數(shù)，該數(shù)存放于數(shù)組Bin口...n]中

i=l

whilen!=0do{

Bin[i]=n%2;

n=(int)n/2;

i++；

)

whilei!=0do{

printBin[i];

i--；

)

9.考慮下面這個(gè)算法

，它求的是數(shù)組中大小相差最小的兩個(gè)元素的差.(算法略)對(duì)這個(gè)算法

做盡可能多的改進(jìn).

算法MinDistance(A[O..n-l])

〃輸入:數(shù)組A[O..n-l]

//輸出:thesmallestdistancedbetweentwoofitselements

習(xí)題1.3

1.考慮這樣一個(gè)排序算法，該算法對(duì)于待排序的數(shù)組中的每一個(gè)元素,

計(jì)算比它

小的元素個(gè)數(shù)，然后利用這個(gè)信息，將各個(gè)元素放到有序數(shù)組的相應(yīng)位

置上去.

a.應(yīng)用該算法對(duì)列表”60,35,81,98,14,47”排序

b.該算法穩(wěn)定嗎？

c.該算法在位嗎？

解：

a.該算法對(duì)列表”60,35,81,98,14,47”排序的過程如下所示

b.該算法不穩(wěn)定.比如對(duì)列表”2,2*"排序

c.該算法不在位.額外空間forSandCount[]

4.(古老的七橋問題

)

第2早

習(xí)題2.1

7.對(duì)下列斷言進(jìn)行證明:(如果是錯(cuò)誤的，請(qǐng)舉例)

a.如果t(n)60(g(n),則g(n)e0(t(n))

b.a>；0時(shí),@(ag(n))=?(g(n))

解：

a.這個(gè)斷言是正確的。它指出如果t(n)的增長(zhǎng)率小于或等于g(n)的增

長(zhǎng)率，那么g(n)的增長(zhǎng)率大于或等于t(n)的增長(zhǎng)率

由t(n)Wc,g(n)foralln，nO,wherec>0

則：()t(n)Wg(n)foralln^nOcl

b.這個(gè)斷言是正確的。只需證明)(ag(n))??(g(n)),?(g(n))??(ag(n))o

設(shè)f(n)￡?(ag(n)),則有：

f(n)Wcag(n)

f(n)^clg(n)foralln>=nO,c>0foralln>=nO,cl=ca>0

即：f(n)G?(g(n))

又設(shè)f(n)e0(g(n)),則有:f(n)Wcg(n)foralln>=n0,c>0

f(n)Wc

aag(n)=clag(n)foralln>=nO,cl=c/a>O

即：f(n)e@(ag(n))

8.證明本節(jié)定理對(duì)于下列符號(hào)也成立：

a.Q符號(hào)

b.?符號(hào)

證明：

a。weneedtoproofthatiftl(n)GQ(gl(n))andt2(n)￡Q(g2(n)),then

tl(n)+t2(n)eQ(max{gl(n),g2(n)})o

由tl(n)GQ(gl(n)),

tl(n)^clgl(n)foralln>=nl,wherecl>0

由t2(n)eQ(g2(n)),

T2(n)〉c2g2(n)foralln>=n2,wherec2>0

那么，取c>=min{cl,c2},當(dāng)n>=max{nl,n2}時(shí)：

tl(n)+t2(n)^clgl(n)+c2g2(n)

2cgl(n)+cg2(n)^c[gl(n)+g2(n)]

2cmax{gl(n),g2(n)}

所以以命題成立。

b.tl(n)+t2(n)G?(max(gl(n),g2(n)))

證明：由大?的定義知，必須確定常數(shù)cl、c2和nO,使得對(duì)于所有

n>=nO,有：clmax((gl(n),g2(n))^tl(n)+t2(n)^max(gl(n),g2(n))

由tl(n)e?(gl(n))知,存在非負(fù)整數(shù)al,a2和nl使：

al*gl(n)<=tl(n)<=a2*gl(n)----(1)

由t2(n)w0(g2(n))知,存在非負(fù)整數(shù)bl,b2和n2使：

bl*g2(n)<=t2(n)<=b2*g2(n)----(2)

(1)+(2)：

al*gl(n)+bl*g2(n)<=tl(n)+t2(n)<=a2*gl(n)+b2*g2(n)

令cl=min(al,bl),c2=max(a2,b2),貝

Cl*(gl+g2)<=tl(n)+t2(n)<=c2(gl+g2)一一(3)

不失一般性假設(shè)

max(gl(n),g2(n))=gl(n).

顯然，gl(n)+g2(n)<2gl(n),即gl+g2<2max(gl,g2)

又

g2(n)>0,gl(n)+g2(n)>gl(n),iPgl+g2>max(gl,g2)o

則(3)式轉(zhuǎn)換為：

Cl*max(gl,g2)<=tl(n)+t2(n)<=c2*2max(gl,g2)

所以當(dāng)cl=min(al,bl),c2=2c2=2max(cl,c2),nO=max(nl,n2)時(shí),當(dāng)

n>=nO時(shí)上述不等式成立。

證畢。

習(xí)題2.2

2.請(qǐng)用錯(cuò)誤！未找到引用源。的非正式定義來判斷下列斷言是真還是

假。

a.n(n+1)/2G0(n3)b.n(n+1)/2e0(n2)

c.n(n+1)/2￡?(n3)d,n(n+1)/2￡Q(n)

答：c假，其它真。

5.按照下列函數(shù)的增長(zhǎng)次數(shù)對(duì)它們進(jìn)行排列(按照從低到高的順序)

(n?2)),5lg(n+100)10,22n,0.001n4+3n3+l,In2n,錯(cuò)誤!未找到引用源。

3n.

答：

習(xí)題2.3

1.計(jì)算下列求和表達(dá)式的值。

答

，：

3.考慮下面的算法。

a.該算法求的是什么？

b.它的基本操作是什么？

c.該基本操作執(zhí)行了多少次？

d.該算法的效率類型是什么？

e.對(duì)該算法進(jìn)行改進(jìn)，或者設(shè)計(jì)一個(gè)更好的算法，然后指出它們的

效率類型。

如果做不到這一點(diǎn)，請(qǐng)?jiān)囍C明這是不可能做到的。

9.證明下面的公式：

可以使用數(shù)學(xué)歸納法，也可以像10歲的高斯一樣，用洞察力來解決

該問題。這個(gè)小學(xué)生長(zhǎng)大以后成為有史以來最偉大的數(shù)學(xué)家之一。

數(shù)學(xué)歸納法：

高斯的方法：

習(xí)題2.4

1.解下列遞推關(guān)系(做a,b)a.?x(n)=x(n-l)+5當(dāng)n>l時(shí)??x(l)=0

解：

b.

解：?x(n)=3x(n-l)??x(l)=4當(dāng)n>l時(shí)

2.對(duì)于計(jì)算n!的遞歸算法F(n),建立其遞歸調(diào)用次數(shù)的遞推關(guān)系并求

解。

解：

3.考慮下列遞歸算法，該算法用來計(jì)算前n個(gè)立方的和：

S(n)=13+23+…+n3。

算法S(n)

〃輸入：正整數(shù)n

〃輸出：前n個(gè)立方的和

ifn=lreturn1

elsereturnS(n-l)+n*n*n

a.建立該算法的基本操作次數(shù)的遞推關(guān)系并求解

b.如果將這個(gè)算法和直截了當(dāng)?shù)姆沁f歸算法比，你做何評(píng)價(jià)？

解

7.a.請(qǐng)基于公式2n=2n-l+2n-l,設(shè)計(jì)一個(gè)遞歸算法。當(dāng)n是任意非負(fù)

整數(shù)的時(shí)候，該算法能夠計(jì)算2n的值。

b.建立該算法所做的加法運(yùn)算次數(shù)的遞推關(guān)系并求解

c.為該算法構(gòu)造一棵遞歸調(diào)用樹，然后計(jì)算它所做的遞歸調(diào)用次數(shù)。

d.對(duì)于該問題的求解來說，這是一個(gè)好的算法嗎？解:a.算法power(n)

〃基于公式2n=2n-l+2n-l,計(jì)算2n

〃輸入:非負(fù)整數(shù)n

n〃輸出:2的值

Ifn=0return1

Elsereturnpower(n-l)+power(n-l)

c.

n

C(n)=￡2

i=0i=2n+l-l

8.考慮下面的算法

算法Minl(A[0..n-l])

〃輸入:包含n個(gè)實(shí)數(shù)的數(shù)組A[0..n-l]

Ifn=lreturnA[0]

日setemp*-Minl(A[0..n-2])

Iftemp^A[n-l]returntemp

日sereturnA[n-1]

a.該算法計(jì)算的是什么？

b.建立該算法所做的基本操作次數(shù)的遞推關(guān)系并求解

解：

a.計(jì)算的給定數(shù)組的最小值

?C(n-l)+lb.C(n)=?O?foralln>ln=l

9.考慮用于解決第8題問題的另一個(gè)算法，該算法遞歸地將數(shù)組分成兩

半.我們將它稱為Min2(A[0..n-l])

4.

爬梯子假設(shè)每一步可以爬一個(gè)或兩格梯子，爬一部n格梯子一共可

以用幾種的不同方法？（例如，一部3格的梯子可以用三種不同的方法爬：

1-1-1,1-2和2-1）。

6.改進(jìn)算法Fib,使它只需要？（1）的額外空間。

7.證明等式：

答：數(shù)學(xué)歸納法證明

習(xí)題2.6

1.考慮下面的排序算法，其中插入了一個(gè)計(jì)數(shù)器來對(duì)關(guān)鍵比較次數(shù)進(jìn)

行計(jì)數(shù).

算法SortAnalysis（A[0..n-l]）

〃input:包含n個(gè)可排序元素的一個(gè)數(shù)組A[O..n-l]

“output:所做的關(guān)鍵比較的總次數(shù)

count-0

fori<-1ton-1do

v-A[i]

whilej>OandA[j]>vdo

count,—count+1

A[j+1]-AQ]

j-j+l

A[j+1]-v

returncount

比較計(jì)數(shù)器是否插在了正確的位置?如果不對(duì)，請(qǐng)改正.

解:應(yīng)改為：

算法SortAnalysis(A[0..n-l])

〃input:包含n個(gè)可排序元素的一個(gè)數(shù)組A[O..n-l]

“output:所做的關(guān)鍵比較的總次數(shù)

count-0

fori*-lton-1do

returnp

基本操作乘法運(yùn)算總次數(shù)M(n):

M(n)=￡2=2n￡0(n)

i=ln

c.不行.因?yàn)橛?jì)算任意一個(gè)多項(xiàng)式在任意點(diǎn)x的值，都必須處理它的n+1

個(gè)系數(shù).例如：(x=l,p(x)=an+an-l+..+al+aO,至少要做n次加法運(yùn)算)

5.應(yīng)用選擇排序?qū)π蛄蠩,X,A,M,P,L,E按照字母順序排序.

6.選擇排序是穩(wěn)定的嗎?(不穩(wěn)定)

7.用鏈表實(shí)現(xiàn)選擇排序的話，能不能獲得和數(shù)組版相同的?(n2)效率？

Yes.Bothoperation—findingthesmallestelementandswappingit-can

bedoneasefficientlywiththelinkedlistaswithanarray.

8.應(yīng)用冒泡排序?qū)π蛄蠩,X,A,M,P,L,E按照字母順序排序.

9a請(qǐng)證明，如果對(duì)列表比較一遍之后沒有交換元素的位置，那么這個(gè)

表已經(jīng)排

好序了，算法可以停止了.

b.結(jié)合所做的改進(jìn),為冒泡排序?qū)懸欢蝹未a.

C.請(qǐng)證明改進(jìn)的算法最差效率也是平方級(jí)的.

Hints:

a.第i趟冒泡可以表示為：

如果沒有發(fā)生交換位置,那么：

b.AlgorithmsBetterBubblesort(A[0,.n-l])

〃用改進(jìn)的冒泡算法對(duì)數(shù)組A[0..n-l]排序

〃輸入:數(shù)組A[0..n-l]

〃輸出:升序排列的數(shù)組A[0..n-l]

count-n-1〃進(jìn)行比較的相鄰元素對(duì)的數(shù)目

flag-true〃交換標(biāo)志

whileflagdo

flag*-false

fori=0tocount-1do

ifA[i+l]<A[i]

swap(A[i],A[i+l])

flag-true

count,―count-1

c最差情況是數(shù)組是嚴(yán)格遞減的，那么此時(shí)改進(jìn)的冒泡排序會(huì)蛻化為原

來的冒泡排序.

10.冒泡排序是穩(wěn)定的嗎?(穩(wěn)定)

習(xí)題3.2

1.對(duì)限位器版的順序查找算法的比較次數(shù)：

a.在最差情況下

b.在平均情況下.假設(shè)成功查找的概率是p(O<=p<=l)

Hints:

a.Cworst(n)=n+1

b.在成功查找下，對(duì)于任意的I,第一次匹配發(fā)生在第i個(gè)位置的可能性

是ph

比較次數(shù)是i.在查找不成功時(shí)，比較次數(shù)是n+1,可能性是1-p.

6.給出一個(gè)長(zhǎng)度為n的文本和長(zhǎng)度為m的模式構(gòu)成的實(shí)例，它是蠻力字

符串匹配算法的一個(gè)最差輸入.并指出,對(duì)于這樣的輸入需要做多少次字符

比較運(yùn)算.

Hints:

文本:由n個(gè)0組成的文本

模式:前m-1個(gè)是0,最后一個(gè)字符是1

比較次數(shù):m(n-m+l)

7.為蠻力字符匹配算法寫一個(gè)偽代碼，對(duì)于給定的模式,它能夠返回給

定的文本中所有匹配子串的數(shù)量.

AlgorithmsBFStringmatch(T[0..n-l],P[0..m-l])

〃蠻力字符匹配

〃輸入:數(shù)組長(zhǎng)度為n的文本，數(shù)組長(zhǎng)度為m的模

式〃輸出:在文本中匹配成功的子串?dāng)?shù)量

count-0

fori'—0ton-mdo

j-o

whileandP[j]=T[i+j]

j-j+l

ifj=m

count,—count+1

returncount

8.如果所要搜索的模式包含一些英語中較少見的字符,我們應(yīng)該如何

修改該蠻力算法來利用這個(gè)信息.

Hint:每次都從這些少見字符開始比較，如果匹配，則向左邊和右邊進(jìn)

行其它字符的比較.

習(xí)題3.4

8.解釋一下如何對(duì)排序問題應(yīng)用窮舉查找，并確定這種算法的效率類

型。

答：生成給定元素的一個(gè)排列，通過連續(xù)比較它們之間的元素，檢查

他們是否符合排序的要求。如果符合就停止，否則重新生成新的排列。

最差情況生成排列的個(gè)數(shù)是n!,每趟連續(xù)元素比較次數(shù)為n-l次。所

以效率類型為0(n!(n-l))o

9.幻方一個(gè)n階幻方是把從1到n2的整數(shù)填入一個(gè)n階方陣，每個(gè)

整數(shù)只出現(xiàn)一次，使得每一行，每一列，每一條主對(duì)角線的和都相等。

a.證明：如果一個(gè)n階幻方存在的話,所討論的和一定等于n(n2+l)/2o

答：令s為n階幻方的每一行的和。則把從1到n2的整數(shù)求和可得

如下式子

由上式可得：

算法

MaxMin(A[l..r]zMax,Min)

〃該算法利用分治技術(shù)得到數(shù)組A中的最大值和最小值

〃輸入：數(shù)值數(shù)組

〃輸出：最大值Max和最小值Min

if(r=l)Max—A[l]；Min-A[l];〃只有一個(gè)元素時(shí)

else

ifr-|=l〃有兩個(gè)元素時(shí)

ifA[l]^A[r]

Max-A[r];Min-A[l]

else

Max—A[l];Min*-A[r]

else//r—l>l

MaxMin(A[l,(l+ij/2],Maxl,Minl);〃遞歸解決前一部分

MaxMin(A[(l+r/)2..r],Max2,Min2);〃遞歸解決后一部分

ifMaxl<Max2Max=Max2〃從兩部分的兩個(gè)最大值中選擇大值

ifMin2<MinlMin=Min2;〃從兩部分的兩個(gè)最小值中選擇小值｝

b.假設(shè)n=2k,比較次數(shù)的遞推關(guān)系式：

C(n)=2C(n/2)+2forn>2

C(l)=0,C(2)=l

C(n)=C(2k)=2C(2k-l)+2

=2[2C(2k-2)+2]+2

=22C(2k-2)+22+2

=22[2C(2k-3)+2]+22+2

=23C(2k-3)+23+22+2

=2k-lC(2)+2k-l+2k-2+...+2//C(2)=l

=2k-l+2k-l+2k-2+...+2〃后面部分為等比數(shù)列求和

=2k-l+2k-2//2(k-l)=n/2,2k=n

=n/2+n-2

=3n/2-2

b.蠻力法的算法如下：

算法simpleMaxMin(A[l..r])

〃用蠻力法得到數(shù)組A的最大值和最小值

〃輸入：數(shù)值數(shù)組

〃輸出：最大值Max和最小值Min

Max=Min=A[l];

fori=l+ltordo

ifA[i]>MaxMax-A[i];

elseifA[i]<MinMin—A[i]

returnMax,Min

)

b.

最好情況(列表升序或降序)下：

Cbest(n)=2Cbest(n/2)+n/2forn>l(n=2k)

Cbest(l)=0

c.鍵值比較次數(shù)M(n)

M(n)=2M(n)+2nforn>l

M(l)=0

習(xí)題4.2

1.應(yīng)用快速排序?qū)π蛄蠩,X,A,M,P,L,E按字母順序排序

4.請(qǐng)舉一個(gè)n個(gè)元素?cái)?shù)組的例子,使得我們有必須對(duì)它使用本節(jié)提到

的“限位器”.

限位器的值應(yīng)是多少年來?為什么一個(gè)限位器就能滿足所有的輸入呢?

Hints:

Withthepivotbeingtheleftmostelement,theleft-to-rightscanwillget

outofboundsifandonlyifthepivotislargerthantheotherelements.

Appendingasentinel(限位器)ofvalueequalA[0](orlargerthanA[0])

afterthearrayJslastelement,thequicksortalgorithmswillstopthe

indexoftheleft-to-rightscanofA[0..n-l]fromgoingbeyondpositionn.

8.設(shè)計(jì)一個(gè)算法對(duì)n個(gè)實(shí)數(shù)組成的數(shù)組進(jìn)行重新排列，使得其中所有的

負(fù)元素都位于正元素之前.這個(gè)算法需要兼顧空間和時(shí)間效率.

Algorithmsnetbeforepos(A[0..n-l])

〃使所有負(fù)元素位于正元素之前

〃輸入:實(shí)數(shù)組A[O..n-l]

〃輸出:所有負(fù)元素位于于正元素之前的實(shí)數(shù)組A[O..n-l]

A[-l]--l;A[n]-1〃限位器

i-O;j*-n-l

Whiledo

WhileA[i]WOdo

i-i+1

whileA[j]2Odo

j-j-1

swapA[i]andA[j]

swapA[i]andA[j]//undothelastswap

當(dāng)全是非負(fù)數(shù)或全是非正數(shù)時(shí)需要限位器.

習(xí)題4.3

2.當(dāng)n=2k時(shí),用反向替換法求下面的遞推方程：

當(dāng)n>l時(shí),Cw(n)=Cw(n/2)+l,Cw(l)=l

(略)

習(xí)題5.1

4.應(yīng)用插入排序?qū)π蛄蠩,X,A,M,P,L,E按照字母順序排序.

答:插入排序過程如下：

習(xí)題5.4

2.使用下面的方法生成｛1,2,3,4｝的全部排列：

a.從底向上的最小變化算法。

b.Johnson-Trotter算法。

字典序算法。

答：從底向上的最小變化算法過程如下：

b.Johnson-Trotter算法實(shí)現(xiàn)如下：

c.字典序算法實(shí)現(xiàn)如下：

9.a.當(dāng)n=4時(shí)，用減一技術(shù)生成它的格雷碼。

答：用減一技術(shù)生成格雷碼：

n=l0-*1;

n=200—01fli-*10;(從左到右，最左邊填0,從右到左，最左邊填

1)n=3000^001—011-*010-110—111—101-*100n=4生成的

格雷碼：

習(xí)題5.