发布时间 : 星期三 文章算法设计与分析实验报告更新完毕开始阅读
using namespace std; int count=0;
int check(char list[],int k ,int m ) //判断是否互异，重复返回 0 {
if( m > k)
for(int i = k ; i< m ; i++) if( list[i] == list[m] ) return 0 ; return 1 ; }
inline void swap(char &a,char &b) {
char temp;
temp=a;a=b;b=temp; }
void perm(char list[],int k,int m) {//依次交换第一个元素进行排序 if(k==m) //只剩下一个元素 {
count++;
for(int i=0;i<=m;i++) fout< else //还有多个元素，递归产生排列 for(int i=k;i<=m;i++) { if(check(list,k,i)) { swap(list[k],list[i]); perm(list,k+1,m); swap(list[k],list[i]); } } return; } void main() { char number[100]; int i=0,n=0; //n 是总个数 fin>>number; //number 数组为待排元素 while(number[i] != '\\0') { n++; i++; } perm(number,0,n-1); fout< （3） 设计算法求解棋盘的覆盖问题，并编程实现（P20）。 （4） 设计一个求解 Gray 码的分治策略，并编程实现（P39 算法分析题 2-14）。 （5） 设计求解半数集问题的算法，并编程实现。（P40算法实现题 2-3） （6） 设计求解整数因子分解问题的算法，并编程实现。 （P43 算法实现题 2-11） #include \ #include int number,result; int count=1; fin>>number;//输入整数 for(int i=2;i if(number%i==0) { result=number/i; //result 是因子 for(int i=2;i<=result;i++) { if(result%i==0) count++; } } } fout< （7） 设计求解双色 hanoi 问题的算法，并编程实现。 （P43 算法实现题 2-11） 注：至少选择其中 3 题完成 实验三 动态规划及其应用 （验证型、设计型实验 6 学时） 1.目的要求 （1） 理解动态规划算法的概念和基本要素，并能和分治法进行比较。 （2） 掌握设计动态规划算法的步骤，并编程实现有关算法。 （3） 理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反 复努力和重新修正的结果。 （4） 对设计好的算法，要分析算法的时间和空间复杂度。 2.实验内容 （1） 编程实现矩阵连乘问题的求解。 （P47） （2） 分别采用分治法和动态规划法求解实现最大子段和问题，并编程实现。（#include \ #include int MaxSubSum(int *a,int left,int right) //最大子段和 分治法 { int sum=0; if(left==right) sum=a[left]>0 ? a[left] :0; else { int center=(left+right)/2; int leftsum=MaxSubSum(a,left,center); int rightsum=MaxSubSum(a,center+1,right); int s1=0; int lefts=0; for(int i=center;i>=left;i--) { lefts+=a[i]; if(lefts>s1) s1=lefts; } int s2=0; int rights=0; for( i=center+1;i rights+=a[i]; if(right>s2)s2=rights; } sum=s1+s2; if(sum return sum; } P54） int MaxSumDongtai(int n,int *a) //最大子段和 动态规划法 //n 表示前 n 个数字 { int sum=0,b=0; for(int i=1;i<=n;i++) { if(b>0) b+=a[i]; else b=a[i]; if(b>sum) sum=b; } return sum; } void main() { int a[]={0,1,2,3,4,5,6,7}; int n; cout< cout< （3） 编程实现最长公共子序列(LCS)问题的求解。（4） 编程实现 0－1 背包问题的求解。 （P71）#include #define max(a,b) (((a) > (b)) ? (a) : (b)) //max(a,b) a,b 中的最大值 #define min(a,b) (((a) < (b)) ? (a) : (b)) //min(a,b) a,b 中的最小值 template void Knapsack(Type* v, int *w, int c, int n, Type **m) { //递归初始条件 //v 价值,w 重量,c 容量,n 件数,m 价值数 int jMax = min(w[n] - 1, c); for (int j=0; j<=jMax; j++) {//背包的重量 m[n][j] = 0; } P52） （