第一章 算法的基本概念 徐浩.pptVIP

第一章 算法的基本概念 数理学院 徐浩 考虑下最少和最多次数的情况？ 图1.1比较了3次，图1.2比较了7次 7 4 2 30 4 2 25 18 13 10 8 25 18 13 10 8 图1.1 合并2个有序数组，元素比较次数最少的情况 图1.2 合并2个有序数组，元素比较次数最多的情况 例1.14 收白菜。菜园有n个白菜，并且按照顺时针方向编了号1~n号，按顺时针方向从1号开始，每隔2个白菜收一颗。要求你列出来白菜的编号。 输入：白菜的棵数n 输出：将收割编号的数组B[]输出 void fun(B[],int n) { int i,j,k,s,t; int *A=new int [n]; j=0;k=3;s=n; for(i=0;in;i++) A[i]=i+1; while(jn){ t=s;s=0; for(i=0;it;i++){ if(--k!=0) A[s++]=A[i]; else{ B[j++]=A[i];k=3; } }}delete A; } 红字处分别要赋值n次和2n次。因此一共执行了3n次，时间复杂度是O(n)。 *1.3.3 计算歩的统计 定义1.9：计算歩是一个语法或者语义意义上的程序段。程序段的执行时间与输入实例无关。计算歩统计程序中所有歩的时间花费。选择作为计算歩的部分，必须和输入规模无关。 1.3.4 最坏情况和平均情况 某些算法只与输入的规模n有关，与输入的具体数据无关。 例1.15 插入法排序 输入：n个元素的整数数组A[],数组元素个数n 输出：排好序的数组A[] Void insert(int A[],int n) { int a,i,j; for(i=1;in;i++){ a=A[i];j=i-1; while(j=0A[j]a){ A[j+1]=A[j]; j--; } A[j+1]=a; }} 1.1 引言 1.1.1 算法的定义和特征 算法的定义:Algorithm,解决一个特定问题的一组有穷规则的集合 算法的特征，由唐纳德.E.克努特描述 1.有限性,算法必须在执行有限步后终止,运算的时间合理 2.确定性,每一步都必须有明确的定义 3.输入,必须有0个或者多个输入 4.输出,必须有1个或者多个输出 5.能行性,算法中有待实现的运算都是基本运算 好的算法是如何设计出来的? #include stdio.h #include conio.h main() { int i,j; printf(first num is:); scanf(%d,i); printf(second num is:); scanf(%d,j); printf(the result is:%d,euclid(i,j)); getch(); } int euclid(int m,int n) { int r; do{ r=m%n; m=n; n=r; }while(r); return m; } 一个简单的算法问题:欧几里德问题,求二数的最大公因数 1.1.2 最简单的算法设计方法:穷举法 例1.1:百鸡问题 张丘建在算经中提出:公鸡5元每只,母鸡3元每只,小鸡3只1元,用100元买100只鸡,各自有多少只. 令a为公鸡只数，b为母鸡只数，c为小鸡只数，可得如下约束方程： 只要使用3重循环就可以实现穷举法求结果，程序如下： #include stdio.h #include conio.h main() { int n,h; printf(the total num and money is:) ; scanf(%d,%d,n,h); chicken_question(n,h); getch(); } int chicken_question(int n,int h) { int k, a,b,c; int g[10],m[10],j[10]; k=0; for(a=0;a=n;a++){ for(b=0;b=n;b++){ for(c=0;c=n;c++) { if((a+b+c==n)(5*a+3*b+c/3==h)(c%3==0)) { g[k]=a;m[k]=b;j[k]=c; printf(the cock num is:%d,the hen num is:%d,the chicken num is:%d\n,a,b,c); k++; } }}} if(k==0) printf(no result); else printf(the total result nu