for (i=1;i<=n;i++) x[i]=0; float c=M;

for (i=1;i<=n;i++) { if (w[i]>c) break; x[i]=1; c - =w[i]; }

if (i<=n) x[i]=c/w[i]; }

2.最大子段和: 动态规划算法 int MaxSum(int n, int a[]) {

int sum=0, b=0； //sum存储当前最大的b[j], b存储b[j] for(int j=1； j<=n； j++) { if (b>0) b+= a[j] ；

else b=a[i]; ； //一旦某个区段和为负，则从下一个位置累和

if(b>sum) sum=b;

}

return sum； } 3.快速排序

template

void QuickSort (Type a[], int p, int r) {

if (p

int q=Partition(a,p,r);

QuickSort (a,p,q-1); //对左半段排序

QuickSort (a,q+1,r); //对右半段排序 } }

4.排列问题

Template

void perm(Type list[], int k, int m ) { //产生[list[k:m]的所有排列 if(k==m)

{ //只剩下一个元素

for (int i=0;i<=m;i++) cout<

else //还有多个元素待排列，递归产生排列 for (int i=k; i<=m; i++) {

swap(list[k]，list[i]); perm(list,k+1;m);

swap(list[k],list[i]); } }

5.给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。

据此容易设计出二分搜索算法： template

int BinarySearch(Type a[], const Type& x, int l, int r) {

while (l<=r ){ int m = ((l+r)/2); if (x == a[m]) return m;

if (x < a[m]) r = m-1; else l = m+1; } return -1; }

6、合并排序描述如下： template

void Mergesort(Type a[ ], int left, int right) {

if (left

int i=( left+right)/2; Mergesort(a, left, i ); Mergesort(a, i+1, right);

Merge(a,b, left,i,right);//合并到数组b Copy(a,b, left,right ); //复制到数组a }

}

7、以下是计算xm的值的过程

int power ( x, m ) {//计算xm的值并返回。

y=( 1 );i=m; While(i- - >0) y=y*x; (return y) ; } 四、问答题

1.用计算机求解问题的步骤：

1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制

2. 算法定义：

算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程

3.算法的三要素

1、操作2、控制结构3、数据结构

13. 分治法与动态规划法的相同点是：

将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

两者的不同点是：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。

回溯法中常见的两类典型的解空间树是子集树和排列树。 22.请叙述动态规划算法与贪心算法的异同。

共同点：都需要最优子结构性质，都用来求有优化问题。 不同点：

动态规划：每一步作一个选择—依赖于子问题的解。 贪心方法：每一步作一个选择—不依赖于子问题的解。

动态规划方法的条件：子问题的重叠性质。

可用贪心方法的条件：最优子结构性质；贪心选择性质。

动态规划：自底向上求解；贪心方法： 自顶向下求解。可用贪心法时，动态规划方法可能不适用；可用动态规划方法时，贪心法可能不适用。 23. 请说明动态规划方法为什么需要最优子结构性质。

答：最优子结构性质是指大问题的最优解包含子问题的最优解。

动态规划方法是自底向上计算各个子问题的最优解，即先计算子问题的最优解，然后再利用子问题的最优解构造大问题的最优解，因此需要最优子结构. 24. 请说明：

(1)优先队列可用什么数据结构实现？ (2)优先队列插入算法基本思想？ (3)优先队列插入算法时间复杂度？