第早

算法基本概念

思考與練習

1.什么是程序？什么是算法？算法和程序的區(qū)別是什么？

參考答案：計算機程序要對問題的每個對象和處理規(guī)則給出正確詳盡的描述，其中程序

的數(shù)據(jù)結構和變量用來描述問題的對象，程序結構、函數(shù)和語句用來描述問題的算法。算法

數(shù)據(jù)結構是程序的兩個重要方面。

算法是問題求解過程的精確描述，一個算法由有限條可完全機械地執(zhí)行的、有確定結果

的指令組成。

程序與算法不同，程序是算法用某種語言的具體實現(xiàn)。程序可以不滿足算法有限性的性

質(zhì)，通常求解一個問題可能會有多種算法可供選擇，選擇的主要標準是算法的正確性和可靠

性，簡單性和易理解性。其次是算法所需要的存儲空間少和執(zhí)行更快等。

2.算法有哪些特點？為什么說一個具備了所有特征的算法，不一定就是一個實用的算

法？

參考答案：算法需要指令正確地描述了要完成的任務和它們被執(zhí)行的順序。計算機按算法指

令所描述的順序執(zhí)行算法的指令能在有限的步驟內(nèi)終止，或終止于給出問題的解，或終止于

指出問題對此輸入數(shù)據(jù)無解。

一個實用的算法，不僅要求步驟有限，同時要求運行這些步驟所花費的時間是人們可以接受

的。如果一個算法需要執(zhí)行數(shù)十百億億計的運算步驟，從理論上說，它是有限的，最終可以

結束，但是，以當代計算機每秒數(shù)億次的運算速度，也必須運行數(shù)百年以上時間，這是人們

所無法接受的，因而是不實用的算法。

3.考慮這樣一個排序算法，該算法對于待排序的數(shù)組中的每一個元素，計算比它小的

元素個數(shù)，然后利用這個信息，將各個元素放到有序數(shù)組的相應位置上去。

#include"stdafx.hn

#incIudeHstdio.hH

#defineN100

intb[N];

int1=0;

intMax(int*a,intm,intn){〃求最大值

intxl,x2;

if{n-in<=l){

if(n-m=O){b[l]=a[m];l++；retumm;}〃將底層比較的較小值存入b[n]

if(a[n]>=a[m]){b[l]=a[m];l-H-;retumn;}

else{b[l]=a[n];l++;returnm;}

}

else{

x1=Max(a,m,(m+n)/2);

x2=Max(a,(m+n)/2+1,n);

if(a[x1]>=a[x2])retumxl;

elsereturnx2;

}

}

intMin(int*b,intm,intn){〃求最小值

intxl,x2;

ifi(n-m<=l){

if{m==n)retumm;

elseif(b[n]<b[m])retumn;

elsereturnm;

}

else{

x1=Min(b,m,(m+n)/2);

x2=Min(b,(m+n)/2+1,n);

if(b[xl]<=b[x2])retumxl;

elsereturnx2;

}

}

voidmain(){

inta[N];

ints,i,n;

printfl(,,Pleaseinputthenumber

scanfi["%d",&n);

printf(nPleaseinput:")；

for(i=O;i<n;i++){

scanf(n%d,r,&a[i]);

}

s=Max(a,O,n-l);

printf(HMax:%d\n",a[s]);

s=Min(b,O,l-l)；

printf(HMin:%d\nM,b[s]);

)

4.描述將十進制整數(shù)表達為二進制整數(shù)的標準算法，分別使用偽代碼描述和用文字描

述。

參考答案：

a.將十進制整數(shù)轉換為二進制整數(shù)的算法

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

輸出：正整數(shù)n相應的二進制數(shù)

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

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

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

b.偽代碼

算法DectoBin(n)

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

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

〃輸出：該正整數(shù)相應的二進制數(shù)，該數(shù)存放于數(shù)組中

i=l

whilen!=0do{

Bin[i]=n%2;

n=(int)n/2;

i++；

whilei!=0do{

printBin[i];

i--；

5.對下面程序段進行算法的時間復雜度分析，并給出結果。

1.x=0；

2.for(k=l;k〈=n;k++)

3.x=x+l；

4.for(i=l;i<=n;i-H-)

5.fbr(j=l;j<=n;j++)

6.y=y+l；

參考答案：

該算法段的時間復雜度為T(〃)=0(〃o)。

當有若干個循環(huán)語句時，算法的時間復雜度是由嵌套層數(shù)最多的循環(huán)語句中最內(nèi)層語句的頻

度/(〃)決定的。

7.對下面程序段進行算法的時間復雜度分析，并給出結果。

1.x=l；

2.for(i=l;i<=n;i++)

3.fbr(j=l;jv=i；jH)

4.for(k=l;k<=j;j++)

5.x=x+l；

參考答案：

該算法段中頻度最大的語句是(5),從內(nèi)層循環(huán)向外層分析語句(5)的執(zhí)行次數(shù)：

〃(〃+1)(〃+2)n(n+1)

njjnjW+l)_6

"2―2

/=1j=\k=\i=\j=\/=1/乙

則該算法段的時間復雜度為：T(〃)=(0(/?/12)+低次項尸0(〃3)。

8.分析：考慮下面的算法，輸入：N個元素的數(shù)組輸出：按遞增順序排序的數(shù)組

voidsort(intA[],intn)

(

inti,j,temp；

fbr(i=0;i<n-l;i4-F)

{for(intj=O;j<n;j++)

if(A[j]<A[i])

temp=A[i];

A[i]=AO];

A[j]=temp;

)

}

在什么情況下所執(zhí)行的元素賦值的次數(shù)最多？最多多少次?

在什么情況下所執(zhí)行的元素賦值的次數(shù)最少？最少多少次?

參考答案：

在倒序情況下所執(zhí)行的元素賦值的次數(shù)最多，最多n!次

在順序情況下所執(zhí)行的元素賦值的次數(shù)最少，最少n-1次

第2章

常用的Java基礎和數(shù)學方法

/思考與練習

1.簡述Java程序的特點。

參考答案：

Java是一種跨平臺，適合于分布式計算環(huán)境的面向?qū)ο缶幊陶Z言。具體來說，它具

有如下特性：簡單性、面向?qū)ο蟆⒎植际?、解釋型、可靠、安全、平臺無關、可移植、

高性能、多線程、動態(tài)性等。

2.簡述Java垃圾回收機制。

參考答案：

JAVA是純粹的面向?qū)ο蟮木幊陶Z言，其程序以類為單位，程序運行期間會在內(nèi)存

中創(chuàng)建很多類的對象。這些對象在完成任務之后，JAVA的垃圾回收機制會自動釋放這

些對象所占用的空間，使回收的內(nèi)存能被再次利用，提高程序的運行效率。垃圾回收不

僅可以提高系統(tǒng)的可靠性、使內(nèi)存管理與類接口設計分離，還可以使開發(fā)者減少了跟蹤

內(nèi)存管理錯誤的時間，從而把程序員從手工回收內(nèi)存空間的繁重工作中解脫出來。

JAVA垃圾回收機制另一個特點是，進行垃圾回收的線程是一種低優(yōu)先級的線程，

在一個Java程序的生命周期中，它只有在內(nèi)存空閑的時候才有機會運行。

3.Java運行時系統(tǒng)執(zhí)行程序大致分成哪幾個步驟，請詳細說明。

參考答案：

運行jvm字符碼的工作是山解釋器來完成的。解釋執(zhí)行過程分三步進行：

代碼的裝入、代碼的校驗、和代碼的執(zhí)行。

裝入代碼的工作由“類裝載器classloader”完成。類裝載器負責裝入運行一個程序需要

的所有代碼，這也包括程序代碼中的類所繼承的類和被調(diào)用的類。當類裝載器裝入一個

類時，該類被放在自己的名字空間中。除了通過符號引用自己名字空間以外的類，類之

間沒有其他辦法可以影響其他類。在本臺計算機的所有類都在同一地址空間中，而所有

從外部引進的類，都有一個自己獨立的名字空間。這使得本地類通過共享相同的名字空

間獲得較高的運行效率，同時又保證它們與從外部引進的類不會相互影響。當裝入了運

行程序需要的所有類后，解釋器便可確定整個可執(zhí)行程序的內(nèi)存布局。解釋器為符號引

用與特定的地址空間建立對應關系及查詢表。通過在這一階段確定代碼的內(nèi)布局，java

很好地解決了由超類改變而使子類崩潰的問題，同時也防止了代碼的非法訪問。隨后，

被裝入的代碼由字節(jié)碼校驗器進行檢查。校驗器可以發(fā)現(xiàn)操作數(shù)棧益處、非法數(shù)據(jù)類型

轉化等多種錯誤。通過校驗后，代碼便開始執(zhí)行了。

java字節(jié)碼的執(zhí)行有兩種方式：

1)即時編譯方式：解釋器先將字節(jié)編譯成機器碼，然后再執(zhí)行該機器碼。

2)解釋執(zhí)行方式：解釋器通過每次解釋并執(zhí)行一小段代碼來完成java字節(jié)碼程序的所

有操作。

4.根據(jù)你對Java的了解，簡述為什么Java程序具有健壯性？

參考答案：

Java的強類型機制、異常處理、廢料的自動收集等是Java程序健壯性的重要保證。

Java的安全檢查機制使得Java更具健壯性。

5.說明面向?qū)ο蟪绦蛟O計與面向過程程序設計的區(qū)別。

參考答案：

所謂面向?qū)ο?，就是基于對象的概念，以對象為中心，類和繼承為構造機制，認識

了解刻畫客觀世界以及開發(fā)出相應的軟件系統(tǒng)。所謂面向?qū)ο蟮某绦蛟O計，就是把面向

對象的思想應用到軟件工程中，并指導開發(fā)維護軟件。對象是由數(shù)據(jù)和容許的操作組成

的封裝體。

傳統(tǒng)的結構化程序設計(StructureProgramming)：通過設計一系列的過程(算法)

求解。算法+數(shù)據(jù)結構=程序，而面向?qū)ο蟮某绦蛟O計：程序由對象組成。

面向過程就是分析出解決問題所需要的步驟，然后用函數(shù)把這些步驟一步一步實

現(xiàn)，使用的時候一個一個依次調(diào)用就可以了。

6.簡述生成函數(shù)的定義

參考答案：

生成函數(shù)(也叫“母函數(shù)"，generatingfunction)構造這么--個多項式函數(shù)g(x),使得x

的〃次方系數(shù)為/(〃)。于是，如果有系數(shù)/⑴=7,/(2)=4,/(3)=16,/(4)=0,

"5)=1,等等，則/函數(shù)的生成函數(shù)8(幻=7丫+4/+16/+/+.這就是生成函數(shù)。

生成函數(shù)可以將某些生成函數(shù)可以化簡為一個很簡單的函數(shù)。也就是說，不一定每個

生成函數(shù)都是用一長串多項式來表示的。

7.解下列遞推關系

x(〃)=x(n-1)+5,n>1

'刈)=0

參考答案：

x(〃)=x(n-1)+5n>1,x(l)=0

x(n)=x(n-1)+5

二口(〃-2)+5]+5=%(〃-2)+5?2

—[x(n—3)+5]+5?2=x(/?—3)+5?3

—???

=x(n_i)+5?i

=???

=x(l)+5-(n-l)=5(n-l)

x(〃)=3x(〃-1),?>1

,x(l)=4

參考答案：

x(/7)=3x(〃-1)n>1,x(l)=4

x(n)-3[3x(〃-2)]=32x(n-2)

=32[3x(?-3)]=33x(n-2)

=???

=yx(n-i)

=???

=3f(l)=43i

8.對于計算n!的遞歸算法F(n),建立其遞歸調(diào)用次數(shù)的遞推關系并求解。

參考答案：

C(n)=C(〃—1)+1=[C(n—2)+1]+1=-2)+2=…

=C(n—z)+z=???=C(0)+〃=1+〃

第3章

遞歸與分治

Q?思考與練習I

1.簡述分治法的思想，并給出遞歸與分治的區(qū)別與聯(lián)系

參考答案：

將n個輸入分成k個不同子集合，得到k個不同的可獨立求解的子問題，其中ivkWn,而

且子問題與原問題性質(zhì)相同，原問題的解可山這些子問題的解合并得出。

2.編寫計算斐波那契(Fibonacci)數(shù)列的第n項函數(shù)。

參考答案：

publicclassFibonacciPrint{

publicstaticvoidinain(Stringargs[]){

intn=Integer.parseInt(args[O]);

FibonacciPrintt=newFibonacciPrint();

fbr(inti=l;i<=n;i-H-){

t.print(i);

)

}

publicvoidprint(intn){

intnl=1;〃第一個數(shù)

intn2=1;//第二個數(shù)

intsum=0;〃和

if[n<=0){

System.out.println("參數(shù)錯誤!”)；

return;

)

if(n<=2){

sum=1;

}else{

fbr(inti=3;i<=n;i++){

sum=nl+n2;

nl=n2;

n2=sum;

System.out.println(sum);

)

}

3.編寫一個快速排序算法，并分析時間復雜性

參考答案

classQuicksort{

privateint[]data;

QuickSort(int[]data){

this.data=data;

}

publicvoidquickSort(){

recQuickSort(data,0,data.length-1);

}

privatevoidrecQuickSort(int[]data,intlow,inthigh){

〃設置兩個滑標

intlowCursor=low+1;

inthighCursor=high;

〃交換時的臨時變量

inttemp=0;

〃比較樞值,設為數(shù)組的第一個值

intmedi=data[low];

while(true){

〃從低端開始查找，確定大于數(shù)data[low]所在的位置

while(lowCursor<high&&data[lowCursor]<medi){

lowCursor++;

}

〃從高端開始查找，確定小于數(shù)data[lowj所在的位置。這里要使用>=判斷確定小于

值

whilc(highCursor>low&&data[highCursor]>=medi){

highCursor—;

)

〃兩游標位置出現(xiàn)越界，退出循環(huán)

lowCursor>=highCursor){

break;

}

〃交換data[highCursor]和data[lowCursor]位置數(shù)據(jù)

temp=data[highCursor];

data[highCursor]=data[lowCursor];

data[lowCursor]=temp;

}

〃由while循環(huán)退出條件可知：lowCursor>highCursor

//當前l(fā)owCursor指向右側大于data[low]的第個位置；

〃而highCursor指向左側小于data[low]的第一個位置,所以需要交換dataflow]和

data[highCursor]的值

dataflow]=data[highCursor];

data[highCursor]=medi;

〃遞歸運算左半部分

if(low<highCursor){

recQuickSort(data,low,highCursor);

)

〃遞歸運算右半部分

if(lowCursor<high){

recQuickSort(data,lowCursor,high);

)

}

publicvoiddisplay(){

fbr(inti=0;i<data.length;i++){

System.out.print(data[i]+”

)

System.out.println();

}

publicstaticvoidmain(String[]args){

int[]data=newint[]{43,12,32,55,33,67,54,65,43,22,66,98,74};

Quicksortsort=newQuickSort(data);

sort.display();

sort.quickSort();

sort.display();

)

}

4.使用程序?qū)懗龇种畏ㄒ话惴椒ǖ倪f歸過程。

參考答案：

算法：

DanC(p,q)

globaln,A[l:n];integerm,p,q;//l<p<q<n

ifSmall(p,q)thenreturnG(p,q);

elsem=Divide(p,q);//p<m<q

returnCombine(DanC(p,m),DanC(m+1,q));

endif

endDanC

5.請基于公式2n=2n-l+2n-l,設計一個遞歸算法，當n是任意非負整數(shù)的時候，該算

法能夠計算2n的值。建立該算法所做的加法運算次數(shù)的遞推關系并求解。

參考答案：

a.算法power(n)

〃基于公式2n=2n-l+2n-l,計算2n

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

〃輸出：2n的值

Ifn=0return1

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

6.試用分治法實現(xiàn)有重復元素的排列問題：設R={八，々,…，乙}是要進行排列的〃個

元素，其中元素八，弓，…/“可能相同，試計算R的所有不同排列。

參考答案：

Template<classType>

voidPerm(Typelist[],intk,intm)

{

if(k==m){

fbr(inti=0;i<=m;i++)cout?list[i];

cout?endl;

)

elsefbr(inti=k;iv=m;i")

if(ok(list,k,i)){

swap(list[k],list[i]);

Perm(list,k+l,m);

swap(list[k],list[i]);};

)

其中ok用于判別重復元素。

Tempiate<class>

intok(TypeIist[],intk,inti)

{

if(i>k)

fbr(intt=k;t<I;t++)

if(list[t]==list[i])return0;

return1;

7.試用分治法對一個有序表實現(xiàn)二分搜索算法。

參考答案：

Template<class>

intBinarySearch(Typca[],constType&x,intn)

{〃假定數(shù)組a口已按非遞減有序排列，本算法找到x后返回其在數(shù)組a口中的位置，〃否則返

回-1

intleft=O,right=n-l;

while(left<=right){

intmiddle=(left+right)/2;

ifi[x==a[middle])returnmiddle+1;

if(x>a[middle])left=middle+l;

elseright=middle-l;

return-1;

第4章

動態(tài)規(guī)劃

1.簡述動態(tài)規(guī)劃的基本思想和問題的基本要素。

參考答案：

動態(tài)規(guī)劃所研究的對象是多階段決策問題。所謂多階段決策問題是指一類活動過程，它可以

分為若干個互相聯(lián)系的階段，在每個階段都需要做出決策。這個決策不僅決定這一階段的效

益，而且決定下一階段的初始狀態(tài)。每個階段的決策確定以后，就得到一個決策序列，稱為

策略。多階段決策問題就是求一個策略，使各階段的效益和達到最優(yōu)。

?個多階段決策過程最優(yōu)化問題的動態(tài)規(guī)劃模型通常包含以下要素：

(1)階段

(2)狀態(tài)

(3)決策

(4)策略

(5)狀態(tài)轉移方程

(6)指標函數(shù)和最優(yōu)值函數(shù)

(7)最優(yōu)策略和最優(yōu)軌線

2.試用動態(tài)規(guī)劃算法實現(xiàn)最大子矩陣和問題：求加x〃矩陣A的一個子矩陣，使其各

元素之各為最大。

參考答案：

intMaxSum2(intm,intn,int**a)

{

intsum=O,i,j,k;

intb[105];

for(i=0;i<m;i++)

{

for(k=0;k<n;k++)

{

b[k]=0;

forG=i;j<m;j++)

for(k=0;k<n;k++)

b[k]+=aO][k];

)

intmx=MaxSum(n,b);

if(sum<mx)sum=mx;

)

)

returnsum;

)

〃最大m子段和問題

doubleb[50005];

doublec[50005];

intMaxSum3(intm,intn,int*a)

{

inti,j,k,mx,sum;

b[0]=0;

c[0]=0;

for(i=1;i<=m;i++)

{

b[i]=b[i-1]+arr[i];

c[i-1]=b[i];

mx=b[i];

for(j=i+1；j<=i+n-m;j++)

{

b[j]=bD-1]>c0-1]?b0-1]+arr[j]:cO-1]+arrO];

c0-1]=mx;

if(mx<b[j])

{

mx=bO]；

)

)

c[i+n-m]=mx;

)

sum=b[m];

for(k=m+1;k<=n;k++)

(

if(sum<b[k])sum=b[k];

returnsum;

3.動態(tài)規(guī)劃和分治法在分解子問題方面的不同點是什么？

參考答案：

分治算法會重復的求解公共子問題，會做許多不必要的工作，而動態(tài)規(guī)劃對每個子問題之求

解一次，將其結果存入?張表中，從而避免了每次遇到各個子問題有從新求解。前者分解出

的子問題有重疊的，而后者分解出的子問題是相互獨立(不重疊)的。

4.考慮下面的整數(shù)線性規(guī)劃問題：

maxEc/j

“/=，為為非負整數(shù)，14三〃。

Z=1

試設計一個解此問題的動態(tài)規(guī)劃算法，并分析算法的計算復雜性。

參考答案：

此線性規(guī)劃問題是求解目標函數(shù)最大的問題，X：為非負整數(shù)，在這個問題可以用整數(shù)

規(guī)劃模型來描述。

這個問題可以建立動態(tài)規(guī)劃模型

(1)階段k

(2)狀態(tài)

(3)決策”

(4)策略允許集合

(5)狀態(tài)轉移方程x*+|=x&-%叁

(6)指標函數(shù)階段指標：匕=94；

遞推方程：fk(x*)=max(ckdk+fk+](x,+1)｝=max[ckdk+fk+l(xk

(7)終止條件：fg=O。

對備+i(Xn+i)初始化;

｛邊界條件｝

fork:=ndownto1do

for每一個Xk^Xkdo

for每一個Uk《Uk(Xk)dobegin

&(Xk尸一個極值；｛CO或一8｝

xk+i=Tk(xk,uk);｛狀態(tài)轉移方程｝

t:=(p(fk+1(xk+i),vk(xk,uk));｛基本方程(9)式｝

ift比fL(Xk)更優(yōu)then￡描):=匕｛計算-x。的最優(yōu)值｝end;

t=一個極值；{8或一8}

for每一個X,eXido

iffi(xD比t更優(yōu)thent:=fi(xi);{按照10式求出最優(yōu)指標}

輸出t;

5.設有資源。，分配給〃個項目，g,(x)為第，個項目分得資源x所得到的利潤。求

總利潤最大的資源分配方案，也就是解下列H題：

maxz=gi(x)+g2(x)+~+g“(x)

xy+x2-\—xn-a,Xj>0,i-

函數(shù)g,(x)以數(shù)據(jù)表的形式給出：

現(xiàn)有7萬元投資到A,B,C三個項目，利潤如下表，求問題總利潤最大的資源

分配方案。

1234567

A0.110.130.150.210.240.30.35

B0.120.160.210.230.240.240.34

C0.080.120.20.240.260.30.45

參考答案：

設fk(?)為資源〃分配給前上個項目所得的最大利潤。

力(a)=maxg|(x)

&⑷=max{g2(x)+/,(￡/-x)

f(a)=max{^(x)+f{a-x)

3ow32

Z.3)=max{g?(x)+/?,1(a-x)}

1.考慮投入產(chǎn)品A或C的生產(chǎn)資金a與利潤力(a)的關系，如上表第二行。

2.考慮投到A,B兩種產(chǎn)品的生產(chǎn)，資金a與利潤力伍)關系如下，其中/為投

到產(chǎn)品B的生產(chǎn)資金。

f2(?)=max{g2(x2)+fi(a-x2)}

其利潤見下表，其中*表示利潤最大的狀態(tài)。

人⑷=max{^3(x3)-72(x3)}

\

力(。)投入a

01234567

所獲最大利潤

10.110.12*0.12

0.11+0.12

20.130.160.23

=0.23*

0.13+0.120.11+0.16

30.150.210.27

=0.25=0.27*

0.15+0.120.13+0.160.114-0.21

40.210.230.32

=0.27=0.29=0.32*

0.21+0.120.15+0.160.13+0.210.11+0.23

50.240.240.34

=0.33=0.31=0.34=0.34*

0.24+0.120.21+0.160.15+0.210.13+0.230.11+0.24

60.30.240.37

=0.36=0.37*=0.36=0.36=0.35

0.3+0.120.3+0.160.21+0.210.15+0.230.13+0.240.11+0.24

70.350.340.47

=0.32=0.47*=0.42=0.38=0.37=0.35

考慮投入7萬元資金用于三種產(chǎn)品A,B,C的生產(chǎn)，利潤與資金關系如下:

/3(7)=max{g3(x3)+/2(7-x3))

0/3?7

其中x3為投入到產(chǎn)品C的生產(chǎn)資金。利潤表如下。

01234567

g3(X)0.000.080.120.20.240.260.30.45

0.470.370.340.320.270.230.120.00

/2(7-X)

g3(X)+/2(7-X)0.470.450.460.520.510.490.420.45

所以力(7)=0.52

第5章

貪心算法

思考與練習

i.簡述貪心算法的定義和基本思想

參考答案：

用局部解構造全局解，即從問題的某一個初始解逐步逼近給定的目標，以盡可能快地求

得更好的解。當某個算法中的某一步不能再繼續(xù)前進時，算法停止。貪心算法思想的本質(zhì)就

是分治，或者說：分治是貪心的基礎。每次都形成局部最優(yōu)解，換?種方法說，就是每次都

處理出一個最好的方案。

2.簡述貪心算法的最優(yōu)子結構性質(zhì)。

參考答案：

當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結構性質(zhì)。運用貪心策

略在每一次轉化時都取得了最優(yōu)解。問題的最優(yōu)子結構性質(zhì)是該問題可用貪心算法或動態(tài)規(guī)

劃算法求解的關鍵特征。貪心算法的每一次操作都對結果產(chǎn)生直接影響,而動態(tài)規(guī)劃則不是。

貪心算法對每個子問題的解決方案都做出選擇，不能回退；動態(tài)規(guī)劃則會根據(jù)以前的選擇結

果對當前進行選擇，有回退功能。動態(tài)規(guī)劃主要運用于二維或三維問題，而貪心一般是一維

問題。

3.試舉例說明貪心算法對有的問題是有效的，而對一些問題是無效的。

參考答案：

貪心算有效性：最小生成樹、哈弗曼、活動安排、單元最短路徑。

無效反例：0——1背包問題，無向圖找最短路徑問題。

4.有一個背包，背包容量是M=150。有7個物品，物品可以分割成任意大小。要求盡

可能讓裝入背包中的物品總價值最大，但不能超過總容量。

物品ABCDEFG

重量wi35306050401025

價值pi10403050354030

要求按照下面要求建立H標函數(shù):背包內(nèi)物品總價值最大和裝入的物品總重量不超過背包容

量。

（1）根據(jù)貪心的策略，每次挑選價值最大的物品裝入背包，得到的結果是否最優(yōu)？

（2）每次挑選所占重量最小的物品裝入是否能得到最優(yōu)解？

（3）每次選取單位重量價值最大的物品，成為解本題的策略？

參考答案：

值得注意的是，貪心算法并不是完全不可以使用，貪心策略一旦經(jīng)過證明成立后，它就是一

種高效的算法。

貪心算法還是很常見的算法之一，這是由于它簡單易行，構造貪心策略不是很困難。

可惜的是，它需要證明后才能真正運用到題目的算法中。

一般來說，貪心算法的證明圍繞著：整個問題的最優(yōu)解一定由在貪心策略中存在的子問題的

最優(yōu)解得來的。

對于例題中的3種貪心策略，都是無法成立（無法被證明）的，解釋如下：

（1）貪心策略：選取價值最大者。反例：

W=30

物品：ABC

重量：281212

價值：302020

根據(jù)策略，首先選取物品A,接下來就無法再選取了，可是，選取B、C則更好。

（2）貪心策略：選取重量最小。它的反例與第一種策略的反例差不多。

（3）貪心策略：選取單位重量價值最大的物品。反例：

W=30

物品：ABC

重量：282010

價值：282010

根據(jù)策略，三種物品單位重量價值一樣，程序無法依據(jù)現(xiàn)有策略作出判斷，如果選擇A,則

參考答案錯誤。

所以需要說明的是，貪心算法可以與隨機化算法一起使用，具體的例子就不再多舉了。（因

為這一類算法普及性不高，而且技術含量是非常高的，需要通過些反例確定隨機的對象是

什么，隨機程度如何，但也是不能保證完全正確，只能是極大的幾率正確）

5.簡述prim算法，并使用prim算法構造出如下圖G的一棵最小生成樹。

dist(l,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6.4)=2;dist(4,1)=5;

dist(l,3)=l;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6

參考答案：

使用普里姆算法構造出如下圖G的一棵最小生成樹。

dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5;

dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6

6.假設要在m個會場里安排一批活動，并希望使用盡可能多地安排活動。設計一個

有效的貪心算法進行安排。

參考答案：

這個問題和圖的著色問題類似，可以參考下面算法寫法

Algorithmgreedy(s,f,m,n);

Inputs[l:n],f[l:n];

Outputx[l:m,l:n];

Begin

對數(shù)組s和f中的2n個元素排序存入數(shù)組y[l:2n]中；

空閑棧清空；d數(shù)組所有元素置初值0；

Fori=lto2ndo

Begin

If元素y[i]原屬于sthen

If空閑棧不空then

取出棧頂場地j;d[j]=d[j]+l;y[i]存入x[j,d[j]];

If元素y[i]原屬于fthen

設其相應的s存于x[j,k]中，將j存入空閑棧中;

End

Fori=1tomdo

Forj=ltod[j]do

Outputx[i,j];

End

7.試用貪心算法求解下列問題：將正整數(shù)n分解為若干個互不相同的自然數(shù)之和，使

這些自然數(shù)的乘積最大。

參考答案：

voiddicomp(intn,inta[])

(

k=l;

if(n<3){a[l]=0;retum;};

if(n<5){a[k]=l;a[++k]=n-l;return;};

a[l]=2;n-=2;

while(n>a[k]){

k++;

a[k]=a[k-l]+l;

n-=a[k];

}；

if(n==a[k]){a[k]++;n-;)；

for(inti=0;i<n;i++)a[k-i]++;

第6章

回溯法

o思考與練習

1.簡述回溯法的定義。

參考答案：

回溯法的基木做法是試探搜索，是一種組織得井井有條的、能避免一些不必要搜索的窮舉式

搜索法?；厮莘ㄔ趩栴}的解空間樹中，從根結點出發(fā)搜索解空間樹，搜索至解空間樹的任意

一點，先判斷該結點是否包含問題的解；如果肯定不包含，則跳過對該結點為根的子樹的搜

索，逐層向其父結點回溯；否則，進入該子樹，繼續(xù)搜索

2.筒述回溯法的解空間和算法框架。

參考答案：

用回溯法解問題時，首先應明確定義問題的解空間。問題的解空間應至少包含問題

的?個(最優(yōu))解。問題的解向量：回溯法希望一個問題的解能夠表示成一個〃元式

(七，與,…X“)的形式。

顯約束:對分量X,的取值限定。

隱約束:為滿足問題的解而對不同分量之間添加的約束。

解空間:對于問題的一個實例，解向量滿足顯式約束條件的所有多元組，構成了

該實例的解空間。

算法框架

回溯法解題通?？梢詮囊韵氯饺胧郑?/p>

1)針對?所給問題，定義問題的解空間；

2)確定易于搜索的解空間結構；

3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。

用回溯法搜索子集合樹的一般框架：

publicstaticvoidbacktrack(intt){

if(t>n)output(x);

else{

fbr(inti=f(n,t);i<=g(n,t);i++){

x[t]=h(i);

if(constraint(t)&&bound(t))backtrack(t+1);

}

}

}

用回溯法搜索排列樹的算法框架：

publicstaticvoidbacktrack(intt){

if^t>n)output(x);

else(

for(inti=f(n,t);i<=g(n,t);i-H-){

swap(x[t],x[i]);

if(constraint(t)&&bound(t))backtrack(t+l);

swap(x[t],x[i]);

}

}

}

3.詳細敘述使用回溯法解決0-1背包問題的過程和步驟。

參考答案：

第一步:確定解空間：裝入哪幾種物品

第二步:確定易于搜索的解空間結構：可以用數(shù)組p,卬分別表示各個物品價值和重量。

用數(shù)組x記錄，是否選種物品

第三步:以深度優(yōu)先的方式搜索解空間，并在搜索的過程中剪枝

4.中國象棋的半個棋盤如圖所示，馬自左下角往右上角跳。規(guī)定只許向右跳，不許向

左跳，計算所有的行走路線。

參考答案：

Algorithmchess

Begin

top=0;y0=0;x0=0;di=l;r=0;

push;

repeat

pop;

whiledi<=4do

begin

g=x0+x[di];h=yO+y[di];

if(g=8)and(h=4)thenout

elsebegindi=di+l；push;xO=g;yO=h;di=lend

end

untilempty

end

algorithmpush

begin

top=top+l；sx[top]=xO;sy[top]=yO;d[top]=di;

end

algorithmpop

begin

xO=sx[top];yO=sy[top];di=d[top];top=top—1；

end

5.寫出圖著色問題的回溯算法的判斷x[k]是否合理的過程。

參考答案：

inti=0

whilei<kdo

ifG[k,i]=landX[k]=X[i]then

returnfalse

i=i+l

repeat

ifi=kthenreturntrue

6.用遞歸函數(shù)設計一個解n后問題的回溯算法。

參考答案：

classQueen

{

friendintnQueen(int)

private:

boolPlace(intk);

voidBacktrack(intt);

intn,〃皇后個數(shù)

*n;〃當前解

longsum;〃當前已找到的可行方案數(shù)

}；

boolQueen::Place(intk)

{

for(intj=l;j<k;j++)

if((abs(H)=abs(x[j]-x[k]))||(x[j]=x[k]))returnfalse;

returntrue;

voidQueen::Backtrack(intt)

(

if(t>n)sum++;〃達到葉結點

else

fbr(inti=l;i<=n;i++){〃搜索子結點

x[t]=i;〃進入第i個子結點

if(Place(t))Backtrack(t+1);

}

}

intnQueen(intn)

(

QueenX;

//初始化X

X.n=n;

X.sum=0;

int*p=newint[n+1];

for(inti=0;i<=n;i-H-)

p[i]=0；

X.x=p;

X.Backtrack(l);〃對整個解空間回溯搜索

delete[]p;

returnX.sum;

7.給定背包的載重量M=20,有6個物體，價值分別為11,8,15,18,12,6,重量

分別為5,3,2,10,4,2o說明用回溯法求解上述0/1背包問題的過程。畫出搜索樹,

結點按照生成順序編號，并在節(jié)點旁邊標出生成該結點時所執(zhí)行動作的結果。

參考答案：

把物體按價值重量比進行排序

V1561281118

w2243510

標注1表示裝入，標注0表示不裝入，如圖最后得到的最大價值是53

按照順序分別裝入(2,,15)(4,12)(3,8)(10,18)四件物體。

Max12,40

Max13,44

第7章

分支限界法

思考與練習?

i.常見的兩種分支限界法是什么？

參考答案：

隊列式(FIFO)分支限界法與優(yōu)先隊列式分支限界法:

2.用分支限界法解裝載問題時，對算法進行了一些改進，下面的程序段給出了改進部

分；試說明斜線部分完成什么功能，以及這樣做的原因，即采用這樣的方式，算法

在執(zhí)行上有什么不同。

//檢查左兒子結點

Typewt=Ew+w[i];//左兒子結點的重量

if(wt<=c){//可行結點

if(wt>bestw)bestw=wt;

II加入活結點隊列

if(i<n)Q.Add(wt);

)

//檢查右兒子結點

if(Ew+r>bestw&&i<n)

Q.Add(Ew);〃可能含最優(yōu)解

Q.Delete(Ew);〃取下一擴展結點

參考答案：

斜線標識的部分完成的功能為：提前更新bestw值；

這樣做可以盡早的進行對右子樹的剪枝。具體為：算法Maxloading初始時將bestw設置為0,

直到搜索到第一個葉結點時才更新bestw。因此在算法搜索到第一個葉子結點之前，總有

bestw=0,r>0故Ew+r>bestw總是成立。也就是說，此時右子樹測試不起作用。

為了使上述右子樹測試盡早生效，應提早更新bestw。又知算法最終找到的最優(yōu)值是所求問

題的子集樹中所有可行結點相應重量的最大值。而結點所相應得重量僅在搜索進入左子樹是

增加，因此，可以在算法每一次進入左子樹時更新bestw的值。

3.最小代價搜索（LC檢索）的基本思想。

參考答案：

一開始，根結點入棧；

從棧中彈出一個結點為當前擴展結點；

對當前擴展結點，先從左到右地產(chǎn)生它的所有兒子，用約束條件檢查，把所有滿足約束

函數(shù)的兒子入棧；

再從棧中彈出一個結點（棧中最后進來的結點）為當前擴展結點......直到找到一個

解或棧為空為止。

4.分枝一限界算法的上界函數(shù)的作用是什么？

參考答案：

上界函數(shù)U表示問題可以找到代價不超U的解，如果活節(jié)點X的最小代價的下界：（X）〉U,

則說明搜索以X為根的子樹找到的最小代價的解?定U,所以設置最小成本的上界U使算

法進一步加速。如果u是最小成本解的成本上界，則具有

5.分支限界法在問題的解空間樹中，什么策略是從根結點出發(fā)搜索解空間樹？

參考答案：

分支限界法在解空間樹中，按深度優(yōu)先策略，從根結點出發(fā)搜索解空間樹.

6.對0-1背包問題分別使用分支限界法和回溯法進行解決，并說明兩種方法的差別。

參考答案：

分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹在

分支限界法中，每一個活結點只有一次機會成為擴展結點。活結點一旦成為擴展結點，就一

次性產(chǎn)生其所有兒子結點。在這些兒子結點中，導致不可行解或?qū)е路亲顑?yōu)解的兒子結點被

舍棄，其余兒子結點被加入活結點表中。此后，從活結點表中取下一結點成為當前擴展結點,

并重復上述結點擴展過程。這個過程一直持續(xù)到找到所需的解或活結點表為空時為止。

回溯法它有兩種可能的樹結構，一種對應于元組大小固定的表示；另一種對應于元組大

小可變的表示。用其中任一種樹結構都可導出背包問題的回溯算法。

在選擇限界函數(shù)上，有一條必須遵循的基本原則，即無論使用哪種限界函數(shù)，都應有助

于殺死某些活結點，使這些活結點實際上不再擴展。背包問題的一個好的限界函數(shù)可以設計

成能產(chǎn)生某些值的上界的函數(shù)。如果擴展給定活結點和它的任一子孫結點所導致最好可行解

值的上界不大于迄今所確定的最好解之值，就可殺死此活結點。

6.有如下0/1背包問題，畫出它們的搜索樹，在結點旁邊標出相應的上界；寫出最后

的最優(yōu)解，及相應的最大價值。

(1)M=20,p={11,8,15,18,12,6},w={5,3,2,10,4,2}

(2>=12,p={10,12,6,8,4},vv={4,6,3,4,2}

(3)M=15,p={6,7,8,3,l},w={5,7,10,5,2)

參考答案：

按照物體價值重量比的遞減順序排序如下

PWP/W

1527.5

623

832.666667

1252.4

1152.2

18101.8

由題意，背包的裝載價值上限為ub=20*7.5=150

分支限界法首先確定一個合理的限界函數(shù)，并根據(jù)限界函數(shù)確定目標函數(shù)的界［而町up］。

然后，按照廣度優(yōu)先策略遍歷問題的解空間樹，在分支結點上，依次搜索該結點的所有孩子

結點，分別估算這些孩子結點的目標函數(shù)的可能取值，如果某孩子結點的目標函數(shù)可能取得

的值超出目標函數(shù)的界，則將其丟棄，因為從這個結點生成的解不會比目前己經(jīng)得到的解更

好；否則，將其加入待處理結點表(以下簡稱表PT)中。依次從表PT中選取使目標函數(shù)的

值取得極值的結點成為當前擴展結點，重復上述過程，直到找到最優(yōu)解.求解從略。結果是

最大價值是53分別裝入(15,2)(8,3)(12,5)(18,10)o

第8章線性規(guī)劃與網(wǎng)絡流問題

Q

1.寫出單純形算法的偽代碼。

參考答案：

步驟1：選入基變量。

如果所有“wo,則當前基本可行解為最優(yōu)解，計算結束。

否則取q>0相應的非基本變量4為入基變量。

步驟2：選離基變量。

對于步驟1選出的入基變量血,如果所有40,則最優(yōu)解無界，計算結束。

否則計算

0=min<

選取基本變量4為離基變量。

新的基本變量下標集為B=B+{e}-{k}

新的非基本變量下標集為N=N+{k}-{e}

步驟3：作轉軸變換。

新單純形表中各元素變換如下。

bi=bt—aje——iwB

ake

ciij=4-aje—ieB,jwN

jGN

步驟4：轉步驟1。

2.求解下面的線性規(guī)劃問題

max/=12xj+14x24-8x3

l.lX]+1.2X2+1.4X3<4600

0.5x,+0.6工2+0.6芻-2100

s.tA

0.7x1+0.812+0.6