欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C++动态规划实现查找最长公共子序列

程序员文章站 2022-06-12 23:51:15
具体内容之后再补_(:з」∠)_先贴代码 ......

具体内容之后再补_(:з」∠)_先贴代码

  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 }