当前位置: 首页 > news >正文

网站 网络架构/互联网营销推广方案

网站 网络架构,互联网营销推广方案,网站开发招标采购需求,关于未备案网站今天是2012年12月22日。今天的算法练习题是最长公共子序列的长度求解。此题初看时,感觉问题非常复杂,要求解两个序列的最长的(可以不连续)的公共子序列。但是,"将复杂的问题分解成简单的问题"是基本的程序设计思想。分治法是将一个…
         今天是2012年12月22日。今天的算法练习题是最长公共子序列的长度求解。
         此题初看时,感觉问题非常复杂,要求解两个序列的最长的(可以不连续)的公共子序列。但是,"将复杂的问题分解成简单的问题"是基本的程序设计思想。分治法是将一个大问题分解成多个相似的小问题,而本题采用的动态规划算法,则是将复杂的问题分解成一系列的相似的子问题。另外,将所求解的子问题的解通过数组等容器保存起来,来节省重复求解相同子问题的时间,是动态规划算法的一个很重要的思想:备忘录思想。
         另外,本题还将采用逆向的思路,这与常规的顺序的思路相悖。str1[a],str2[b]两个字符串,不是从左至右的考虑,而是从右至左的方向。
         分析过程如下:
         str1[a],str1[b]是待求最长公共子序列的两个字符串,假设result[c]就是其最长公共子序列。
         那么就有以下3种情况。
         1.如果str1[a-1]==str2[b-1],那么肯定有result[c-1]=str1[a-1]=str2[b-1],即最后一个元素一定是最长公共子序列的一部分。那么,就可以不再考虑str1[a-1],str2[b-1],result[c-1],从他们之前的元素开始讨论,也就是意味着,result[c-2]及之前的元素就是str1[a-2]之前的元素与str[b-2]之前的元素的最长公共子序列。
         2.如果str1[a-1]!=str2[b-1],而且result[c-1]!=str1[a-1],那么就可以肯定,str1[a-1]不在最长公共子序列中,也就是说,result[c-1]及之前的元素就是str1[a-2]之前的元素与str2[b-1]之前的元素的最长公共子序列。
         3.如果str1[a-1]!=str2[b-1],而且result[c-1]!=str2[b-1],类似的,就可以肯定,str1[b-1]不在最长公共子序列中,也就是说,result[c-1]及之前的元素就是str1[a-1]之前的元素与str2[b-2]之前的元素的最长公共子序列。
         由此,可以得到递归方程。(ps:我不知道在这里如何插入公式,如果您知道,请告诉小弟我,非常感谢!)
         max_len[i][j]=0                                      如果i<=0 || j<=0     (当一个序列长度为0时,也就没有意义)
                            =1 +max_len[i-1][j-1]         如果str1[i-1]==str2[j-1]      (对应上面第1种情况)
                            =MAX(max_len[i-1][j],max_len[i][j-1])   如果str1[i-1]!=str2[j-1]     (对应上面第2,3种情况)
         思路已经很清晰了,代码如下:
最长公共子序列
 1 #include <stdio.h>2 #include <string.h>3 #define MAX 1004 5 int max(int num1,int num2);6 7 //记录a[i],b[j]的最长公共子序列的长度8 int max_len[MAX+2][MAX+2]={0};9 
10 char a[MAX]="abcde";
11 char b[MAX]="afffbcde";
12 
13 int main()
14 {
15     int len_a=strlen(a);
16     int len_b=strlen(b);
17     int result_max=0;
18     int i,j;
19     LCS(len_a,len_b); 
20     for(i=1;i<=len_a;i++)
21     {
22         for(j=1;j<=len_b;j++) 
23         {
24             if(result_max<=max_len[i][j]) 
25                 result_max=max_len[i][j];
26         }
27     }
28     printf("result: %d\n",result_max);
29     return 0;
30 }
31 
32 int LCS(int m,int n)
33 {
34     if(m<=0 || n<=0)
35         return 0;
          else if(max_len[m][n]!=0)return max_len[m][n];
36     else if(a[m-1]==b[n-1])
38         return (max_len[m][n]=LCS(m-1,n-1)+1);
40     else
41         return (max(LCS(m,n-1),LCS(m-1,n)));
42 }
43 
44 int max(int num1,int num2)
45 {
46     return (num1>num2?num1:num2);
47 }
 明天得把具体的最长公共子序列给打印出来。
         以下内容补充于2012年12月23日:
          昨天留了个问题,就是打印出最长公共子序列。想了一会,没什么思路,就索性把max_len给打印出来,结果一打印我才发现,我把问题想得太复杂了。这本是一个多么简单的问题。
          比如str1="abbcd";  str2="afffbcd";  那么打印出max_len:
?
1 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 2 0 0
0 0 0 0 0 3 0
0 0 0 0 0 0 4
一目了然了。当且仅当str1[a-1]==str2[b-1]时,肯定会使得max_len中对应元素加1.
       在程序中加一步就可以了。如下:
1  for(i=1;i<=len_a;i++)
2     {
3         for(j=1;j<=len_b;j++) 
4         {
5             if(max_len[i][j]!=0)
6                 printf("%c ",a[i-1]);
7         }
8     }
如果您觉得我的文章对您有所帮助,请赞一下,非常感谢!   
本文转自NeilHappy 51CTO博客,原文链接:http://blog.51cto.com/neilhappy/1097226,如需转载请自行联系原作者
http://www.jmfq.cn/news/4745467.html

相关文章:

  • 福州建设银行官网招聘网站/销售网站有哪些
  • 四川建筑信息数据共享平台/常州百度搜索优化
  • 小工厂怎么做网站/想要导航页面推广app
  • 做快递网站难吗/郴州网站建设推广公司
  • 个人如何建立公司网站/信阳网络推广公司
  • 个人可以做自媒体网站吗/网站推广seo优化
  • 404错误直接转向到网站首页/百度总部客服电话
  • 广州翼讯资讯科技有限公司 网站/深圳搜索引擎
  • 常州外贸网站制作/全网优化哪家好
  • 微服务网站/磁力天堂最新版地址
  • 网站制作建设公司/怎么做小程序
  • 厦门自助建站/上海seo优化外包公司
  • 一个云主机可以做多少网站/百度一下官网首页百度
  • 惠州市网站设计公司/抚顺优化seo
  • 建设网站和公告号的意义/汕头seo收费
  • 建网站开发费用/seo搜索排名
  • 网站客服悬浮/效果最好的推广软件
  • 怎样弄网站/整合营销传播工具有哪些
  • 网站源码在线下载/商旅平台app下载
  • 怎么做私服网站/上海最新发布
  • 黔西南州党风廉政建设网站/打开百度浏览器
  • 河津网站建设/南京seo建站
  • 长春自助建站软件/今日最新重大新闻
  • asp.net网站开发详解/seo推广有哪些公司
  • 专业柳州网站建设价格/如何在百度做免费推广产品
  • 军事网站模板/查询关键词
  • 如何做网站首页的psd图/河南seo优化
  • html对于网站/郑州网站建设优化
  • 鲜花店网站建设的规模设想/新软件推广平台
  • 注册网站的流程/自己的网站怎么推广