算法设计与分析实验报告

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 #include ifstream fin(\ ofstream fout(\ using namespace std; void main() {

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 using namespace std;

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 #include \ #include using namespace std;

#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） （