文档介绍：程序设计=计算机编程语言+数据结构+算法
数据结构是指数据的逻辑结构和存储结构，而算法则是对数据运算的描述。
程序设计的实质是对实际问题选择一种好的数据结构，加之设计一个好的算法。
第1页，共79页，编辑于2022年，星期一
算法的1)+ F(n-2) n = 3,4,…
第14页，共79页，编辑于2022年，星期一
求Fibonacci数列流程图
开始
F1=1,F2=1,n=3
n<14
F3=F1+F2
F1=F2, F2=F3
n=n+1
输出Fn
结束
N
Y
第15页，共79页，编辑于2022年，星期一
设每只母鸡值3元，每只公鸡值2元，。现要用100元钱买100只鸡，设计买鸡方案算法。 （列举法）
解：设买母鸡 I 只，买公鸡 J 只，买小鸡 K 只，则有
第16页，共79页，编辑于2022年，星期一
猴子吃桃子：小猴在一天摘了若干个桃子，当天吃掉一半多一个；第二天接着吃了剩下的桃子的一半多一个；以后每天都吃尚存桃子的一半零一个，到第7天早上要吃时只剩下一个了，问小猴那天共摘下了多少个桃子？
设第n天的桃子为Ｘn，那么它是前一天的桃子数Ｘn-1的二分之一减一。
递推关系为 ：
第7天：1
第6天：4
第5天：10
第4天：22
第3天：46
第2天：94
第1天：190
第17页，共79页，编辑于2022年，星期一
猴子吃桃子算法的流程图
i >1
i=i-1
x=xi
xi=2(x+1)
输出 i,xi
i=7 , x=1
结束
N
Y
开始
第7天：1
第6天：4
第5天：10
第4天：22
第3天：46
第2天：94
第1天：190
第18页，共79页，编辑于2022年，星期一
0
f(x1)
f(x2)
f(x3)
f(x4)
x1
x2
x3
x4
减半递推（迭代）法
设方程 f(x)=0在区间[x1,x2]上有一个实根，且f(x1)与f(x2)异号，用二分法求该方程在区间[x1,x2]上的实根。
减半递推过程：
求中点：x3=1/2(x1+x2)
判 f(x3)是否接近0？
若接近0，x3即为所求根
若不接近0，则将原区间减半
舍弃与f(x3)同号者：x2=x3
再求中点：x4=1/2(x1+x3)
如此重复得：x1,x2,…,xn-1,xn
当xn与xn-1之差小于给定的误差En时，xn即为近似解
迭代关系： x3=(x1+x2)/2
舍弃与f(x3)同号者：f(x3)*f(x2)>0 : x2=x3; /*为下一次迭代做准备*/
f(x3)*f(x1)>0 : x1=x3;
第19页，共79页，编辑于2022年，星期一
f(x3)* f(x1) <0
f(x3)=.. f(x1)=.. f(x2)=...
x1=x3
x2=x3
输入x1,x2
结束
N
Y
开始
x3=(x1+x2)/2
|f(x3)|>10-4
输出结果x3
Y
N
流程图
第20页，共79页，编辑于2022年，星期一
算法的评价
时间复杂度：指算法中包含简单操作的次数
假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，则可记作：
T(n) = O(f(n))
称T(n) 为算法的(渐近)时间复杂度
一般以数量级的形式给出
如Ο(1), Ο(log2n), Ο(n), Ο(n2)
其中Ο(1)表示算法的时间复杂度为常量，它不随数据量n的改变而改变，如访问一个数据表中第一个元素时，无论该表的大小如何，其时间复杂度均为Ο(1)
第21页，共79页，编辑于2022年，星期一
For i=1 to n－1 do
{ y=y+1; /* ① */
For j=0 to 2n do
x=x+1; /* ② */
}
语句①的执行次数为：n－1，
语句②的执行次数为：（n－1）（2n＋1）＝2n2－n－1
该程序段的时间复杂度为：
T（n）＝O（n－1＋2n2－n－1）＝O（n2）
第22页，共79页，编辑于2022年，星期一
空间复杂度
空间复杂度主要考虑在算法运行过程中临时占用的存储空间的大小
假如，随着问题规模 n 的增大，算法运行所需存储量的增长率与 g(n) 的增长率相同，则可记作：
S(n) = O(g(n))
称S(n)为算法的空间复杂度
第23页，共79页，编辑于