您身边的网站建设专家
日期： 2022-09-20 15:11:48 浏览数：3
上往建站提供服务器空间服务商，百度快照排名，网站托管，百度推广运营,致力于设计外包服务与源代码定制开发，360推广，搜狗推广,增加网站的能见度及访问量提升网络营销的效果,主营：网站公司,百度推广公司电话,官网搭建服务,网站服务企业排名,服务器空间,英文域名等业务，专业团队服务，效果好。
定州申请400电话费用【定州企业全国热线电话办理】定州开通400电话电信价格、定州微信公众号代运营外包托管、定州网店编辑装修美工、定州网站推广优化大概需要多少钱
定州市，河北省辖县级市，由保定市代管， [1] 是河北省省直管县（市）体制改革试点县（省直管县行政区划隶属关系不变 [2] ）， [3-4] 是全省重点培育的新兴区域中心城市。连续4年获评全国中小城市投资潜力百强、新型城镇化质量百强，晋级全国科技创新百强，入围全国县域经济强县。面积1283平方公里，截至2019年，定州市常住总人口123.09万人，辖25个乡镇（办），542个村（社区）。 [5-6]
定州市位于京津冀经济区，是京津冀经济区重要节点城市 [7] ，国家新型城镇化综合试点地区 [8] ，河北省十二五规划重点培育的现代化中等城市 [9] ，河北省十大历史文化名城之一。
2019年，定州市户籍总户数37.3万户，户籍总人口124.1万人，比上年增加0.3万人。常住总人口123.09万人，比上年末增加0.4万人。 [6] 2019年，定州市生产总值实现3330429万元，比上年增长7.1%。按常住人口计算，定州市人均地区生产总值为27101元。 [6] 2020年9月，入选河北省食品产业强县（市、区）（培育型）名单。 [10] 2020年12月，入选河北省数字乡村试点地区名单。
命题S(k)。如果在第i 行第 j 列，其中i+j=k，而且有L(i , j )=v，我们随后就会在LCS中找到v 个元素。
依据。依据是k=0的情况。如果i+j=0，那么i 和 j 都为0。我们已经完成了路径，并发现LCS不会有更多元素。因为已经知道L(0,0)=0，所以归纳假设对i+j=0成立。
归纳。假定对k 或更小的和的归纳假设成立，并令i+j=k+1。假设我们在值为v 的L(i , j )处。如果ai=bj，就找到了匹配并移动到L(i-1, j-1)。因为(i-1）+（j-1)的和小于i+1，所以归纳假设是适用的。因为L(i-1, j-1)一定是v-1，所以我们知道LCS还将找到v-1个元素，再加上已经找到的一个元素，就会给我们v 个元素。这一直观结果证明了这种情况下的归纳假设。
唯一的例外是ai ≠bj 的情况。这种情况下，L(i-1, j )或L(i , j-1)，或者这两者，一定具有值v，而且我们要移动到具有值v 的这些位置之一。因为任一情况下行列值的和都是i+j-1，所以归纳假设是适用的，这样就能得出在LCS中找到v 个元素的结论。这样我们又能得出S(k+1)为真的结论。因为已经考虑了所有的情况，所以就完成了证明，并可以说如果在数据项L(i , j )处，就总是在LCS找出L(i , j )个元素。
1. 下列表的LCS的长度各为多少？
(a) banana和cabana
(b) abaacbacab和bacabbcaba
2. * 找到习题1两个小题中两个表的所有LCS。提示：在为习题(1)构建二维表之后，从右上角往回追溯，在遇到有两条或三条不同路径的点时，要顺着每种选择继续移动。
3. ** 假设使用我们最先描述的递归算法而不是推荐的填表程序计算LCS。如果对两个没有共同符号的表调用L(4,4)，要执行多少次对L(1,1)的调用？提示：使用填表（动态规划）算法计算二维表，给出对应所有i 和 j 的L(i , j )的值。将计算结果与4.5节中的帕斯卡三角相比较。这一关系表示了与调用次数的公式有关的哪些信息？
4. ** 假设有表x 和表y，且二者的长度均为n。当n 小到一定程度之后，就最多只有一个字符串是x 和y 的LCS了，虽然该字符串可能出现在x 和/或y 的不同位置。例如，如果n=1，那么LCS只能是ε，除非x 和y 都是同一个符号a，这种情况下a 就是唯一的LCS。那么，让x 和y 可以有两个不同LCS的最小n 值是多少？
5. 证明图6-31所示的程序运行时间为 O(mn) 。
6. 编写C语言程序，接受图6-31所示程序计算出的那种表，并找出LCS在各字符串中的位置。如果该表的规格为m×n，那么这一程序的运行时间是多少？
7. 在6.9节开头，我们表示过LCS的长度是与两个字符串最大位置匹配的大小有关的。
(a*) 通过对k 的归纳证明，如果两个字符串有着长度为k 的公共子序列，那么它们也有着长度为k 的匹配。
(b) 证明：如果两个字符串有长度为k 的匹配，那么它们也有长度为k 的公共子序列。
(c) 由(a)和(b)得出，LCS的长度与匹配的最大值其实是一回事。
字符串可能是实践过程中最常见的表的形式。表示字符串的方法数不胜数，而且其中一些技巧很难适用于其他类型的表。因此，本节专门介绍一些与字符串有关的特殊问题。
首先，应该意识到存储单个字符串基本不成问题。通常，我们有大量很短的字符串。它们可能形成词典，意味着我们可以随着时间的推移插入和删除字符串，也可能是静态字符串集合，时间再久也不会改变。下面要讲两个典型的例子。
1. 字母索引是一种研究文本的实用工具，它是由文档中使用过所有单词以及这些单词出现的位置构成的表。在大型文档中通常会有成千上万个不同的单词，而单词每出现一次就要被存储一次。这一单词集合是静态的，也就是说，一旦成形就不会改变，除非原有的字母索引中存在错误。
2. 将C语言程序转化为机器代码的编译器必须记录表示程序变量的所有字符串。大型程序可能拥有成百上千的变量名。想想看，分别在两个函数中声明的局部变量i，其实是两个不同的变量，这样就能明白为什么会有如此多的变量了。随着编译器对程序加以扫描，会找到新的变量名，并将其插入变量名集合中。一旦编译器完成了函数的编译，该函数的变量对随后的函数来说便不可用了，因此可以删除掉。
在这两个例子中，都存在很多短字符串。英语中的短单词比比皆是，而程序员则喜欢用i或x这样的字母表示变量。另一方面，不管是在英语文本还是在程序中，单词的长度都是没有限制的。
C语言程序中可能出现字符串常量，而它们会被存储为字符数组，后面跟上名为空字符（null character）且值为0的特殊字符“”。不过，在上面提到的应用中，我们需要随着程序运行而创建并存储新字符串的便利。因此，需要能向其中存储任意字符串的数据结构。其中一些可能如下。
1. 使用定长数组存放字符串。比数组短的字符串之后由空字符补齐。而比数组长的字符串不能完整地存储到数组中，它们必须被截断，只将长度与数组长度相等的前缀存储到数组中。
2. 与(1)类似的模式，但假设每一个字符串或被截断字符串的前缀之后都有一个空字符。这种方式简化了字符串的读操作，但它让数组中可以存储的字符串的长度减少了1。
3. 与(1)类似的模式，它不会在字符串后放置空字符，而是用另一个整数length 指示字符串的真实长度。
4. 要避免最大字符串长度的限制，可以将字符串中的字符存储为链表元素，而且可以将多个字符存储在一个单元中。
5. 可以创建大型字符数组，将很多单独的字符串放置其中。而每个字符串就由指向该字符串开头字符在该数组中位置的指针表示。字符串可能以空字符结尾，也可能有与之关联的长度。
我们来考虑一下上述第(1)类结构，其中字符串是由定长数组表示的。在下面的例子中，我们会创建拥有定长数组作为其中一个字段的结构体。
考虑一下用来存放索引中某一项，即单个单词以及与其相关的信息的数据结构。我们需要
存放下列内容。
1. 单词本身；
2. 单词出现的次数；
3. 表示文档中文本行的表，该单词会在其中出现一次或多次。
因此可以使用如下结构体：
typedef struct {
char word[MAX];
int occurrences;
LIST lines;} WORDCELL;复制代码这里的MAX是指单词的最大长度。所有的WORDCELL结构体都包含一个名为word的有MAX个字节的数组，不管要存放的单词到底有多短。
字段occurrence是计算某单词出现次数的计数器，而lines则是指向链表开头的指针。链表中的单元具有由以下宏定义的常规类型：
DefCell(int, CELL, LIST);复制代码
每个单元存放着一个整数，表示出现问题中单词的文本行。请注意，如果某个单词在一行中出现若干次，那么occurrence就要比表的长度更大。
在图6-34中，我们看到表示《圣经·创世记》第1章中的单词earth的结构体。假设MAX至少为6。表示行（诗句）号的完整表是(1，2，10，11，12，15，17，20，22，24，25，26，28，29，30)。
图 6-34 单词earth在《圣经·创世记》第1章中的索引项
整个索引可能是由一系列WORDCELL类型的结构体组成的。例如，这些结构体可以被组织为一棵二叉查找树，有着基于单词字母顺序的<次序。在使用字母索引时，该结构体可以提供相当高的单词访问速度。而随着我们不断扫描文本，找到并列出各单词的出现，它还能让我们高效地创建索引。要使用二叉树结构，就需要在类型WORDCELL中定义表示左子节点和右子节点的字段。我们还可以在原始的WORDCELL类型定义中加入“next”字段，从而将这些结构体排列在链表中。这是一种更简单的结构，不过如果单词数量众多，它的效率就要差不少。我们在第7章中将会看到如何在散列表中排列这些结构体，这基本上是解决这一问题的所有数据结构中性能最佳的。
定州申请400电话费用【定州企业全国热线电话办理】定州开通400电话电信价格、定州微信公众号代运营外包托管、定州网店编辑装修美工、定州网站推广优化大概需要多少钱
上往建站提供搭建网站，域名注册，官网备案服务，网店详情页设计，企业网店，专业网络店铺管理运营全托管公司咨询电话，服务器空间，微信公众号托管，网页美工排版,致力于域名申请，竞价托管，软文推广，全网营销,提供标准级专业技术保障，了却后顾之忧,主营：虚拟主机，网站推广，百度竞价托管，网站建设，上网建站推广服务，网络公司有哪些等业务，专业团队服务，效果好。
服务热线：400-111-6878 手机微信同号:18118153152（各城市商务人员可上门服务）
