计科班算法设计与分析(doc 8页)

1. 算法：是若干条指令组成的有穷序列2. 算法的三个要素1)数据: 运算序列中作为运算对象和结果的数据.2)运算: 运算序列中的各种运算:赋值,算术和逻辑运算 3)控制和转移: 运算序列中的控制和转移. 四条性质：输入、输出、确定性、有穷性3. 四条性质：1)输入：有零个或多个由外部提供的量作为算法的输入2)输出：算法产生至少一个量作为输出3)确定性：组成算法的每条指令是清晰的，无歧义的。4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。4. 程序：是算法用某种程序设计语言的具体实现5. 算法的复杂性：算法运行所需要的计算机资源的量时间复杂性（算法运行所需要的计算机时间资源的量）空间复杂性（算法运行所需空间资源的量）时间复杂性的三种情况：最坏情况（可操作性最好且最优实际价值）、最好情况、平均情况6. 分治法的设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。7. 递归：直接或间接地调用自身的算法。递归函数：用函数自身给出定义的函数。8. 阶乘函数可递归定义为：递归定义式：int factorial(int n)if (n = 0) return 1;return n * factorial(n-1);9. Fibonacci数列：无穷数列1，1，2，3，5，8，13，21，34，5，可递归定义为递归定义式：int fibonacci(int n)if (n = 1) return 1;return fibonacci(n-1)+fibonacci(n-2);10. Hanoi塔定义式：void hanoi(int n, int a, int b, int c)if (n 0)hanoi (n - 1, a, c, b);move (a, b);hanoi (n - 1, c, b, a);11. 二分搜索算法的基本思想：是将n个过元素分成大致相同的两半，取an/2与x作比较。12. 合并排序：用分治法策略实现对n个元素进行排序的算法。基本思想是：将待排序元素分成大小大致相同的两个子集，分别对两个子集合进行排序，最终将排好序的子集合并成所要求的排好序的集合。13. 动态规划算法基本思想（自底向上、全局最优）：讲带求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是：适用于动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。最优子结构性质（问题的最优解包含了其子问题的最优解）子问题重叠性质（在用递归算法自顶向下求解此问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次）备忘录方法（动态规划算法变形）：用表格保存已解决的子问题的答案，在下次需要解此子问题时，只要简单地查看该子问题的解答，而不必重新计算。14. 最优二叉搜索树性质：存储于每个结点中的元素x大于其左子树中任一结点所存储的元素，小于其右子树中任一结点所存储的元素。15. 贪心算法（自顶向下、局部最优）：通过一系列的选择来得到问题的解。它所做的每一个选择都是当前状态下局部最好选择。贪心选择性质（所求问题的整体最优解可以通过一系列局部最优的选择来达到，是贪心算法与动态规划算法的主要区别）最有子结构性质（一个问题的最优解包含其子问题的最优解）16. 哈夫曼编码：是广泛用于数据文件压缩的十分有效的编码方法。17. 最短路径：给定一个，其中每条边的权是非负实数。一个带权有向图1111110060103010502018. 最小生成树性质：用贪心算法设计策略可以设计出构造最小生成树的有效算法。19. 回溯法（盲人爬山、迷宫问题、n后问题）：在解问题的解空间树中，按深度优先策略，从根节点出发搜索解空间树。20. 基本思想：从开始结点（根节点）出发，以深度有限方式搜索整个解空间。21. 分枝限界法基本思想：以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。分枝限界法求解目标是找出满足约束条件的一个解，或是满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。回溯法求解目标是找出解空间中满足约束条件的所有解。22. 批处理作业调度：给定n个作业的集合J = (J1,J2,Jn)。每个作业Ji都有两项任务分别在两台机器上完成。每个作业必须先由机器1处理，然后再由机器2处理。23. 分支限界法与回溯法：分支限界法与回溯法的求解目标不同，回溯法的求解目标是找出求解空间中满足约束条件的所有解，而分支限界法求解的目标则是找出满足约束条件的一个解。回溯法以深度优先的方式搜索解空间，而分支限界法则以广度优先或最小耗费优先的方式搜索空间。24. 随机化算法基本特征：对所求解问题的同一实例用同一随机化算法求解两次可能得到完全不同的效果。随机数在随机化算法设计中扮演着十分重要的角色。符号三角问题：#include #define M 13#define N 13Triangle(char AMN)int i,j; printf(n 输入第1行的数据：);for (j=0;jN;j+)/ 输入第1行的数据scanf(%c,&A0j);for (i=1;iM;i+)/ A数组的第2行以下清空for (j=0;jN;j+)Aij= ; i=0;j=0;while(iM-1)while(jN-1)if (Aij=Aij+2) / 如果上一行的相邻两符号相同Ai+1j+1=+;/ 则下一行的符号为+elseAi+1j+1=-;/ 否则下一行的符号为-j=j+2;i+;j=i;void main()int i,j;char AMN;Triangle(A);for (i=0;iM/2+1;i+)for (j=0;jN-i;j+)printf(%4c,Aij);printf(nn);矩阵相乘：/ 两矩阵相乘#include #define M 2#define N 3MatrixMultiply(int AMN,int BNM,int CMM)int i,j,k,sum;for (i=0;iM;i+)for (j=0;jM;j+) sum=0;for (k=0;kN;k+)sum=sum+Aik*Bkj;Cij=sum;void main()int AMN,BNM,CMM,i,j,k;for (i=0;iM;i+)/ 输入6个整数给矩阵Afor (j=0;jN;j+)scanf(%d,&Aij);for (i=0;iN;i+)/ 输入6个整数给矩阵Bfor (j=0;jM;j+)scanf(%d,&Bij);MatrixMultiply(A, B, C);printf(n 两矩阵相乘的的结果如下：nn);for (i=0;iM;i+)for (j=0;jM;j+)printf(%4d,Cij);printf(nn);二分搜索算法：是用分支策略的典型例子，需要先排序。# include # define MAXLEN 11typedef structint key;type_element;int binary_search(type_element r,int key)int left=1,right=MAXLEN,middle;while (leftkey)right=middle-1; / 在右半部继续查找elseleft=middle+1; / 在右半部继续查找return -1;void main()int i,j,key;type_element temp,rMAXLEN+1=0,9,13,15,30,37,55,60,75,80,90,92;for (i=1;iMAXLEN;i+)/ 对数组进行排序for (j=i+1;jrj.key)temp=ri;ri=rj;rj=temp;for (i=1;i=MAXLEN;i+)printf(%3d,ri.key);printf(nn 输入欲查找的数据：);scanf(%d,&key);i=binary_search(r,key);if (i=-1)printf(n 已经查找完，尚未找到该数！nn);elseprintf(nn 已找到，其序号是：%d nn,i);快速排序：#include #include #define MAXLEN 10int partition(int r,int s,int t)int i,j,rp;i=s;j=t;/一趟快速排序，将基准记录移到正确位置rp=rs;/基准记录暂存 rp 中while(ij)/从序列的两端交替向中间扫描while(i=rp)/扫描比基准记录小的位置j-;ri=rj;/将比基准记录小的数据移到低端while(ij & ri=rp)/扫描比基准记录大的位置i+;rj=ri;/将比基准记录大的数据移到高端ri=rp;/基准记录到位return i;void QuickSort(int r,int s,int t)/快速排序递归算法int k;if (st)/长度达于1k=partition(r,s,t);/调用一趟快速排序算法将rs.rt一分为二QuickSort(r,s,k-1);/对低端子序列递归排序，k是支点位置QuickSort(r,k+1,t);/对高端子序列递归排序void main()int i;int rMAXLEN;printf(n 请输入%d个整数：,MAXLEN);for (i=0;iMAXLEN;i+)scanf(%d,&ri);QuickSort(r,0,MAXLEN-1);printf(n 快速排序的结果如下：nn);for(i=0;iMAXLEN;i+)printf(%3d,ri);printf(nn);循环赛日程表：#include #define MAXLEN 8 void main()int i,j;int xMAXLEN+1MAXLEN+1=0;/ 数组清零for (i=1;i=MAXLEN;i+) / 产生第1列数据xi1=i;for (i=1;i=MAXLEN;i+) / 产生第2列数据if (i % 2 !=0)xi2=xi+11; / 产生奇数行的第2列的数据elsexi2=xi-11; / 产生偶数行的第2列的数据for(i=1;i=8;i+) / 产生左半部表中的右半部分for (j=1;j=2;j+)if (i=1 | i=2 | i=5 | i=6)xi+2j+2=xij;elsexi-2j+2=xij;for(i=1;i=8;i+)/ 产生右半部表的数据for (j=1;j=4;j+) if (i=4)xi+4j+4=xij;elsexi-4j+4=xij;printf(n 循环赛日程表如下：nn);for (i=1;i=MAXLEN;i+) / 输出该表for (j=1;j=MAXLEN;j+)printf(%6d,xij);printf(nn);最大公约数：int gcd(int m,int n) int r;while(n!=0) r = m % n;m = n;n = r;return m; 最小公倍数：int gcm(int m,int n)int i,k,f;if (mn) / 交换m与ni=m;m=n;n=i;f=1; if (m%n=0)f=f*m;return f;i=2;k=(int)(sqrt(n);/ 求n的平方根取整数while(i=k) if (m%i=0)&(n%i=0)f=f*i; m=m/i;n=n/i;i=2;else i+;f=f*m*n;return f; 冒泡排序：/ 交换排序中的冒泡排序法# include # define LENGTH 10void main() int i,j,k,temp;int rLENGTH;for (i=0;iLENGTH;i+)scanf(%d,&ri);/输入10个整数for (i=1;i=LENGTH-1;i+)/共进行 LENGTH-1 趟排序k=0;for (j=0;jrj+1)/若相邻两记录的关键字逆序， k+; / 则互相交换 temp=rj; rj=rj+1; rj+1=temp; if (k=0)/ 说明该趟没有发生交换break; / 跳出该层循环for(i=0;iLENGTH;i+)printf(%3d,ri); / 输出排序结果素数判断：int number; / number 为全局变量bool prime(int x)int i,k;k=sqrt(x);for (i=2;i=k;i+) / 如果X能被 2 - sqrt(x) 中的任何一个整数整除，if (x%i=0)/则X不是素数，因此应跳出该层循环return false;retrun true;/ 表示X未被 2 - sqrt(x) 中的任何一个整数整除素数因子分解：#include #include #define N 100void main()int i,j,k,x,y,sieve_AN+1,sieve_BN+1,sieve_CN+1;scanf(%d,&x);/ 输入一个100以内的非负整数y = x; if(x0)return;/ 输入整数是负数for(i=2;i=x;i+)/ 设置sieve_A筛中数据 2 Xsieve_Ai=i;k=(int)sqrt(x);for(i=2;i=k;i+)j=i*i;while(j=x)if (sieve_Aj!=0)/定位 i 的倍数处sieve_Aj=0;