算法设计与分析实验报告完整版.doc-资料库

c42662f3-b78e-4ecd-9b1c-a24ff1b562e7.doc.pdf-第1页.png

第1页 / 共6页

c42662f3-b78e-4ecd-9b1c-a24ff1b562e7.doc.pdf-第2页.png

第2页 / 共6页

c42662f3-b78e-4ecd-9b1c-a24ff1b562e7.doc.pdf-第3页.png

第3页 / 共6页

c42662f3-b78e-4ecd-9b1c-a24ff1b562e7.doc.pdf-第4页.png

第4页 / 共6页

c42662f3-b78e-4ecd-9b1c-a24ff1b562e7.doc.pdf-第5页.png

第5页 / 共6页

c42662f3-b78e-4ecd-9b1c-a24ff1b562e7.doc.pdf-第6页.png

第6页 / 共6页

最大公约数实验：欧几里得算法： #include int CommonFactor(int m,int n) { int r=m%n; while(r!=0) { m=n; n=r; r=m%n; } return n; } void main() { int a,b; cout<<"请输入两个整数： "; cin>>a>>b; cout< int min(int a,int b) { return (a<=b? a:b); } int gcd(int m,int n) { int t; for( t=min(m,n);t>0;t--) { if(m%t==0 && n%t==0) return t; "; } "; } } } void main() { int a,b; cout<<"请输入两个整数： "; cin>>a>>b; cout< int decompose(int num, int p[]) { int i=2, count=0; while(i<=num){ while(num%i ==0){ p[count++]=i; num/=i; } i++; } return count; } int CommonFactor(int m, int n) { int a[100], b[100], c[100]; int la=decompose(m, a); int lb=decompose(n, b); int i=0, j=0, k=0; while(i>a>>b; cout< char S[100]={0},T[100]={0};//初始化 S[0]、 T[0]为 0 //BF 算法: int BF(char S[], char T[]) { int i=1,j=1,k=0; while(S[0]-i+1>=T[0]) { k=i; while(j<=T[0] && S[i]==T[j]) { } if(j>T[0])break;//如果 j>T[0]说明循环 while(j<=T[0] && S[i]==T[j]) 能进行到 j==T[0]&& S[i]==T[j],完全匹配,已找到所需的 i、j i++; j++; i=k+1; j=1; } if(j>T[0])return i-j+1; else return 0; } //KMP 算法: int next[100]={0}; void GetNext(char T[], int next[])

next[1]=0; int j=1,k=0; while(j=T[0])return T[0]; else return T[0]-i; { } } } int BM(char S[], char T[]) { int i=T[0],j; while(i<=S[0]) { j=T[0]; while(j>0 && S[i]==T[j]) { j=j-1; i=i-1; } if(j==0)return i+1; else i=i+dist(S[i]); } return 0; void main() { int returns; cout<<"请输入字符串 S:"<>(S+1); cout<<"请输入字符串 T:"<>(T+1); for(int i=1; S[i]!='\0'; i++) //'\0'表示字符串的结束符 S[0]++; for(int j=1; T[j]!='\0'; j++) T[0]++; /*BM 算法输出*/ cout<<"--------------->BF 算法运行结 cout<<" 找不到匹配字符 cout<<" 匹配字符串的起始下标: /*KMP 算法输出*/ cout<<"--------------->KMP 算法运行结果:"<BM 算法运行结 cout<<" 找不到匹配字符 cout<<" 匹配字符串的起始下标: 果:"< #include #define TRUE 1 #define FALSE 0 typedef struct Node { double x; double y; }Node; //坐标 typedef struct List { Node* data; int count; //点 //点的个数 }List; typedef struct CloseNode { Node a; Node b; double space; //计算距离的两个点 //距离平方 }CloseNode; int n; //点的数目

//输入各点到 List 中 void create(List &L) { cout<<"请输入平面上点的数目:\n"; cin>>n; L.count=n; L.data = new Node[L.count]; // 动态空间分配 cout<<"输入各点坐标 :x_y):"<>L.data[i].x>>L.data[i].y; } //求距离的平方 double square(Node a,Node b) { return ((a.x-b.x)*(a.x-b.x))+((a.y-b.y)*(a.y -b.y)); } //蛮力法 void BruteForce(const List &L,CloseNode &cnode,int begin,int end) { for(int i=begin;i<=end;++i) { for(int j=i+1;j<=end;++j) { double space=square(L.data[i],L.data[j]); if(space=0&&L.data[i].x>=(midX-d)) //在左边的 d 区域内 { j=mid; while(L.data[++j].x<=(midX+d)&&j<=L.c ount) { //在右边的 d 区域内 if(L.data[j].y<(L.data[i].y-d)||L.dat a[j].y>(L.data[i].y+d)) // 判断纵坐标是否在左边某固定点的 2d 区域内 continue; double space square(L.data[i],L.data[j]); = if(cnode.space>space) //在满足条件的区域内依次判断 { } cnode.a=L.data[i]; cnode.b=L.data[j]; cnode.space=space; //冒泡排序 void BubbleSort(Node r[],int length) { } --i; } } int change,n; n=length;change=TRUE; double b,c; for(int i=0;ir[j+1].x) { DivideConquer(const //分治法求最近对 void List &L,CloseNode &closenode,int begin,int end) { if(begin!=end) { int mid = (begin+end)/2; // 排列后的中间的那个点 b=r[j].x;c=r[j].y; double midX = L.data[mid].x; r[j].x=r[j+1].x;r[j].y=r[j+1].y; r[j+1].x=b;r[j+1].y=c; change=TRUE; } } DivideConquer(L,closenode,begin,mid); //继续在左半边用分治法求最近对 DivideConquer(L,closenode,mid+1,end); //继续在右半边用分治法求最近对 middle(L,closenode,mid,midX);

//判断左右各距中线 d 的区域，是否有最近对 } } void main() { //初始化 List list; CloseNode closenode; closenode.space = 10000; 点的距离 //最近 create(list); // 输入各点到 NList 中 cout<<"各点坐标为:"< int MaxSum1(int a[],int n){//蛮力法 int sum=0; int i,j,k; for(i=1;i<=n;i++){ int asum=0; for(j=i;j<=n;j++) { asum+=a[j]; if(asum>sum) { sum=asum; } } } return sum; } void main(){ "<>n; cout<<"请输入各元素的值："<>a[m]; maxsum=MaxSum(a,n,i,j); cout<<" 最大子段和是： "< int MaxSum(int a[],int left,int right)//分治法 { int sum=0; if (left==right) { if(a[left]>0) sum=a[left]; else sum=0; } else { int center=(left+right)/2; int leftsum=MaxSum(a,left,center); int rightsum=MaxSum(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(int j=center+1;j<=right;j++) { rights+=a[j]; if(rights>s2) s2=rights; } sum=s1+s2; if(sum>n; cout<<"请输入各元素的值："<>a[m]; maxsum=MaxSum(a,1,n);

cout<<" 最大子段和是： "< void MaxSum(int n,int a[])//动态规划法 { int sum=0; int b=0; for(int i=1;i<=n;i++) { if(b>0) else b+=a[i]; b=a[i]; if(b>sum) sum=b; } cout<<"最大子段和是："<< sum<>n; cout<<"请输入各元素的值："<>a[m]; MaxSum(n,a); //权重 float weight; int lchild,rchild,parent; }HTNode; void CreateHT(HTNode ht[], int n) { int i,j,k,lnode,rnode; float min1,min2; for(i=0; i<2*n-1; i++) 关域置初值-1 //所有结点的相 ht[i].parent=ht[i].lchild=ht.rchild=-1; //构造霍夫曼树 for(i=n;i<2*n-1;i++) { min1=min2=0xFFFF; lnode=rnode=-1; //lnode 和 rnode 为最小权重的两个 for(k=0;k<=i-1;k++) if(ht[k].parent==-1) //只在尚未构造二叉树的结点 { if(ht[k].weight int MaxSum(int a[], int len)//动态规划法 { int *b = new int[len]; b[0]=a[0]; for(int j=1; j0) b[j] = b[j-1]+a[j]; else b[j] = a[j]; if(msum < b[j]) msum = b[j]; } return msum; } void main(){ int a[]={5,1,6,-2,8,-10,2,20}; int s=MaxSum(a,8); cout<

} //装满背包 if(i<=n) } bound +=p[i]/w[i]*cleft; return bound; 左孩子结点左孩子结点 { if(ht[f].lchild==c) //当前结点是双亲结点的 hc.cd[hc.start--]=‘0’; else //当前结点是双亲结点的 hc.cd[hc.start--]=‘1’; c=f; f=ht[f].parent;// 再对 } hc.start++;//start 指向霍夫曼编双亲结点进行同样操作码最开始的字符 hcd[i]=hc; }//编码个数为 n 个 } //物品数 0/1 背包实验参考代码： double c; //背包容量 int n; double w[MAX]; double p[MAX]; double cw; double cp; double bestp; double knapsack(double pp[], double ww[], double cc, int len) { //当前重量 //当前价值 //当前最优价值 //物品重量数组 //物品价值数组 n=len; c=cc; cw=0.0; cp=0.0; bestp=0.0; //对各物品的重量进行排序，自己完成， //回溯搜索结果存入 p[],w[] backtrack(1); return bestp; } void backtrack(int i) { if(i>n) { //到达叶子结点 if(cp>bestp) bestp=cp; return; } //搜索子树 if(cw+w[i]<=c) { //进入左子树 cw+=w[i]; cp+=p[i]; backtrack(i+1); cw-=w[i]; cw-=p[i]; } if(cp+bound(i+1)>bestp) backtrack(i+1); //进入右子树 } double bound(int i) { //计算上界 double cleft=c-cw; //剩余容量 double bound=cp; //以物品单位重量价值递减顺序装入物品 while(i<=n && w[i]<=cleft) { cleft -= w[i]; bound+=p[i]; i++;

资料库

算法设计与分析实验报告完整版.doc

相关推荐

课程资源

热门标签

最新资料