算法(h)方案策划.pptVIP

第一章 算法; 教学目标 了解算法的基本概念、算法描述语言 ， 掌握几种常见算法的基本实现，并能分析算法的时间和空间复杂度。 学习要点 ⑴ 掌握算法的基本概念和基本特征⑵ 掌握常用的几种算法的思想，例如：列举法，递推法，递归法和减半递推。⑶ 算法复杂度的概念和意义（时间复杂度与空间复杂度）。;算法; 1.1 算法基本概念; 1.1 算法基本概念;1.1.2 算法的基本要素;;1.2 算法设计基本方法;1.列举法;#include iostream #include iomanip using namespace std; int main（） {int i,j,k; for (i=0;i=100;i++) for (j=0;j=100;j++) for (k=0;k=100;k++) {m=i+j+k; n=3*i+2*j+0.5*k; if( (m==100.0) (n==100)) coutsetw(5)isetw(5)jsetw(5)kednl; } return 0; } 总循环次数为1013＝1030301;#include iostream #include iomanip using namespace std; int main（） {int i,j,k; for (i=0;i=100;i++) for (j=0;j=100;j++) for (k=0;k=100;k++) {m=i+j+k; n=3*i+2*j+0.5*k; if( (m==100.0) (n==100)) coutsetw(5)isetw(5)jsetw(5)kednl; } return 0; } 总循环次数为1013＝1030301;首先，考虑到母鸡为3元一只，因此，母鸡最多只能买33以，即算法中的外循环没有必要从0到100．而只需要从0到33就可以了。 其次，考虑到公鸡为2元一只，因此，公鸡最多只能头50只。又考虑到对公鸡的列举是在算法的第二层循环中，此时已经买了I只母鸡，且买一只母鸡的价钱相当于买1.5只公鸡。因此，由第一层循环已经确定买I只母鸡的前提下，公鸡最多只能买50-1.5I只，即第二层对J的循环只需从0到50-1.5I就可以了。 最后，考虑到买的总鸡数为100，而由第一层循环已确定买I只母鸡，由第二层循环已确定买J只公鸡，因此，买小鸡的数量只能是K=100-I-J，即第三层循环已经没有必要了。;#include iostream #include iomanip using namespace std; int main（） {int i,j,k; for (i=0;i=33;i++) for (j=0;j=50-1.5*i;j++) {k=100-i-j; if (3*i+2*j+0.5*k==100.0) coutsetw(5)isetw(5)jsetw(5)kednl; } return 0; };课堂练习;2.归纳法;3.递推法;递推法例题分析;递推法例题分析;递推法例题分析--改进方法;递推法总结:例题分析--改进前后;4.递归法;递归法举例说明;总结：;5.减半递推技术;对于低阶的矩阵相乘问题，如二阶矩阵相乘，减少乘法次数是有可能的。令： ;乘积矩阵C中的各元素可用以上7个量的线性组合来表示：;根据以上分析，假设 ，且 阶矩阵相乘所需要的乘法次数为M（k），则有;减半递推技术总结：;例题;double fun1(double x) { return x*x-2; } typedef double (*FuncType)(double ); double root(double a, double b, double eps, FuncType f) { double f0=f(a),f1, c; do { c=(a+b)/2; f1=(*f)(c); if (f1==0) { return c;} if (f0*f10) a=c; else b=c; } while(fabs(a-b)=eps); c=(a+b)/2; return(c); } ;6.回溯法;1.4 算法的复杂度分析;平均性态;最坏情况复杂性;例题;如果已知需要查找的x一定在数组中，此时q＝1，则A(n)=（n＋l）／2。 如果已知需要查找的x有一半的机会在数组中，此时q＝1／2；则 A(n)=[(n+1)/4]+n/2≈3n/4;最坏情况分析 ;算法的最优性 衡量算法的好坏主要依据算法的复杂度，特别是时间复杂度。通常总是在最坏的情况下分析算法的工作量。 最