C++动态规划实现查找最长公共子序列
程序员文章站
2023-11-08 17:33:40
具体内容之后再补_(:з」∠)_先贴代码 ......
具体内容之后再补_(:з」∠)_先贴代码
1 #include<cstdio> 2 #include<cstring> 3 #include<stack> 4 #include<ctime> 5 #include<iostream> 6 #include<fstream> 7 #include<algorithm> 8 #include<windows.h> 9 using namespace std; 10 large_integer nfreq;//large_integer在64位系统中是longlong,在32位系统中是高低两个32位的long,在windows.h中通过预编译宏作定义 11 large_integer nbegintime;//记录开始时的计数器的值 12 large_integer nendtime;//记录停止时的计数器的值 13 #define n 10000 14 //const int size_char = 10000; //生成32 + 1位c style字符串 15 const char cch[] = "_0123456789abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz_"; 16 int dp[n][n]; 17 char c; 18 int main(void) 19 { 20 //char a[n]; 21 //char b[n]; 22 //char a[size_char+2]; 23 //char b[size_char+2]; 24 ofstream fout; 25 int m = 0,i = 0; 26 int size_char; 27 cout<<"please enter the number of times you want to run the program:"; //输入程序运行次数 28 cin>>m; 29 //int size[m]; 30 double cost; 31 //double runtime[m]; 32 srand((unsigned)time(null)); 33 fout.open("data.txt",ios::app); 34 if(!fout){ 35 cerr<<"can not open file 'data.txt' "<<endl; 36 return -1; 37 } 38 fout.setf(ios_base::fixed,ios_base::floatfield); //防止输出的数字使用科学计数法 39 for(i = 0; i < m; i++){ 40 //size_char=10000+rand_max*(rand()%300)+rand(); //rand_max=32767,随机生成数据量 41 size_char = rand() % 10000; 42 fout<<size_char<<","; 43 // size[i]=size_char; //限定数据规模为10000~9872867 44 char a[size_char + 1] = {'\0'}; 45 char b[size_char + 1] = {'\0'}; 46 cout<<"☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆the "<<i+1<<"th test's string size is:"<<size_char<<"☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆"<<endl; 47 for (int i = 0; i < size_char; ++i){ 48 int x = rand() / (rand_max / (sizeof(cch) - 1)); 49 a[i] = cch[x]; 50 } 51 cout<<"the first random sting is:" <<a <<endl; 52 for (int i = 0; i < size_char; ++i){ 53 int x = rand() / (rand_max / (sizeof(cch) - 1)); 54 b[i] = cch[x]; 55 } 56 cout<<"the second random string is:" <<b <<endl; 57 cout<<"the longest common subsequence is:"; 58 queryperformancefrequency(&nfreq);//获取系统时钟频率 59 queryperformancecounter(&nbegintime);//获取开始时刻计数值 60 int la=strlen(a); 61 int lb=strlen(b); 62 memset(dp,0,sizeof(dp)); 63 for(int i=1; i<=la; i++){ 64 for(int j=1; j<=lb; j++){ 65 if(a[i-1]==b[j-1]) 66 dp[i][j]=dp[i-1][j-1]+1; 67 else 68 dp[i][j]=max(dp[i-1][j],dp[i][j-1]); 69 } 70 } 71 int i=la,j=lb; 72 stack<char>s; 73 while(dp[i][j]){ 74 if(dp[i][j]==dp[i-1][j]){//来自于左方向 75 i--; 76 } 77 else if(dp[i][j]==dp[i][j-1]){//来自于上方向 78 j--; 79 } 80 else if(dp[i][j]>dp[i-1][j-1]){//来自于左上方向 81 i--; 82 j--; 83 s.push(a[i]); //压栈以便倒序输出 84 } 85 } 86 while(!s.empty()) 87 { 88 c=s.top(); 89 printf("%c",c); 90 s.pop(); 91 } 92 cout<<endl; 93 queryperformancecounter(&nendtime);//获取停止时刻计数值 94 cost=(double)(nendtime.quadpart - nbegintime.quadpart) / (double)nfreq.quadpart; 95 fout<<cost<<endl; 96 //runtime[i]=cost; 97 cout<<"the running time is:"<<cost<<" s"<<endl; 98 } 99 fout.close(); 100 cout<<"success!"<<endl; 101 return 0; 102 }
上一篇: 桑葚要涨价!桑葚多少钱