[计算机软件及应用]算法设计与分析实验报告.doc
实验一 分治与递归（4学时）基本题一：基本递归算法一、实验目的与要求1、 熟悉C/C+语言的集成开发环境；2、 通过本实验加深对递归过程的理解二、实验内容：掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。三、实验题任意输入一个整数，输出结果能够用递归方法实现整数的划分。四、实验步骤1 理解算法思想和问题要求；2 编程实现题目要求；3 上机输入和调试自己所编的程序；4 验证分析实验结果；5 整理出实验报告。五、结果截图： 基本题二：棋盘覆盖问题一、实验目的与要求1、掌握棋盘覆盖问题的算法；2、初步掌握分治算法二、实验题： 盘覆盖问题：在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。三、实验提示void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; int t = tile+, / L型骨牌号 s = size/2; / 分割棋盘 / 覆盖左上角子棋盘 if (dr < tr + s && dc < tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc, dr, dc, s); else / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖右下角 boardtr + s - 1tc + s - 1 = t; / 覆盖其余方格 chessBoard(tr, tc, tr+s-1, tc+s-1, s); / 覆盖右上角子棋盘 if (dr < tr + s && dc >= tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s); else / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖左下角boardtr + s - 1tc + s = t; / 覆盖其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s); / 覆盖左下角子棋盘 if (dr >= tr + s && dc < tc + s) / 特殊方格在此棋盘中 chessBoard(tr+s, tc, dr, dc, s); else / 用 t 号L型骨牌覆盖右上角 boardtr + stc + s - 1 = t; / 覆盖其余方格 chessBoard(tr+s, tc, tr+s, tc+s-1, s); / 覆盖右下角子棋盘 if (dr >= tr + s && dc >= tc + s) / 特殊方格在此棋盘中 chessBoard(tr+s, tc+s, dr, dc, s); else / 用 t 号L型骨牌覆盖左上角 boardtr + stc + s = t; / 覆盖其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s); 四、结果截图提高题一：二分搜索一、实验目的与要求1、熟悉二分搜索算法；2、初步掌握分治算法；二、实验题1、设a0:n-1是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置I和大于x的最小元素位置j。当搜索元素在数组中时，I和j相同，均为x在数组中的位置。结果截图：2、设有n个不同的整数排好序后存放于t0:n-1中，若存在一个下标I，0in，使得ti=i，设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为O（logn）。结果截图：三、实验提示1、用I，j做参数，且采用传递引用或指针的形式带回值。bool BinarySearch(int a,int n,int x,int& i,int& j) int left=0; int right=n-1; while(left<right) int mid=(left+right)/2; if(x=amid) i=j=mid; return true; if(x>amid) left=mid+1; else right=mid-1; i=right; j=left; return false; int SearchTag(int a,int n,int x) int left=0; int right=n-1; while(left<right) int mid=(left+right)/2; if(x=amid) return mid; if(x>amid) right=mid-1; else left=mid+1; return -1; 提高题二： 用分治法实现元素选择一、实验要求与目的1、了解分治法的基本思想，掌握递归程序编写方法；2、使用分治法编程，求解线形序列中第k小元素。二、实验内容1、 给定线形序列集中n个元素和一个整数k，1kn，输出这n个元素中第k小元素的值及其位置。2、 简述该算法的原理、步骤。对该算法与直接排序查找进行比较。3、 编写并调试程序。测试要求：元素个数不少于100；分三种情况：k=1、k=n和k=中位数。#include<iostream>using namespace std;/递归实现的函数int q(int n,int m)if(m<1|n<1)return 0;if(n=1|m=1)/int i=1;/cout<<n<<"=1"/for(;i<n;i+)/cout<<"+1"/cout<<endl;return 1;if(n<m)return q(n,n);/最大的加数不可能大于nif(n=m)/cout<<n<<"="<<n<<endl;return q(n,m-1)+1;/多一种被分解数的本身这种情况return q(n,m-1)+q(n-m,m);/cout<<n<<"="<<int main()int m;cout<<"请输入要划分的正整数："cin>>m;cout<<"划分的个数为"<<q(m,m)<<endl;return 0;/*该程序中为了输入输出的格式方便控制，在输出时采用了c语言的printf函数进行输出*/#include<iostream>using namespace std;int Board130130;/Board为棋盘数组，k小于等于7int tile=1;/定义骨牌号void ChessBoard(int tr,int tc,int dr,int dc,int size)/将四为2k(size)的棋盘覆盖/tr,tc为棋盘的左上角方格所在的坐标，dr，dc为特殊方格所在的位置坐标 if (size = 1) return; int t = tile+, / L型骨牌号 s = size/2; / 分割棋盘 / 覆盖左上角子棋盘 if (dr < tr + s && dc < tc + s) / 特殊方格在此棋盘中 ChessBoard(tr, tc, dr, dc, s); else / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖右下角 Boardtr + s - 1tc + s - 1 = t; / 覆盖其余方格 ChessBoard(tr, tc, tr+s-1, tc+s-1, s); / 覆盖右上角子棋盘 if (dr < tr + s && dc >= tc + s) / 特殊方格在此棋盘中 ChessBoard(tr, tc+s, dr, dc, s); else / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖左下角Boardtr + s - 1tc + s = t; / 覆盖其余方格 ChessBoard(tr, tc+s, tr+s-1, tc+s, s); / 覆盖左下角子棋盘 if (dr >= tr + s && dc < tc + s) / 特殊方格在此棋盘中 ChessBoard(tr+s, tc, dr, dc, s); else / 用 t 号L型骨牌覆盖右上角 Boardtr + stc + s - 1 = t; / 覆盖其余方格 ChessBoard(tr+s, tc, tr+s, tc+s-1, s); / 覆盖右下角子棋盘 if (dr >= tr + s && dc >= tc + s) / 特殊方格在此棋盘中 ChessBoard(tr+s, tc+s, dr, dc, s); else / 用 t 号L型骨牌覆盖左上角 Boardtr + stc + s = t; / 覆盖其余方格 ChessBoard(tr+s, tc+s, tr+s, tc+s, s); int main()int size=0,dr=0,dc=0;cout<<"请输入棋盘每一条边数的方格："cin>>size;cout<<"请输入特殊方格所在的位置坐标（第一个方格的坐标为0）："<<endl;cout<<" 请输入横坐标："cin>>dc;cout<<" 请输入纵坐标："cin>>dr;Boarddrdc=-1;cout<<"以下为棋盘的初始状态，0表示没有覆盖，-1表示特殊方格所在的位置:"<<endl;int i=0,j=0;for(i=0;i<size;i+)for(j=0;j<size;j+)printf("%3d",Boardij);cout<<endl;ChessBoard(0,0,dr,dc,size);cout<<"以下为棋盘的覆盖后的状态，0表示没有覆盖，-1表示特殊方格所在的位置，正整数表示骨牌号:"<<endl;for(i=0;i<size;i+)for(j=0;j<size;j+)printf("%3d",Boardij);cout<<endl;return 0;#include<iostream>using namespace std; void BubbleSort(int* pData,int Count)/冒泡排序的函数，pData中从0位置处存了Count个数， 该函数将数组中元素排为升序 int iTemp; for(int i=1;i<Count;i+) for(int j=Count-1;j>=i;j-) if(pDataj<pDataj-1) iTemp = pDataj-1; pDataj-1 = pDataj; pDataj = iTemp; bool BinarySearch(int a,int n,int x,int& i,int& j)/数组a大小为n，数组中存放了已经排好序（升序）的数列 int left=0; int right=n-1;int mid=0; while(left<right) mid=(left+right)/2; if(x=amid) i=j=mid; return true; if(x>amid) left=mid+1; else right=mid-1; i=right; j=left; return false; /*int SearchTag(int a,int n,int x) int left=0; int right=n-1; while(left<right) int mid=(left+right)/2; if(x=amid) return mid; if(x>amid) right=mid-1; else left=mid+1; return -1;*/int main()int a100;cout<<"请输入数组中数的个数，小于100:"int num=0;cin>>num;cout<<"请输入数组中的数："<<endl;for(int i=0;i<num;i+)cin>>ai;/下面将数组a排成升序BubbleSort(a,num);cout<<"下面输出排序后的数组："<<endl;for(i=0;i<num;i+)printf("%4d",ai);cout<<endl;cout<<"请输入要查找的数:"int x=0;cin>>x;int j=0;if(BinarySearch(a,num,x,i,j)cout<<"找到了，位置为"<<i<<endl;elsecout<<"没找到,小于该数的最大元素位置为"<<i<<"大于该数的最小元素的位置为"<<j<<"（第一个元素的位置为0）"<<endl;return 0;#include<iostream>using namespace std; /*根据题目中的隐含要求，现在将问题进行简化，假设数组中存放的数全部为整数*/void BubbleSort(int* pData,int Count)/冒泡排序的函数，pData中从0位置处存了Count个数， 该函数将数组中元素排为升序 int iTemp; for(int i=1;i<Count;i+) for(int j=Count-1;j>=i;j-) if(pDataj<pDataj-1) iTemp = pDataj-1; pDataj-1 = pDataj; pDataj = iTemp; bool BinaryFind_iei(int a,int n,int& i)/数组a大小为n，数组中存放了已经排好序（升序）的数列 int left=0; int right=n-1;int mid=0; while(left<right) mid=(left+right)/2; if(mid=amid) i=mid; return true; /找到了 elseif(mid>amid)left=mid;elseright=mid; return false; /*int SearchTag(int a,int n,int x) int left=0; int right=n-1; while(left<right) int mid=(left+right)/2; if(x=amid) return mid; if(x>amid) right=mid-1; else left=mid+1; return -1;*/int main()int a100;cout<<"请输入数组中数的个数，小于100:"int num=0;cin>>num;cout<<"请输入数组中的数："<<endl;for(int i=0;i<num;i+)cin>>ai;/下面将数组a排成升序BubbleSort(a,num);cout<<"下面输出排序后的数组："<<endl;for(int i=0;i<num;i+)printf("%4d",ai);cout<<endl;int j=0;if(BinaryFind_iei(a,num,j)cout<<"找到了，位置为"<<j<<endl;elsecout<<"不存在符合第i个位置等于i的元素。"<<endl;return 0;实验二 动态规划算法（4学时） 基本题一：最长公共子序列问题一、实验目的与要求1、熟悉最长公共子序列问题的算法；2、初步掌握动态规划算法；二、实验题 若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk，是X的子序列是指存在一个严格递增下标序列i1,i2,ik使得对于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相应的递增下标序列为2，3，5，7。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。 三、实验提示include "stdlib.h"#include "string.h" void LCSLength(char *x ,char *y,int m,int n, int *c, int *b) int i ,j; for (i = 1; i <= m; i+) ci0 = 0; for (i = 1; i <= n; i+) c0i = 0; for (i = 1; i <= m; i+) for (j = 1; j <= n; j+) if (xi=yj) cij=ci-1j-1+1; bij=1; else if (ci-1j>=cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; void LCS(int i ,int j, char *x ,int *b) if (i =0 | j=0) return; if (bij= 1) LCS(i-1,j-1,x,b); printf("%c",xi); else if (bij= 2) LCS(i-1,j,x,b); else LCS(i,j-1,x,b);四、实验结果截图基本题二：最大字段和问题 一、实验目的与要求1、熟悉最长最大字段和问题的算法；2、进一步掌握动态规划算法；二、实验题 若给定n个整数组成的序列a1，a2，a3，an，求该序列形如aiai1an的最大值。三、实验提示int MaxSum(int n,int *a,int &besti,int &bestj) intsum=0; for(int i=1;i<=n;i+) for(int j=i;j<=n;j+) int thissum=0; for(int K=i;k<=j;k+)thissum+=ak; if(thissum>sum) sum=thissum; besti=i; bestj=j; return sum; int MaxSum(int n,int *a,int &besti,int &bestj) intsum=0; for(int i=1;i<=n;i+) int thissum=0; for(intj=i;j<=n;j+) thissum+=aj; if(thissum>sum) sum=thissum; besti=i; bestj=j; return sum; 四、实验结果截图提高题一： 用动态规划法求解0/1背包问题一、实验要求与目的1、 掌握动态规划算法求解问题的一般特征和步骤。2、 使用动态规划法编程，求解0/1背包问题。二、实验内容1、 问题描述：给定n种物品和一个背包，物品i的重量是Wi，其价值为Vi，问如何选择装入背包的物品，使得装入背包的物品的总价值最大？2、 算法描述。3、 程序实现；给出实例测试结果。二、实验结果截图#include<iostream>using namespace std;/构造最大子序列，完成之后，最大子序列信息存放在数组c中，构造方法存在b中void LCSLength(char *x ,char *y,int m,int n, int c100, int b100) int i ,j; for (i = 0; i <= m; i+) ci0 = 0; for (i = 0; i <= n; i+) c0i = 0; for (i = 1; i <= m; i+) for (j = 1; j <= n; j+) if (xi=yj) cij=ci-1j-1+1; bij=1; else if (ci-1j>=cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; /下面构造最长子序列void LCS(int i ,int j, char *x ,int b100) if (i =0 | j=0) return; if (bij= 1) LCS(i-1,j-1,x,b); printf("%c",xi); else if (bij= 2) LCS(i-1,j,x,b); else LCS(i,j-1,x,b);int main()int m,n;cout<<"请输入第一个序列b1的长度："cin>>m;cout<<"请输入第二个序列b2的长度："cin>>n;char *b1=new charm+1;char *b2=new charn+1;if(b1=NULL|b2=NULL)cout<<"meiyouchenggongfenpei"<<endl;cout<<"输入第一个序列："<<endl;b10=b20='0'int i=0;for(i=1;i<=m;i+)cout<<" 请输入第一个序列b1的第"<<i<<"个字符:"cin>>b1i;cout<<"输入第二个序列："<<endl;for(i=1;i<=n;i+)cout<<" 请输入第二个序列b2的第"<<i<<"个字符:"cin>>b2i;int c100100,b100100;LCSLength(b1,b2,m,n,c,b);/void LCSLength(char *x ,char *y,int m,int n, int *c, int *b)cout<<"最长公共子序列的长度为"<<cmn<<endl;LCS(m,n,b1,b);/void LCS(int i ,int j, char *x ,int *b)delete b1;delete b2;cout<<endl;return 0;#include<iostream>using namespace std;int MaxSum(int n,int *a)int sum=0,b=0;for(int i=1;i<=n;i+)if(b>0)b=b+ai;elseb=ai;if(b>sum)sum=b;return sum;int main()cout<<"请输入整数序列a的长度:"int l;cin>>l;int *a=new intl+1;if(l=NULL)cout<<"chucuole,hheh."<<endl;return 0;a0=0;for(int i=1;i<=l;i+)cout<<"请输入整数序列的第"<<i<<"个元素："cin>>ai;cout<<"最大字段和为"<<MaxSum(l,a)<<endl;delete a;return 0;#include<iostream>using namespace std;int MaxSum(int n,int *a)int sum=0,b=0;for(int i=1;i<=n;i+)if(b>0)b=b+ai;elseb=ai;if(b>sum)sum=b;return sum;int main()cout<<"请输入整数序列a的长度:"int l;cin>>l;int *a=new intl+1;if(l=NULL)cout<<"chucuole,hheh."<<endl;return 0;a0=0;for(int i=1;i<=l;i+)cout<<"请输入整数序列的第"<<i<<"个元素："cin>>ai;cout<<"最大字段和为"<<MaxSum(l,a)<<endl;delete a;return 0;#include<iostream>using namespace std;int min(int x,int y)return x>y?y:x;int max(int x,int y)return x>y?x:y;void Knapsack(int *v,int *w,int c,int n,int m100)int jMax=min(wn-1,c);for(int j=0;j<=jMax;j+)mnj=0;for(int j=wn;j<=c;j+)mnj=vn;int i=n-1;for(i=n-1;i>1;i-)jMax=min(wi-1,c);int j=0;for(j=0;j<=jMax;j+)mij=mi+1j;for(j=wi;j<=c;j+)mij=max(mi+1j,mi+1j-wi+vi);m1c=m2c;if(c>=wi)m1c=max(m1c,m2c-wi+v1);void traceback(int m100,int *w,int c,int n,int *x)for(int i=1;i<n;i+)if(mic=mi+1c)xi=0;elsexi=1;c=c-wi;xn=mnc?1:0;int main()cout<<"请输入背包容量C："int c=0;cin>>c;cout<<"请输入待放物体的个数:"int n;cin>>n;int *v=new intn+1;int *w=new intn+1;int *x=new intn+1;if(x=NULL|w=NULL|v=NULL)cout<<"meiyou chenggong fenpei,hehe"<<endl;return 0;/Knapsack(int *v.int *w,int c,int m100)/viod traceback(int m100,int *w,int c,int n,int *x)cout<<"请输入待放物体的价值和重量信息："<<endl;int i=0;for(i=1;i<=n;i+)cout<<" 第"<<i<<"个物体的价值: "cin>>vi;cout<<" 第"<<i<<"个物体的重量:"
