第一部分：算法基础
1、算法五个特征：
零个或多个输入、至少一个输出、确定性、能行性、有穷性。 算法就是求解一类问题的任意一种特殊的方法。
联系：算法+数据结构=程序，算法是程序设计的核心，算法的好坏程度上决定了一个程序的效率。一区别：算法是解决问题的步骤，程序是算法的代码实现依靠程序来完成功能，程序作为算法的灵魂。2、算法意义：
3、算法与程序的联系与区别：
个好的算法可以降低一个程序运行的时间复杂度和空间复杂度。
程序是结果算法是手段，编写一个同样功能的程序，使用不同的算法，可以让程序的体积和效率有很大的该变。
4、好算法的特性：
正确性、简明性、效率、最优性（健壮性、可靠性）。 程序所依赖的算法、问题规模和输入数据、计算机系统性能 5、影响程序运行的时间因素：
6、时间复杂性分为3坏情况下的时间复杂性。 7、渐进表示法：
大O 几号（渐进上界）：
定义：设函数f(n)和g(n)c 和n 0, 使得当
n>=n0时，有f(n)
Ω记号（渐进紧界）：
定义：设有函数f(n)和g(n)c 和n 0，使得
当n>= n0时，有f(n)>=cg(n),Ω(g(n)),omega notation）【算法设计与分析c++描述第二版陈惠南p20
Θ记号（渐进下界）：
定义：设有函数如果存在正常数c1,c2和n
0, 使得当小
且f(n)!= Ω(g(n))。
n>=n0）f(n)= Θ(g(n)),称为Θ记号（Theta natation）。
***渐进表示法
设有f(n)和g(n),分析。
1】f(n)=20n+logn,g(n)=n+nlog3n; 当n ≥3时，log n 2n 。可
选 c =
21
，n 0=3。对于n ≥n 0，f (n ) ≤cg (n ) ，即f (n ) =O(g (n )) 。注意：是f (n ) 和g (n ) 2
的关系。
2】f （n ）=n2/logn,g(n)=nlog2n; 当 n
≥4 时，log n
c =1，n 0=4。对于 n ≥n 0，f (n )
3】f(n)=(logn)因为
logn
,g(n)=n/logn;
，
f (n ) =(logn ) log n =n log(logn )
g (n ) =n /log n =n log n 2
。当
n ≥4
时，
第三部分：贪心法
背包问题：
n=5,m=11,(p0…p4)=(8,6,15,6,3) (w0…w5)=(2,3,5,2,3),
最优量度标准：优先选择单位重量收益最大的物品放入背包。 (p0/w0, p1/w1, p2/w2, p3/w3,p4/w4)=(4,2,3,3,1) 最优解为：(x0,x1,x2,x3,x4,x5,x6) =(1,2/3,1,1,0) 最大收益为:8+6*2/3+15+6)=33
分析所有最优解。。。。。。。。。。。。。。。。。
1、简述贪心算法的思想策略、算法特点，以及它所具有的两种性质各是什么？ 思想策略: 贪心法是一种求解最优化问题的算法设计策略。
算法特点: 贪心法是通过分步决策的方法来求解问题的, 贪心法在求解问题的每一步上做出某种决策, 产生N –元组解的一个分量。
性质: 贪心选择性质和最优子结构性质。 2、简要说明贪心算法的两个基本要素。
贪心选择性质: 贪心法要求根据题意, 选定一种最优量度标准, 作为选择当前分量值的依据, 这种在贪
***********详解s[i][j]******************************
以此题为例，A0,A1，A2，A3,A4，A5.
第五部分：回溯法
1、回溯法法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。
第六部分：分枝界限法
1、分枝限界法法在问题的解空间树中，按广度优先策略，从根结点出发搜索解空间。
***
附加***
回溯法和分支限界法的不同之处。
: . 如果在运用搜索算法是使用剪枝函数, 回溯法的求解目标是在状态空间树上找出满足约束条件的所有解, , 或是在满足约束条件的解中找出最优解. 递推关系式
#include
#define MAX 99 //定义无穷大 struct Node{ };
class Graph {
int length; //权值（源点到该结点的路径长度） inti; //结点编号
friend bool operator
returna.length>b.length;
i =j ⎧⎪0
m [i ][j ]=⎨min {m [i ][k ]+m [k +1][j ]+p p p } i
public:
voidShorestPaths(int); voidShowDist(); Graph(); ~Graph(); private:
int n; //图的节点个数 int *prev; //存放顶点的前驱节点 int **c; //存放图的邻接矩阵
int *dist; //存放源点到各个顶点的距离 };
Graph::Graph() {
intwi = 0; intyi = 0; int s;
inti,j,m;
cout>n;
cout>s;
c = new int*[n]; for (wi = 0; wi
dist = new int[n];
prev = new int[n];
for (wi = 0; wi
( ij // (无穷大（99）代表节点间无边
cin>>i>>j>>m;
c[i][j] = m;
}
for (wi = 0; wi
dist[wi] = MAX; prev[wi] = -1; } }
Graph::~Graph() {
for(inti=0;i
delete []c;
delete []dist; delete []prev; }
void Graph::ShowDist() {
cout
cout
cout=0 ) { cout
if(temp) cout
temp = prev[temp]; } cout
{
E.i = v; E.length = 0; dist[v] = 0;
cout
{ if ((c[E.i][j] != MAX) && (E.length + c[E.i][j]
{
dist[j] = E.length + c[E.i][j]; prev[j] = E.i; //记录前驱结点
//加入活结点优先队列 ,若节点为终点，则不加入活结点队列 if (j != n-1) { Node N; N.i = j;
N.length = dist[j]; H.push(N); //N结点入队
cout
}
}
} //for
if(!H.empty())
{
E=H.top();//出队 cout
H.pop(); //删除該元素
cout
break; } //while }
int main() {
Graph g;
}