发布时间 : 星期一 文章算法设计与分析复习题目及答案资料更新完毕开始阅读
while (i < length(n)) && (n[i] delete(n,i,1); //删除字符串n的第i个字符 s--; } while (length(n)>1)&& (n[1]=‘0’) delete(n,1,1); //删去串首可能产生的无用零 输出n; 三、算法填空 1.背包问题的贪心算法 void Knapsack(int n,float M,float v[],float w[],float x[]) { Sort(n,v,w); int i; 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.请叙述动态规划算法与贪心算法的异同。 共同点：都需要最优子结构性质，都用来求有优化问题。 不同点： 动态规划：每一步作一个选择—依赖于子问题的解。 贪心方法：每一步作一个选择—不依赖于子问题的解。