下载文档原格式
（1）用计算机求解问题的步骤：1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制（2）算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程（3）算法的三要素1、操作2、控制结构3、数据结构算法具有以下5个属性：有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
确定性：算法中每一条指令必须有确切的含义。
不存在二义性。
只有一个入口和一个出口可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。
输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。
输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。
算法设计的质量指标：正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。
效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。
一般这两者与问题的规模有关。
经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。
利用迭代算法解决问题，需要做好以下三个方面的工作：一、确定迭代模型。
在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。
二、建立迭代关系式。
所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。
迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。
三、对迭代过程进行控制。
在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。
不能让迭代过程无休止地重复执行下去。
迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。
《算法分析与设计》期末复习题一、选择题1.算法必须具备输入、输出和（ D ）等4个特性。
A．可行性和安全性 B．确定性和易读性C．有穷性和安全性 D．有穷性和确定性2.算法分析中，记号O表示（ B ），记号Ω表示（ A ）A.渐进下界B.渐进上界C.非紧上界D.紧渐进界3.假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。
在某台计算机上实现并完成概算法的时间为t秒。
现有另一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？（ B ）解题方法：3*2^n*64=3*2^xA．n+8 B．n+6C．n+7 D．n+54.设问题规模为N时，某递归算法的时间复杂度记为T(N)，已知T(1)=1，T(N)=2T(N/2)+N/2，用O表示的时间复杂度为（ C ）。
A．O(logN) B．O(N)C．O(NlogN) D．O(N²logN)5.直接或间接调用自身的算法称为（ B ）。
A．贪心算法 B．递归算法C．迭代算法 D．回溯法6.Fibonacci数列中，第4个和第11个数分别是（ D ）。
A．5，89 B．3，89C．5，144 D．3，1447.在有8个顶点的凸多边形的三角剖分中，恰有（ B ）。
A．6条弦和7个三角形 B．5条弦和6个三角形C．6条弦和6个三角形 D．5条弦和5个三角形8.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。
A．重叠子问题 B．最优子结构性质C．贪心选择性质 D．定义最优解9.下列哪个问题不用贪心法求解（ C ）。
A．哈夫曼编码问题 B．单源最短路径问题C．最大团问题 D．最小生成树问题10.下列算法中通常以自底向上的方式求解最优解的是（ B ）。
A．备忘录法 B．动态规划法C．贪心法 D．回溯法11.下列算法中不能解决0/1背包问题的是（ A ）。
A．贪心法 B．动态规划C．回溯法 D．分支限界法12.下列哪个问题可以用贪心算法求解（ D ）。
算法设计与分析期末试卷A卷A卷一、选择题1.二分搜索算法是利用（A）实现的算法。
A、分治策略2.回溯法解旅行售货员问题时的解空间树是（A）。
A、子集树3.下列算法中通常以自底向上的方式求解最优解的是（B）。
B、动态规划法4．下面不是分支界限法搜索方式的是（D）。
D、深度优先5．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为(。
B。
)。
B、O（nlogn）6．分支限界法解最大团问题时，活结点表的组织形式是（B）。
B、最大堆7、下面问题（B）不能使用贪心法解决。
B N皇后问题8.下列算法中不能解决0/1背包问题的是（A）A贪心法9.背包问题的贪心算法所需的计算时间为（B）A、O （nlogn）B、O（nlogn）10.背包问题的贪心算法所需的计算时间为（B）。
B、O（nlogn）二、填空题1.算法的复杂性有时间复杂性和空间复杂性之分。
2.算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有穷性四条性质。
其中算法的“确定性”指的是组成算法的每条指令是清晰的，无歧义的。
3.解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是回溯法，需要排序的是动态规划和分支限界法。
4.动态规划算法的两个基本要素是最优子结构性质和重叠子问题性质。
5.回溯法是一种既带有深度优先搜索又带有回溯的搜索算法；分支限界法是一种既带有广度优先搜索又带有回溯的搜索算法。
6.用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。
在任何时刻，算法只保存从根结点到当前扩展结点的路径。
如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。
7.用回溯法解图的m着色问题时，使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时O(n)。
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;8.用回溯法解布线问题时，求最优解的主要程序段如下。
1、用计算机求解问题的步骤：1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程3、算法的三要素1、操作2、控制结构3、数据结构算法具有以下5个属性：有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
确定性：算法中每一条指令必须有确切的含义。
不存在二义性。
只有一个入口和一个出口可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。
输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。
输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。
算法设计的质量指标：正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。
效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。
一般这两者与问题的规模有关。
经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法迭代法基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。
解题步骤：1、确定迭代模型。
根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。
2、建立迭代关系式。
迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量3、对迭代过程进行控制。
确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题。
不能让迭代过程无休止地重复执行下去。
迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。
对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。
《算法分析与设计》期末试题及参考答案《算法分析与设计》期末试题及参考答案一、简要回答下列问题：1.算法重要特性是什么？1.确定性、可行性、输入、输出、有穷性2.2.算法分析的目的是什么？2.分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。
3.3.算法的时间复杂性与问题的什么因素相关？3. 算法的时间复杂性与问题的规模相关，是问题大小n的函数。
4.算法的渐进时间复杂性的含义？4．当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。
时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。
5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。
最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：W(n) = max{ T(n，I) } , I∈Dn平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：A(n) =∑P(I)T(n，I) I∈Dn6.简述二分检索（折半查找）算法的基本过程。
6. 设输入是一个按非降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x比较，如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2]<="">7.背包问题的目标函数和贪心算法最优化量度相同吗？7. 不相同。
目标函数：获得最大利润。
最优量度：最大利润/重量比。
8.采用回溯法求解的问题，其解如何表示？有什么规定？8. 问题的解可以表示为n元组：（x1,x2,……x n），x i∈S i, S i为有穷集合，x i∈S i, （x1,x2,……x n）具备完备性，即（x1,x2,……x n）是合理的，则（x1,x2,……x i）(i<n)一定合理。
一、填空题（20分）1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。
2.算法的复杂性有_____________和___________之分，衡量一个算法好坏的标准是______________________。
3.某一问题可用动态规划算法求解的显著特征是____________________________________。
4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。
5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。
6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。
7.以深度优先方式系统搜索问题解的算法称为_____________。
8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。
9.动态规划算法的两个基本要素是___________和___________。
10.二分搜索算法是利用_______________实现的算法。
二、综合题（50分）1.写出设计动态规划算法的主要步骤。
2.流水作业调度问题的johnson算法的思想。
3.若n=4，在机器M1和M2上加工作业i所需的时间分别为a i和b i，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。
4.使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。
1、用计算机求解问题的步骤：1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程3、算法的三要素1、操作2、控制结构3、数据结构算法具有以下5个属性：有穷性：确定性：可行性：输入：输出：算法设计的质量指标：正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。
效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。
一般这两者与问题的规模有关。
复杂性的渐近性态设T(N)是算法A的复杂性函数，使得当N→∞时有：(T(N)-T’(N))/T(N) → 0那么，我们就说T’(N)是T(N)当N→∞时的渐近性态，或叫T’(N)为算法A当N→∞的渐近复杂性而与T(N)相区别。
P = NP经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法分而治之法1、基本思想将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
分治法所能解决的问题一般具有以下几个特征：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
3、分治法的基本步骤（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；（3）合并：将各个子问题的解合并为原问题的解。
递归：直接或间接的调用自身的算法，叫做递归算法。
1、用计算机求解问题的步骤：
1、问题分析
2、数学模型建立
3、算法设计与选择
4、算法指标
5、算法分析
6、算法实现
7、程序调试
8、结果整理文档编制
2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程
3、算法的三要素
1、操作
2、控制结构
3、数据结构
算法具有以下5个属性：
有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
确定性：算法中每一条指令必须有确切的含义。
不存在二义性。
只有一个入口和一个出口
可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。
输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。
输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。
算法设计的质量指标：
正确性：算法应满足具体问题的需求；
可读性：算法应该好读，以有利于读者对程序的理解；
健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。
效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。
一般这两者与问题的规模有关。
经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法迭代法
基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。
解题步骤：1、确定迭代模型。
根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。
2、建立迭代关系式。
迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量
3、对迭代过程进行控制。
确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题。
不能让迭代过程无休止地重复执行下去。
迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。
对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。
编写计算斐波那契（Fibonacci）数列的第n项函数fib（n）。
写成递归函数有：
int fib(int n)
{ if (n==0) return 0;
if (n==1) return 1;
if (n>1) return fib(n-1)+fib(n-2);
}
一个饲养场引进一只刚出生的新品种兔子，这种兔子从出生的下一个月开始，每月新生一只兔子，新生的兔子也如此繁殖。
如果所有的兔子都不死去，问到第12 个月时，该饲养场共有兔子多少只？
Main()
{int I,a=1,b=1; Print(a,b);
For(i=1;i<=10;i++) {
C=a+b; Print(c); A=b;
B=c;
}
}
分而治之法
1、基本思想
将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
分治法所能解决的问题一般具有以下几个特征：
（1）该问题的规模缩小到一定的程度就可以容易地解决；
（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
（3）利用该问题分解出的子问题的解可以合并为该问题的解；
（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
3、分治法的基本步骤
（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
（3）合并：将各个子问题的解合并为原问题的解。
贪婪法
基本思想：以逐步的局部最优，达到最终的全局最优。
无后
效性
【问题】背包问题
问题描述：有不同价值、不同重量的物品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]]);
}
动态规划
基本思想：把求解的问题分成许多阶段或多个子问题，然后按顺序求解各个子问题。
前一个子问题的解为后一个子问题的求解提供了有用的信息。
在求解任何一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解，依次解决各子问题，最后一个子问题就是问题的解。
基本步骤
（1）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。
注意这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。
（2）选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。
当然，状态的选择要满足无后效性。
（3）确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。
所以，如果我们确定了决策，状态转移方程也就写出来了。
但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。
回溯法
基本思想：按照深度优先策略，从根结点出发搜索解空间。
算法搜索至解空间的任一结点时总是先判断该结点是否问题的约束条件。
如果满足进入该子树，继续按深度优先的策略搜索。
否则，不去搜索以该结点为根的子树，而是逐层向其祖先结点回溯。
其实回溯法就是对隐式图的深度优先搜索算法
基本步骤：
1、确定问题的解空间：应用回溯法时，首先应明确定义问
题的解的空间。
问题的解空间应至少包含问题的一个
解。
2、确定结点的扩展规则
3、搜索解空间：从开始结点出发，以深度优先的方式搜索
整个解空间。
【问题】n皇后问题
分支限界法
基本思想：分支限界法是由“分支”和“限界”两部分组成。
“分支”策略体现在对问题空间是按广度优先的策略进行搜索“限界”策略是为了加速搜索速度面采用启发信息剪枝策略。
可能会让画出“子集树斩图”235页例题及图好好看一下。
