计算机算法设计与分析总课件.ppt

设数组为：a[n] 1、当n==1时，return a[n]; 当n!=1时，将数组元素两两比较，大的放在big[ ],小的放在samll[ ],对数组samll求最大值元素，并与上一次所得的second比较,将较大值斌给second; 2、对big[ ]重复第1步, if(n%2!=0) { big[i]=num[i]; i++; } if(i==1) return big[0]; else return max(big,i); } V[0] V[1] V[2] V[3] V[4] V[5] 1 2 3 4 5 6 由于礼物是升序排列的，所以在分配的时候由从最大的礼物分配起来，根据数学原理，因从升序开始分配 通过实际例子理解分配方式： V[0] V[1] V[2] V[3] V[4] V[5] 1 2 3 4 5 6 通过实际例子理解分配方式： Alan-0 Bob-0 -6 -3 -2 -5 -4 -1 -11 -10 a加上该元素后大于b，则将下一个元素赋给b 降序排列 V[0] V[1] V[2] V[3] V[4] V[5] 1 2 3 4 5 6 通过实际例子理解分配方式： Alan-0 Bob-0 降序排列 -1 -3 -5 -2 -4 -6 -9 -12 a加上该元素后大于b，则将下一个元素赋给b for(int i=n-1;i=0;i--) {if(ab) {b=b+v[i]; Bob[r]=v[i]; r++;} else{ a=a+v[i]; Alan[s]=v[i]; s++; } 按照从高的礼物分配起 重点的选择分配循环 a加上该元素后大于b，则将下一个元素赋给b a和b分别表示Alan和Bob所得到的礼物的价格 Alan[s]和Bob[r]在得到礼物的分别价格 通过软件来分配更多的礼物来看情况。 程序设计的总体过程 1.礼物的个数和各个礼物的价格 2.通过循环来分配礼物 3.输出每个人所得到的礼物总体价格 4.输出每个人所得到礼物的各个价格 通过实际例子理解分配方式： 12-19-21-25-40 45-56-72-79-80 Alan-0 Bob-0 -80 -56 -45 -79 -72 -40 -25 -21 -19 -12 【225】 【224】 通过软件来分配更多的礼物来看情况。 运用软件实现 通过软件来实现礼物分配： 运用软件实现 设有n个程序{1，2，3，...，n}要存放在长度为L的磁带上。程序i存放在磁带上的长度是li，1≦i≦n。如果将这n个程序按i1,i2,...，in的次序存放，则读取程序ir所需的时间与 成正比。这n个程序的平均读取时间为 。 题意：第六题（优化存储） 解题人：陈振凯 学号：2008034243135 分析思路： 存放的有序 平均读取时间的最小 ------ 1 2 3 ...... n i1 i2 i3 ...... in 当输入每个任务的长度： 磁带最优存储问题要求确定这n个程序在磁带上的一个存储次序，使得平均读取时间达到最小。 需要设计一个解决此问题的算法，并分析算法的正确性和计算的复杂度。 分析思路： 读第一个程序的时间 t1=k（i1）/1 读第二个程序的时间 t2=k（i1+i2）/2 ...... ...... 读第n个程序的时间 tn=k（i1+i2+...in）/n 当输入每个任务的长度（k是个常量） n个程序的平均读取时间为: t’=（t1+t2+。。。tn）/n =k[n*i1+(n-1)*i2+(n-2)*i3+。。。+in] 分析思路： 为了使t’达到最小，只能使in的排序为降序（数学证明） * 算法设计与分析 小组成员： 张建龙 莫媚 陈壮茂 陈振凯 林晓丹 3 4 1 2 6 8 1、给定数组a[0:n-1],试设计一个算法,在最坏情况下用n+[logn]-2次比较找出a[0:n-1] 中的元素的最大值和次大值. 题意：第一题（最大次大） 解题人：张建龙 学号：2008034243132 算法思想： 采用递归算法 比较a[i]与a[n-i-1] n/2 … … 1 0 n/4 … … 1 0 n/4 … … 1 0 2/n … … 1 0 n … … 1 0 n=0 small big … number=max(small,i); n/8 … … 1 0 Second=(number