算法设计与分析 - 总结0

20. {

21. j=0; 22. o=0;

23. m=fabs(i-1);

24. s1=newint *[fabs(i)]; 25. while(o

27. q=p=s[o];

28. for(k=i-1;k>=0;k--)

29. { 30. s1[j]=newint[i]; 31. for(l=0;l

33. if(l==k){s1[j][l]=i;} 34. else{

35. s1[j][l]=*p; 36. p++;} 37. } 38. j++; 39. p=q; 40. } 41. o++; 42. delete[] q; 43. }

44. delete[]s; 45. s=s1; 46. } 47. }

3-8对于一个平面上n个点的集合S，设计蛮力算法求集合S的凸包的一个极点。 点集合中最左边或者最右边的点一定是凸包的一个极点，则求凸包的极点的问题转化为求点的x坐标最大或最小的点

1. int getPole(int x[],int y[],int n) 2. {

3. int r=0;

4. for(inti=0;i

6. if(x[i]>x[r])r=i; 7. }

8. return r;

3-11 设计算法生成在n个元素中包含k个元素的所有组合对象。

两种思路：

1、 生成所有的组合，在组合中找元素个数为k个的组合。 伪代码：

1．初始化一个长度为n的比特串s=00…0并将对应的子集输出； 2．for(i=1; i<2n; i++) //注意不能书写成i<=2n 2.1 s++；

2.2 判断s中1的个数，若为k，则将s对应的子集输出；

2、 使用k层嵌套循环生成元素个数为k个的组合。 设k=3；n个元素存储在数组a[]中； 伪代码：

for (i=1; i

输出a[i]a[j]a[k]构成的组合。

3-13美国有个连锁店叫7-11这个连锁店以前是每天7点开门，晚上11点关门 不过现在是全天24小时营业。有一天，有个人来到这个连锁店，买了4件商品

营业员拿起计算器敲了一下，说：总共是$7.11顾客开玩笑说：所以你们商店就叫7-11？营业员没有理她，说：当然不是，我是把它们的价格相乘之后得到的。

顾客说：相乘？你应该把他相加才对。营业员说，我弄错了。接着又算了一遍，结果让两个人吃惊的是：计算结果也是$7.11请问，这4件商品的价格是多少？ 参考代码：

1. #include 2. #include 3. int main() 4. {

5. long i,j,k,m; 6.

7. for (i=1; i <=711/4 ; i++) 8. {

9. for (j=i; j <=711/3 ; j++) 10. {

11. for (k=j; k <=711/2 ; k++) 12. {

13. m=711-i-j-k;

14. if (i*j*k*m==711*1000000) 15. {

16. cout<

21. return 0; 22. }

输出结果为：价格分别是1.2 1.25 1.5 3.16

第4章 分治法

了解分治法的设计思想

设计思想：将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。 步骤：（1）划分（2）求解子问题（3）合并

分治法的代表算法及时间复杂度：

归并排序，快速排序，最大子段和，最近对问题，凸包问题，这五种问题的分治算法的时间复杂度为O(nlog2n)

棋盘覆盖，循环赛日程安排为O(4k)

掌握归并排序和快速排序算法的算法伪代码。（P78-83） 归并排序：

算法中数组r中存储原始数据，r1在中间过程中存储排序后的数据，s指需排序数组的起始下标，t指需排序数组的结束下标。最终排序后的数据依然存储在r数组中。

快速排序：