算法分析基础2.ppt

* CHANGCHUN UNIVERSITY OF TECHNOLOGY 主讲教师：王涛 第一章 算法设计基础 1 2 3 4 算法时间复杂性分析 算法空间复杂性分析 最优算法 小 结 公元5世纪末，我国古代数学家张丘建在他所撰写的《算经》中，提出了这样的一个问题：“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？”意思是公鸡每只5元、母鸡每只3元、小鸡3只1元，用100元钱买100只鸡，求公鸡、母鸡、小鸡的只数。 思考如下问题 案例一——百鸡问题 令a为公鸡只数，b为母鸡只数，c为小鸡只数。列出约束方程： a+b+c=100 （1） 5a+3b+c/3=100 （2） c%3=0 （3） 分析: a、b、c的可能取值范围为0~100，对a、b、c的所有组合进行测试，满足约束方程的组合是问题的解。把问题转化为用钱买只鸡，则上式变为： a+b+c=n （1）’ 5a+3b+c/3=n （2）’ 案例一——百鸡问题 算法1 百鸡问题 1. void chicken_question(int n,int k,int g[],int m[],int s[]) 2. { 3. int a,b,c; 4. k = 0; 5. for (a=0;a=n;a++){ 6. for (b=0;b=n;b++){ 7. for (c=0;c=n;c++) { 8. if ((a+b+c==n)(5*a+3*b+c/3==n)(c%3==0)) { 9. g[k] = a; 10. m[k] = b; 11. s[k] = c; 12. k++; 13. } 14. } 15. } 16. } 17. } 算法2 改进的百鸡问题 1. void chicken_problem(int n,int k,int g[],int m[],int s[]) 2. {int i,j,a,b,c; k = 0; i = n/5; j = n/3; 3. for (a=0;a=i;a++){ 4. for (b=0;b=j;b++) { 5. c = n–a–b; 6. if ((5*a+3*b+c/3==n)(c%3==0)) { 7. g[k] = a; 8. m[k] = b; 9. s[k] = c; 10. k++; 11. } 12. } 13. } 14. } 米开朗基罗创作的西斯廷教堂穹顶画《创世纪》 西斯廷教堂 案例二——生活中处处存在算法 1. 任选一位观众将一副扑克牌充分洗好. 2. 背对观众,请观众随机抽出一张牌,记住牌面,然后将这张牌放回整副牌的最上面. 3. 接过牌后,洗牌几次.洗的时候保持最上面一张牌不动。 4. 对观众说:我来教你魔法,只要吹一口气,就能把刚才你抽的牌吹到任意位置上. 5. 请观众说出一个数字,比如说10,然后一边吹气,一边想着刚才说的数字10. 6. 在吹完气后,请观众一张一张地将上面的牌取出放在桌上. 7. 到第10张时,将牌翻开,发现并不是其原来抽的牌. 8. 接回整副牌,把上一个步骤里取出堆放在桌上的牌收起,仍放在整副牌的最上面. 9. 然后洗牌几次,洗的时候保持上面放回来的那堆牌不动. 10. 从观众手上拿回刚才翻开的那张牌,插入到最上面9个位置中的任意一个. 11. 对观众说: “你刚才不是在想着那个数字的时候吹的气,而是在吹气的时候想着那个数字,而这是完全不同的两回事.我现在演示一下如何吹气”.对着牌吹一口气. 12. 请观众从上到下数牌,到第10张时翻开. 13. 这张翻开的牌就是观众一开始抽的那张牌. 案例三——生活中处处存在算法 PARTITION(A，p，q) // A是一个实数数组,p, q是该数组的上下限 { x←A[p]； // A[