longest_common_sub-sequence.rar_sub_最长子序列

#include <stdio.h> #include <time.h> #include <stdlib.h> #define MAX 100 #define MAX1 1000 #define MAX2 3000 #define MAX3 10000 static int temp[MAX3]; static int length = 0; ////////////////////////////////////////////////////////////////// //////////////////////*法一：转化为LCS问题求解*/////////////////// //////////////////////比较原序列与排好序的序列的LCS即可/////////// void lcs_length(int *x , int *y , int *b,int xlen,int ylen) { int i,j,k; int c[MAX][MAX]; for(i=0;i<=xlen;i++) c[i][0] = 0; for(j=0;j<=ylen;j++) c[0][j] = 0; for(i=0;i<=xlen;i++) for(j=0;j<=ylen;j++) { if(x[i] == y[j]) { c[i][j] = c[i-1][j-1] + 1; k = i*(ylen+1) + j; b[k] = 1; //表示斜上 } else if(c[i-1][j] >= c[i][j-1]) { c[i][j] = c[i-1][j]; k = i*(ylen+1) + j; b[k] = 2; //表示向上 } else { c[i][j] = c[i][j-1]; k = i*(ylen+1) + j; b[k] = 3; //表示向左 } } } void LCS(int *b,int *x,int i,int j,int t) { int k; if(i == -1 || j == -1) return ; k = i*(t+1) + j; if(b[k] == 1) { LCS(b,x,i-1,j-1,t); temp[length++] = x[i]; } else if(b[k] == 2) LCS(b,x,i-1,j,t); else LCS(b,x,i,j-1,t); } void QuickSort(int *a,int l,int h)//递归的快速排序 { int i,j; int sep,t; i = l; j = h; sep = a[(l+h)/2]; do { while (a[i]<sep) i++; while (a[j]>sep) j--; if(i<=j) { t=a[i]; a[i++]=a[j]; a[j--]=t; } }while (i<=j); if(l<j) QuickSort(a,l,j); if(i<h) QuickSort(a,i,h); return; } ///////////////////////////////////////////////////////////// /////////////////////法二：动态规划法/////////////////////// int DymLis(int x[],int xlen) //返回LIS的个数 { int Len = 1; int up,low,mid; //二分查找的上下界与中点 int tt[MAX3] ; //中间存储lis的数组 int i; tt[0] = 0; tt[1] = x[0]; for(i=0; i< xlen; i++) { up = 0; low = Len; while(up <= low) { mid = (up + low)/2 ; if(tt[mid] < x[i]) up = mid + 1; else low = mid - 1; } tt[up] = x[i]; if(up > Len) Len++ ; } for(i=0; i< Len ; i++) temp[i] = tt[i+1]; return Len; } void copyArray(int x[],int y[],int length) //将x数组前面长length的部分复制给y { for(int i=0;i<length;i++) y[i] = x[i]; return; } //////////////////////////////// int main() { /////////////declaration////////// int x1[MAX1],x2[MAX2],x3[MAX3]; int b[MAX] = {0}; int i; int *p; //////////initialize all the arrays/////// srand(time(0)); for(i=0;i<MAX1;i++) x1[i] = (rand()+1)%(MAX1+1); for(i=0;i<MAX2;i++) x2[i] = (rand()+1)%(MAX2+1); for(i=0;i<MAX3;i++) x3[i] = (rand()+1)%(MAX3+1); printf("注释：此次实验做出了两种方法，最长公共子序列方法与动态规划方法。如果使用前者，而序\ 列较大的话，所需的二维数组会很大，而此时内存是无法在栈内给其分配空间的，所以只能能过读写文\ 件来实现大数组的情况，在此没有做此项功能，只简单实现在最长公共子序列的方法，下以｛1，4，6，9，\ 3，2，11，5，10｝为例测试其是否成功\n\ 因为第二种动态规划的方法更简便，时间复杂度更小，为O(nlgn)，而且不存大需要较大数组的情况！\n\n\ \n"); printf("////////////Method by LCS(Longest Common Subsequence)--smart Test////////////"); int x[10] = {4,1,6,9,3,2,11,5,10,8}; printf("\n\nThe Original Sequence is： "); for(i=0;i<10;i++) printf("%d ",x[i]); printf("\nIts LIS is： "); int y[10] ; copyArray(x,y,10); QuickSort(y,0,9); lcs_length(x,y,b,10,10); LCS(b,x,10,10,10); length--; int lisx[length]; copyArray(temp,lisx,length); for(i=0;i<length;i++) printf("%d ",lisx[i]); printf("\n///////////////Dynamic Programming---By binary searching Method///////////\n\n"); printf("Generate three random arrays，respectively, n = 1000,3000,10000\n\ Every Longest Increasing Subsequence of them is as followings:\n"); printf("n=1000:\n\t"); int len1 = DymLis(x1,MAX1); int ll1[len1]; copyArray(temp,ll1,len1); for(i=0;i<len1;i++) printf("%d ",ll1[i]); printf("\n\nn=3000:\n\t"); int len2 = DymLis(x2,MAX2); int ll2[len2]; copyArray(temp,ll2,len2); for(i=0;i<len2;i++) printf("%d ",ll2[i]); printf("\n\nn=10000:\n\t"); int len3 = DymLis(x3,MAX3); int ll3[len3]; copyArray(temp,ll3,len3); for(i=0;i<len3;i++) printf("%d ",ll3[i]); printf("\n\n"); printf("Press any button to end...\n"); char c = getchar(); return 0; }