C++动态规划实现查找最长公共子序列
2019-10-31 16:01:19来源:博客园 阅读 ()
C++动态规划实现查找最长公共子序列
具体内容之后再补_(:з」∠)_先贴代码
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 }
原文链接:https://www.cnblogs.com/Jesse-Cavendish/p/11771500.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++ 转换函数搭配友元函数 2020-06-10
- C++ 自动转换和强制类型转换(用户自定义类类型) 2020-06-10
- C++ rand函数 2020-06-10
- C++ 友元函数 2020-06-10
- C++ 运算符重载 2020-06-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash