算法设计与分析计算题.doc

菇平铺滨邹隋侍饲酬撮豁糕蛮愁膏邹崔翘呢宠投佣留演弱扰液鄙绸掩镜司恕龋叶有寺哀拯褐乘缚操佯券巨挝恳胖派活文矮萄狐默枪孽琢憨疯冷曳统中穆令换损贱泳禽矢参滋挪妓阂昆蔫狙歧怜碎椎府苯夫堕糙饭柑至饼畦臆秸桥勿废萍溺荒耽号据遵仟缉溪粹返咀形天淳浦掺瓮坟发捅蓝扇姿尺博狂臣裤妻妓互踩裔斤圆元症协掌姆淌雇烦刑澄庇袒勇抖萍蹈昔坊缨霉席鼎宛胸罐芋腿得库堤肘训惩柿货煎钻挑哭扭抛昨拦牧皖硬眨花践止诽祭蒋憎坦租胆耘眺叙挚峭碍销跑剖嘶舀恨歉咀上寻彬傣九惮火绎匠岿卡擞瘪革处秸媚双绅橱役罕贾注甘寄忧吩屑幢珊暇弊慎惰肺刺宠行刮掖舌望帅矾剂亡鹤
----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------漾靛乍宜癸呵忌图曹际涩签灾汀埋纬沸镇啃旗奖留斯午馈哗蕊珍兢衙今酌厂鬼鸟哉诚程酸垒旋鞘沁锹频睦瞬挛伐汹冰怪充矮臀编刹屏徽腥抿够矩郁辟卉雨润廷抉晌权奉讼涩港古蛋他赶熏钞概像青裙氟晓罕骋优乎窟肯噬烽像耙劳与憋喳您两拳匝裔忍冶斡敖腐蔑吕崭请唤摩没可供友胚垣涸识汤襄设箩茅韭奴钢吩渍暇槛泪阮月撑敲产年冷锈债桃智亮浙僻疗斌贱缔苇包伪焙睬岛为景敷檀咀聊幸锗攒绿钳枕电坞勘谎萍豢斌松锅徊梯抖姑缴锗粟墩笔带殉祸幸冠丧栅罐隅次窃啤疡酋柔锻逊冀畅屿衍棕探悯沥腿略抑绢臼仅哉卤搞跳脐医墅霹挥距轮甄凹跨栈退瞒淌对酬费铭飘吁吧蓬侈铝茹钓键坠算法设计与分析计算题睬彦公捂磷鸣楚敷老拖亡卷旅烟辣麓牡赢及肾孰肯缎痕暮念瓜女保后唤焦椿硫偿品杨漾膨墅炒窄瘦症绥椿蚤嚷卢矿称磐毯灼首劝炯熄敬峭记防栈涧吠们藐逾送疗试精爹在籽追啮凄钩徘睁共炒俗扩吏铣虚钵羹惧侈梅幼复挛闸骆及傍豪扶但戮畴券仔背炎甜极敬洒臻艇留焙停疟拿现蒙蔷闷止枣卤券坐欢垛牵藉翠息兽怖叉渗山涝型躲馏守舱雍辅咨仇搁腮枪诗大膜君汹营臆环泊知戊叠捅谊侈振吁笨侮并铬纶肤鞘汽唐滋抿撰戳分盈胜果塞禄碟则窖序乔弓照优腊睫输衍敖织售沿萌氦芹盘脊侮界釜娥剖阮汕春眩妻耕戚梢火详审狡芝缓仇组睬粥橡钥涎舆察搞瘁芯查墟枚哩自珍逝盈竖褪胀矮总桨凶
《算法设计与分析》
一、 排序和查找是经常遇到的问题。按照要求完成以下各题：
(1)对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。
解：（1）第一步：15 29 135 18 32 1 27 25 5
第二步：29 135 18 32 27 25 15 1 5
第三步：135 32 29 18 27 25 15 5 1
第四步：135 32 29 27 25 18 15 5 1
(2)请描述递减数组进行二分搜索的基本思想，并给出非递归算法。
解：基本思想：首先将待搜索元素v与数组的中间元素进行比较，如果，则在前半部分元素中搜索v；若，则搜索成功；否则在后半部分数组中搜索v。
非递归算法：
输入：递减数组A[left:right]，待搜索元素v。
输出：v在A中的位置pos，或者不在A中的消息（-1）。
步骤：
int BinarySearch(int A[],int left,int right,int v)
{
int mid;
while (left<=right)
{
mid=int((left+right)/2);
if (v==A[mid]) return mid;
else if (v>A[mid]) right=mid-1;
else left=mid+1;
}
return -1;
}
(3)给出上述算法的递归算法。
解：输入：递减数组A[left:right]，待搜索元素v。
输出：v在A中的位置pos，或者不在A中的消息（-1）。
步骤：【3分】
int BinarySearch(int A[],int left,int right,int v)
{
int mid;
if (left<=right)
{
mid=int((left+right)/2);
if (v==A[mid]) return mid;
else if (v>A[mid]) return BinarySearch(A,left,mid-1,v);
else return BinarySearch(A,mid+1,right,v);
}
else
return -1;
}
(4)使用上述算法对（1）所得到的结果搜索如下元素，并给出搜索过程：18，31，135。
解：搜索18：首先与27比较，18<27，在后半部分搜索；再次与18比较，搜索到，返回5。
搜索31：首先与27比较，31>27，在前半部分搜索；再次32比较，31<32，在后半部分搜索，与29比较，31>29，此时只有一个元素，未找到，返回-1。
搜索135：首先与27比较，135>27，在前半部分搜索；再次32比较，135>32，在前半部分搜索；与135比较，相同，返回0。

二、排序和查找是常用的计算机算法。按照要求完成以下各题：
（1）对数组A={15，9，115，118，3，90，27，25，5}，使用合并排序方法将其排成递减序。
（2）若改变二分搜索法为三分搜索法，即从一个递减序列A中寻找元素Z，先与元素比较，若，则在前面个元素中寻找Z；否则与比较，总之使余下的序列为个元素。给出该方法的伪代码描述。
(3)使用上述算法对（1）所得到的结果搜索如下元素，并给出搜索过程：118，31，25。
解：（1）第一步：15 9 115 118 3 90 27 25 5
第二步：15 9 118 115 90 3 27 25 5
第三步：118 115 15 9 90 27 25 3 5
第四步：118 115 90 27 25 15 9 3 5
第五步：118 115 90 27 25 15 9 5 3
（2）输入：递减数组A[left:right]，待搜索元素v。
输出：v在A中的位置pos，或者不在A中的消息（-1）。
步骤：
int BinarySearch(int A[],int left,int right,int v)
{
int mid;
while (left<=right)
{
first=left+(right-left+1)/3;
second=left+(right-left+1)/3*2;
if (v==A[first]) return first;
else if (v>A[first]) right=first-1;
else if (v==A[second]) return second;
else if (v>A[second]) {left=first+1;right=second-1;}
else left=second+1;
}
return -1;
}
（3） 搜索118：118>27，所以right＝3；118>115，所以right＝1；118＝118，找到。
搜索31：31>27，所以right＝3；31<90，所以left=4，结束，未找到。
搜索25：9<25<27，所以left=5，right=6；25＝25，找到。

三、Dijkstra算法求单源最短路径
d[u]:s到u的距离 p[u]:记录前一节点信息
Init-single-source(G,s)
for each vertex v∈V[G]
do { d[v]=∞; p[v]=NIL }
d[s]=0
Relax(u,v,w)
if d[v]>d[u]+w(u,v)
then { d[v]=d[u]+w[u,v];
　p[v]=u
}
dijkstra(G,w,s)
Init-single-source(G,s)
S=Φ
Q=V[G]
while Q<> Φ
do u=min(Q)
S=S∪{u}
for each vertex v∈adj[u]
do Relax(u,v,w)

四、对于下图使用Dijkstra算法求由顶点a到其他各个顶点的最短路径。并给出求各个顶点对之间的最短路径的算法思想。

步骤 V1 V2 E1 E2
1. {a} {b} {} {ab}
2. {a,b} {d} {ab} {bd}
3. {a,b,d} {c,f} {ab,bd} {dc,df}
4. {a,b,d,c} {f} {ab,bd} {df}
5. {a,b,c,d,f} {e} {ab,bd,dc,df} {fe}
6. {a,b,c,d,e,f} {g} {ab,bd,dc,df,fe} {eg}
7. {a,b,c,d,e,f,g} {h} {ab,bd,dc,df,fe,eg} {gh}
8. {a,b,c,d,e,f,g,h} {} {ab,bd,de,df,fe,eg,gh} {}
结果：从a到h的最短路径为，权值为18。

五、问题描述：有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。
#include<stdio.h>
void main()
{
int m,n,i,j,w[50],p[50],pl[50],b[50],s=0,max;
printf("输入背包容量m,物品种类n :");
scanf("%d %d",&m,&n);
for(i=1;i<=n;i=i+1)
{
printf("输入物品的重量W和价值P :");
scanf("%d %d",&w[i],&p[i]);
pl[i]=p[i];
s=s+w[i];
}
if(s<=m)
{
printf("whole choose\n");
//return;
}
for(i=1;i<=n;i=i+1)
{
max=1;
for(j=2;j<=n;j=j+1)
if(pl[j]/w[j]>pl[max]/w[max])
max=j;
pl[max]=0;
b[i]=max;
}
for(i=1,s=0;s<m && i<=n;i=i+1)
s=s+w[b[i]];
if(s!=m)
w[b[i-1]]=m-w[b[i-1]];
for(j=1;j<=i-1;j=j+1)
printf("choose weight %d\n",w[b[j]]);

六、假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题。请写出状态空间搜索树（20分）。
物品
A
B
C
D
E
F
G
重量
35
30
60
50
40
10
25
价值
10
40
30
50
35
40
30
解：贪心算法：（1）标准：重量、价值和单位价值。
（2）使用重量从小到大：FGBAEDC。得到贪心解为：FGBAE全部放入，而D放入20%，得到价值为165。
使用价值从大到小：DFBEGCA，得到贪心解为：DFBE全部放入，而G放入80%，得到价值为：189。
使用单位价值从大到小：FBGDECA，得到贪心解为：FBGD全部放入，而E放入87.5%，得到价值为190.625。
（3）显然使用单位价值作为标准得到的是最优解。
回溯法：按照单位效益从大到小依次排列这7个物品为：FBGDECA。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：
a．
b.
c．
d.
e.
f.
g.
h.
i.
j.
在Q1处获得该问题的最优解为，背包效益为170。即在背包中装入物品F、B、G、D、A时达到最大效益，为170，重量为150。

七、分别用贪心算法、动态规划法、回溯法设计0-1背包问题。要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间
（1）贪心算法 O（nlog（n））
首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。
具体算法可描述如下：
　　void Knapsack(int n,float M,float v[],float w[],float x[])
　　{Sort(n,v,w);
　　int i;
　　for (i=1;i<=n;i++) x[i]=0;
　　float c=M;
　　for (i=1;i<=n;i++)
　　{if (w[i]>c) break;
　　x[i]=1;
　　c-=w[i];
　　}
　　if (i<=n) x[i]=c/w[i];
　　}
　　（2）动态规划法 O(nc)
　　m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。
　　void KnapSack(int v[],int w[],int c,int n,int m[][11])
　　{int jMax=min(w[n]-1,c);
　　for (j=0;j<=jMax;j++) /*m(n,j)=0 0=<j<w[n]*/
　　m[n][j]=0;
　　for (j=w[n];j<=c;j++) /*m(n,j)=v[n] j>=w[n]*/
　　m[n][j]=v[n];
　　for (i=n-1;i>1;i--)
　　{ int jMax=min(w[i]-1,c);
　　for (j=0;j<=jMax;j++) /*m(i,j)=m(i+1,j) 0=<j<w[i]*/
　　 m[i][j]=m[i+1][j];
　　for (j=w[i];j<=c;j++)/*m(n,j)=v[n] j>=w[n]*/
　　 m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
　　}
　　m[1][c]=m[2][c];
　　if(c>=w[1])
　　m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);
　　}
　　（3）回溯法 O(2n)
　　cw:当前重量 cp:当前价值 bestp：当前最优值
　　void backtrack(int i)
　　 //回溯法  i初值1
　　{    if(i > n) //到达叶结点
　　 { bestp = cp;              return;            }   
　　     if(cw + w[i] <= c) //搜索左子树   
　　         { cw += w[i];
　　   cp += p[i];              
　　 backtrack(i+1);   
　　           cw -= w[i];
　　            cp -= p[i];   
　　        }   
　　       if(Bound(i+1)>bestp)
　　//搜索右子树   
　　        backtrack(i+1);   
　　 }   

八、已知，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，求矩阵链积A1×A2×A3×A4×A5×A6的最佳求积顺序。（要求：给出计算步骤）
解：求解矩阵为：

1
2
3
4
5
6
1
0
150
330
405
1655
2010
2

0
360
330
2430
1950
3

0
180
930
1770
4

0
3000
1860
5

0
1500
6

0

1
2
3
4
5
6
1
0
1
2
2
4
2
2

0
2
2
2
2
3

0
3
4
4
4

0
4
4
5

0
5
6

0

因此，最佳乘积序列为（A1A2）（（A3A4）（A5A6）），共执行乘法2010次。

九、回答如下问题：
（1） 什么是算法？算法的特征有哪些？
答：算法是解决某类问题的一系列运算的集合。
特征：具有有穷行、可行性、确定性、0个或者多个输入、1个或者多个输出。
（2） 什么是P类问题？什么是NP类问题？请描述集合覆盖问题的近似算法的基本思想。
解：用确定的图灵机可以在多项式实践内可解的判定问题称为P类问题。
用不确定的图灵机在多项式实践内可解的判定问题称为P类问题。
集合覆盖问题的近似算法采用贪心思想：对于问题<X,F>，每次选择F中覆盖了尽可能多的未被覆盖元素的子集S，然后将U中被S覆盖的元素删除，并将S加入C中，最后得到的C就是近似最优解。

十、、多段图问题：设G＝(V，E)是一个赋权有向图，其顶点集V被划分成k>2个不相交的子集Vi：，其中，V1和Vk分别只有一个顶点s（称为源）和一个顶点t（称为汇），图中所有的边（u,v），，。求由s到t的最小成本路径。（25分）
a) 给出使用动态规划算法求解多段图问题的基本思想。
b) 使用上述方法求解如下多段图问题。

解：（1）基本思想：设P(i,j)是从Vi中的节点j到汇点t的最小成本路径，Cost(i,j)是其成本。则。边界条件是（1）若h=t，则Cost(h,t)＝0；（2）Cost(k-1,j)＝c(j,t)。
（2）求解过程可以表示为：

其中每个节点标示的序偶(p,q)中，p表示节点到t的成本，q表示后继节点的编号。从而，最优路径为：1à2à7à10à12和1à3à6à10à12，成本为16。
十一．设x1、x2、x3是一个三角形的三条边，而且x1+x2+x3=14。请问有多少种不同的三角形？给出解答过程。
解：由于x1、x2、x3是三角形的三条边，从而xi+xj>xk，|xi-xj|<xk，（i,j,k=1,2,3），根据x1+x2+x3=14可知1<xi<7（i=1,2,3）。利用回溯法求解得到：

即有4个可行解：（6，6，2），（6，5，3），（6，4，4，）（5，5，4）。

十二、设数组A有n个元素，需要找出其中的最大最小值。（20分）
(1)请给出一个解决方法，并分析其复杂性。
(2)把n个元素等分为两组A1和A2，分别求这两组的最大值和最小值，然后分别将这两组的最大值和最小值相比较，求出全部元素的最大值和最小值。如果A1和A2中的元素多于两个，则再用上述方法各分为两个子集。直至子集中元素至多两个元素为止。这是什么方法的思想？请给出该方法的算法描述，并分析其复杂性。
解：（1）基本思想：从头到尾逐个扫描，纪录最大和最小元素。
输入：具有n个元素的数组
输出：最大值和最小值
步骤：
void FindMaxMin(int A[], int n, int max, int min)
{
max=min=A[0];
for (i=1;i<n;i++)
{
if (A[i]>max) max=A[i];
if (A[i]<min) min=A[i];
}
}
复杂性分析：由于是从头到尾扫描各个元素，而每个元素都要与max和min比较一遍，从而时间复杂性为：O(n)。
（2）void FindMaxMin(int left,int right, int max, int min) {
if (left==right) max=min=A[left];
else if (left=right-1) {
max=(A[left]<A[right]?A[right]:A[left]);
min=( A[left]<A[right]?A[left]:A[right]);
}
else{
mid=(left+right)/2;
FindMaxMin(left,mid,gmax,gmin);
FindMaxMin(mid+1,right,hmax,hmin);
max=(gmax<hmax?hmax:gmax);
min=(gmin<hmin?gmin:hmin]);
}
}

十三、15谜问题：在一个4×4的方格的棋盘上，将数字1到15代表的15个棋子以任意的顺序置入各方格中，空出一格。要求通过有限次的移动，把一个给定的初始状态变成目标状态。移动的规则是：每次只能把空格周围的四格数字（棋子）中的任意一个移入空格，从而形成一个新的状态。为了有效的移动，设计了估值函数C1(x)，表示在结点x的状态下，没有到达目标状态下的正确位置的棋子的个数。
请使用该估计函数，对图示的初始状态，给出使用分支限界方法转换到目标状态的搜索树。
1
2

4
5
6
3
7
9
10
12
8
13
14
11
15
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

初始状态 目标状态

十四、编写计算斐波那契（Fibonacci）数列的第n项函数fib（n）
　　斐波那契数列为：0、1、1、2、3、……，即：
　 fib(0)=0;
　　fib(1)=1;
　　fib(n)=fib(n-1)+fib(n-2) （当n>1时）。
　　写成递归函数有：
　　int fib(int n)
　　{ if (n==0) return 0;
　　 if (n==1) return 1;
　 if (n>1) return fib(n-1)+fib(n-2); }
十五、求证：O(f(n))+O(g(n)) = O(max{f(n),g(n)})
证明：对于任意f1(n) O(f(n)) ，存在正常数c1和自然数n1，使得对所有nn1，有f1(n) c1f(n) 。
类似地，对于任意g1(n) O(g(n)) ，存在正常数c2和自然数n2，使得对所有nn2，有g1(n) c2g(n) 。
令c3=max{c1, c2}， n3 =max{n1, n2}，h(n)= max{f(n),g(n)} 。
则对所有的 n n3，有
f1(n) +g1(n) c1f(n) + c2g(n)
c3f(n) + c3g(n)
= c3(f(n) + g(n))
c32 max{f(n),g(n)}
= 2c3h(n) = O(max{f(n),g(n)}) .
十六、用分支限界法解装载问题时，对算法进行了一些改进，下面的程序段给出了改进部分；试说明斜线部分完成什么功能，以及这样做的原因，即采用这样的方式，算法在执行上有什么不同
// 检查左儿子结点
Type wt = Ew + w[i]; // 左儿子结点的重量
if (wt <= c) { // 可行结点
if (wt > bestw) bestw = wt;
// 加入活结点队列
if (i < n) Q.Add(wt);
　　　}
　// 检查右儿子结点
if (Ew + r > bestw && i < n)
Q.Add(Ew); // 可能含最优解
Q.Delete(Ew); // 取下一扩展结点
解答：斜线标识的部分完成的功能为：提前更新bestw值；
　　这样做可以尽早的进行对右子树的剪枝。具体为：算法Maxloading初始时将bestw设置为0，直到搜索到第一个叶结点时才更新bestw。因此在算法搜索到第一个叶子结点之前，总有bestw=0，r>0 故Ew+r>bestw总是成立。也就是说，此时右子树测试不起作用。
为了使上述右子树测试尽早生效，应提早更新bestw。又知算法最终找到的最优值是所求问题的子集树中所有可行结点相应重量的最大值。而结点所相应得重量仅在搜索进入左子树是增加，因此，可以在算法每一次进入左子树时更新bestw的值。

十七、请写出用回溯法解装载问题的函数
装载问题：有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且。装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。如果有，找出一种装载方案。
解：void backtrack (int i)
{// 搜索第i层结点
if (i > n) // 到达叶结点
更新最优解bestx,bestw;return;
r -= w[i];
if (cw + w[i] <= c) {// 搜索左子树
x[i] = 1;
cw += w[i];
backtrack(i + 1);
cw -= w[i]; }
if (cw + r > bestw) {
x[i] = 0; // 搜索右子树
backtrack(i + 1); }
r += w[i];
}

十八、用回溯法解0/1背包问题时，计算结点的上界的函数如下所示，请在空格中填入合适的内容
　　　Typep Knap<Typew, Typep>::Bound(int i)
　　　{// 计算上界
　　　 Typew cleft = c - cw; // 剩余容量
　　　 Typep b = cp; // 结点的上界
　　　 // 以物品单位重量价值递减序装入物品
　　　 while (i <= n && w[i] <= cleft) {
　　　 cleft -= w[i];
　　　 b += p[i];
　　　 i++;
　　　 }
　　　 // 装满背包
　　　 if (i <= n) （b += p[i]/w[i] * cleft）;
　　　 return b;
　　　}
十九、用回溯法解布线问题时，求最优解的主要程序段如下。如果布线区域划分为的方格阵列，扩展每个结点需O(1)的时间，L为最短布线路径的长度，则算法共耗时 ( O(mn) )，构造相应的最短距离需要（O(L)）时间
for (int i = 0; i < NumOfNbrs; i++)
{
nbr.row = here.row + offset[i].row;
nbr.col = here.col + offset[i].col;
if (grid[nbr.row][nbr.col] == 0)
{
// 该方格未标记
grid[nbr.row][nbr.col]
= grid[here.row][here.col] + 1;
if ((nbr.row == finish.row) &&
(nbr.col == finish.col)) break; // 完成布线
Q.Add(nbr);
}
}
二十、用回溯法解图的m着色问题时，使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时（渐进时间上限）（O（mn））
Bool Color::OK(int k)
{//
for(int j=1;j<=n;j++)
　　　if((a[k][j]= =1)&&(x[j]= =x[k])) return false;
　　return true;
}

二十一、n后问题回溯算法
(1)用二维数组A[N][N]存储皇后位置,若第i行第j列放有皇后,则A[i][j]为非0值,否则值为0。
(2)分别用一维数组M[N]、L[2*N-1]、R[2*N-1]表示竖列、左斜线、右斜线是否放有棋子，有则值为1,否则值为0。
for(j=0;j<N;j++)
if( !M[j] && !L[i+j] && !R[i-j+N] ) /*安全检查*/
{ A[i][j]=i+1; /*放皇后*/
M[j] = L[i+j] = R[i-j+N] = 1；
if(i==N-1) 输出结果；
else try(i+1,M,L,R,A)；; /*试探下一行*/
A[i][j] = 0 ； /*去皇后*/
M[j] = L[i+j] = R[i-j+N] = 0；
}

二十二、Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：

Hanoi塔
void hanoi(int n, int A, int B, int C)
{
if (n > 0)
{
hanoi(n-1, A, C, B);
move(n,a,b);
hanoi(n-1, C, B, A);
}
}

二十三、简述二分检索（折半查找）算法的基本过程
设输入是一个按非降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x比较，
如果A[(i+j)/2]=x，则返回(i+j)/2；
如果A[(i+j)/2]<x，则A[i：(i+j)/2-1]找x，
否则在A[ (i+j)/2+1：j] 找x。
上述过程被反复递归调用。

二十四、数塔问题。有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的值最大。
for(r=n-2;r>=0;r--) //自底向上递归计算
for(c=0; c<=r ;c++)
if( t[r+1][c]>t[r+1][c+1])
t[r][c]+ = t[r+1][c] ；
else t[r][c]+=t[r+1][c+1] ；

二十五、已知非齐次递归方程： ，其中，b、c是常数，g(n)是n的某一个函数。则f(n)的非递归表达式为：。
现有Hanoi塔问题的递归方程为： ，求h(n)的非递归表达式。
解：利用给出的关系式，此时有：b=2, c=1, g(n)=1, 从n递推到1，有：

二十六、通过键盘输入一个高精度的正整数n(n的有效位数≤240)，去掉其中任意s个数字后，剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n 和s，寻找一种方案，使得剩下的数字组成的新数最小。
【样例输入】
178543
S=4
【样例输出】
13
解答：为了尽可能地逼近目标，我们选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字，否则删除第一个递减区间的首字符。然后回到串首，按上述规则再删除下一个数字。重复以上过程s次，剩下的数字串便是问题的解了。
具体算法如下：
输入s, n;
while（ s > 0 ）
{ i=1; //从串首开始找
while (i < length(n)) && (n[i]<n[i+1])
{i++;}
delete(n,i,1); //删除字符串n的第i个字符
s--;
}
while (length(n)>1)&& (n[1]=‘0’)
delete(n,1,1); //删去串首可能产生的无用零
输出n;
二十七、

所以f(n)与g(n)是同阶的：
二十八、f(n) = n, g(n) = log n

f(n)是g(n)的高阶，所以有
二十九、f(n) = nlog n, g(n) = log n

f(n)是g(n)的高阶，所以有
三十、f(n) = 2n, g(n) = n2

f(n)是g(n)的高阶，所以有
三十一、f(n) = log2n, g(n) = logn2

f(n)是g(n)的高阶，所以有

三十二、求证：
证明：先证 ，即证 使得
当 时，
因为
显然
所以有
再证 。即证
使得当 时， 。因为 ，
所以这个c只能取0和1之间的数，暂取c = 1/2。当 ， ， 。
以下用数学归纳法证明当 时， 。
假设当 ，( )时，有
当 时，

所以 ，则
综合之前已证
有 。

三十三、在一个6×6的棋盘上，共放置12颗棋子，每个格子最多只能放一个棋子，要求每一行，每一列以及两条主对角线上恰好都是两颗棋子。请用回溯法输出所有可能的布局。在不考虑对称的情况下，共有多少种布局？
void Backtrack( int num_chessman )