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 r = 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、数据结构

4. 算法具有以下5个属性：

有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。

确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口

可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。

输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。

5. 算法设计的质量指标：

正确性：算法应满足具体问题的需求；

可读性：算法应该好读，以有利于读者对程序的理解；

健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。

效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。

经常采用的算法主要有迭代法、分治法、贪婪法、动态规划法、回溯法、分支限界法

6. 迭代法:

也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。 7.利用迭代算法解决问题，需要做好以下三个方面的工作：

1)、确定迭代模型。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。

2)、建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。