发表日期: 2021-03-27 16:22:38 浏览次数:122
祁东网络公司哪家好【祁东企业网站百度SEO推广公司】祁东做网站开发价格、祁东淘宝店铺开店装修设计运营、公司网站制作方案流程改版维护费用、祁东高端企业网站页面制作设计专业公司需要多少钱
祁东县,隶属湖南省衡阳市,地处衡阳市西南部、湘江中游北岸,东西狭长,北高南低,总面积1872平方千米。 [1] 截至2020年6月,祁东县下辖4个街道、17个镇、3个乡。 [2] 共368个行政村(社区居委会),总人口105.8万。
祁东县,因县城在祁山之东而得名。古为扬越之地,春秋时属楚国。祁东境内祁剧为全国优秀剧种之一。明朝重臣宁良、陈荐,清廷尚书陈大受,红军将领王如痴,革命志士曹炎,画家管锄非等都孕育于此。当前有祁东籍将军14人,两院院士2人,省部级领导7人,司级领导78人,处级领导1300多人。
湘桂铁路、娄底—衡阳高速公路、泉州—南宁高速公路、祁永高速穿过祁东境内,另有祁东港归阳港区。 [1] 祁东县是“中国黄花之乡”、“将军之乡”、“黑色金属之乡”、“中国曲艺之乡”、“省级文明县城”、“全省城乡环境卫生十佳县”。2018年4月23日,湖南省政府批准祁东县退出贫困县序列。
由依据可知,ε 是平衡圆括号串。如果应用递归规则,其中x 和y 都等于ε,就可以得出()是平衡的。请注意,在将空字符串提交给变量(如x 或y)时,该变量就“消失”了。然后可以按以下方法应用递归规则。
1. x=()且y=ε,得出(())是平衡的。
2. x=ε且y=(),得出()()是平衡的。
3. x=y=(),得出(())()是平衡的。
最后,因为已知(())和()()是平衡的,所以可以令递归规则中的x和y为这两者,就证明了((()))()()是平衡的。
可以证明两种“平衡”定义指定的是同一组括号串。为了让表述更清楚,我们将根据递归定义定义的平衡括号串直接称为平衡括号串,而将根据非递归定义定义的平衡括号串称为量变平衡括号串。量变平衡括号串就是那些量变最终为0而且从不为负值的括号串。需要证明以下两点。
1. 每个平衡括号串都是量变平衡的。
2. 每个量变平衡括号串都是平衡的。
这就是下面两个示例中归纳证明的目标。
首先,我们来证明(1)部分,也就是每个平衡括号串都是量变平衡的。这段证明复制了定义平衡括号串所使用的完全归纳。也就是说,我们要证明如下命题。
命题 S(n)。如果括号串w 是通过n 次应用递归规则被定义为平衡的,w 就是量变平衡的。
依据。依据为n=0。不需要通过应用任何递归规则便可证明其平衡的括号串就是ε,它的平衡是由依据规则得出的。由此可见,空字符串的量变最终为0,而且从不为负值,所以ε 是量变平衡的。
归纳。假设S(i )对i=0,1,…,n为真,并考虑S(n+1)的实例,也就是说证明w 为平衡括号串需要n+1次使用递归规则。考虑最后那次递归规则的使用,就是拿两个已知为平衡的括号串x 和y,组成形为(x )y 的w。我们使用了n+1次递归规则来形成w,而且最后一次利用递归规则既不是用来形成x,也不是用来形成y。因此,形成x 和y 都不需要利用递归规则n次以上。所以,归纳假设可以应用于x 和y,而且可以得出x 和y 都是量变平衡的。
w 的量变如图2-18所示。它首先会上升一级,作为对第一个左圆括号的回应。接着是x 的量变,由虚线所示,w 的量变在这里会再上升一级。我们使用归纳假设得出x 是量变平衡的,因此,它的量变始于第0级且终于第0级,而且从不为负。如图2-18所示,由于w 的量变中x 的部分已经上升了一级,该部分从第1级开始,在第1级结束,而且从来不低于第1级。
图 2-18 构造w=(x )y 的量变
显式出现在x 和y 之间的右圆括号将w 的量变降为0。接着就到了y 的量变。根据归纳假设,y 是量变平衡的,因此在w 的量变中,y 的部分不会低于0,而且它让w 的量变最终归于0。
我们现在已经构造了w 的量变,并发现它满足量变平衡括号串的条件。也就是说,w 的量变从0开始,以0结束,并且从不为负值。这样就证明了,如果括号串是平衡的,那么它就是量变平衡的。
现在介绍“平衡圆括号”两种定义等价性的第二个方向。在示例2.20中,将要证明量变平衡的括号串是平衡的。
对递归定义的证明
请注意,在示例2.19中,通过对递归规则(用来证实某对象在定义的类中)的使用次数进行归纳,证明了与一类递归定义的对象(平衡圆括号串)有关的断言。这是处理递归定义概念的一种常见方法,其实也是递归定义很实用的原因之一。在示例2.15中,通过对n 的归纳,证明了递归定义的阶乘值的属性(即n!就是1到n 这n 个整数的积)。而在对n!的定义中,使用了n-1次递归规则,所以该证明过程也可视作对递归规则应用次数进行归纳。
现在来证明(2)部分,通过对圆括号串的长度进行完全归纳,由“量变平衡”得出“平衡”。正式的命题如下。
命题 S(n)。如果长度为n 的圆括号串w 是量变平衡的,那么它也是平衡的。
依据。如果n=0,那么该括号串一定是ε。由递归定义的依据可知ε 是平衡的。
归纳。假设长度小于等于n 的量变平衡括号串是平衡的。必须证明S(n+1)为真,也就是要证明长度为n+1的量变平衡括号串也是平衡的。8考虑这样一个括号串w:因为w 是量变平衡的,它不可能以右圆括号开头,否则它的量变会立刻变为负值。因此,w 是以左圆括号开始的。
8请注意,所有的量变平衡括号串都刚好是偶长度的,所以,如果n+1为奇数,就不作说明了。不过,在证明中不需要n为偶数。
将w 分为两部分。第一部分从w 的开头开始,到w 的量变第一次变为0截止。第二部分就是w 中其余的部分。例如,图2-17a所示的量变第一次变为0是在其末尾处,所以如果w=(()(())),那么第一部分就是整个括号串,而第二部分就是ε。在图2-17b中,w=()(())(),那么第一部分就是(),而第二部分是(())()。
第一部分永远不可能以左圆括号结尾,因为如果那样,那么在结尾之前的那个位置,量变就为负值了。因此,第一部分以左圆括号开始,并以右圆括号结尾。这样就可以将w 写为(x )y 的形式,其中(x )是第一部分,而y 是第二部分。x 和y 都要比w 短,所以如果可以证明它们是量变平衡的,就可以利用归纳假设推出它们是平衡的。然后可以使用“括号串平衡”定义中的递归规则来证明w=(x )y 是平衡的。
很容易看出,y 是量变平衡的。图2-18还说明了w、x 和y 的量变之间的关系。也就是说,y 的量变是w 的量变的尾部,开始和结束的高度都是0。因为w 是量变平衡的,所以可以得出结论:y 也是量变平衡的。证明x 是量变平衡括号串的过程也几近相同。x 的量变是w 的量变的一部分,它的起止高度都是第1级,而且x 的量变也从未低于第1级。可以知道w 的量变在x 这一段从未到过0,因为我们选取(x )作为w 的最短前缀,而在它结尾处w 的量变才回到0。这样,w 内的x 的量变从未到过0,所以x 本身的量变从未变为负值。
现在已经证明了x 和y 都是量变平衡的。因为它们都比w 短,所以归纳假设适用于它们,它们都是平衡的。定义“括号串平衡”的递归规则告诉我们,如果x 和y 都是平衡的,那么(x )y 也是平衡的。而w=(x )y,所以w 也是平衡的。我们现在完成了归纳步骤,并证明了命题S(n )对所有的n≥0都成立。
1. * 证明:示例2.16中给出的词典顺序的定义和2.2节中给出的定义是相同的。提示:证明由两部分组成,每个部分都要通过归纳法进行证明。对第一个部分,假设根据示例2.16的定义有w<x。通过对i 的归纳证明如下命题S(i )为真:“如果证明w<x 需要应用i 次递归规则,那么根据2.2节中‘词典顺序’的定义有,w 先于x。”依据情况为i=0。该习题的第二部分是要证明,如果根据2.2节中词典顺序的定义有,w 先于x,那么根据示例2.16中的定义有,w<x,这里要对w 和x 从开头起不间断的相同字母数进行归纳。
2. 画出以下圆括号串的量变曲线。
(a) (()(())
(b) ()())(()
(c) ((()())()())
(d) (()(()(())))
哪些是量变平衡的?对那些量变平衡的圆括号串,使用2.6节中的递归定义证明它们是平衡的。
3. * 证明:每个平衡圆括号串(按照2.6节中的递归定义)都是某个算术表达式中的圆括号串(见介绍算术表达式定义的示例2.17)。提示:对“平衡圆括号”定义中的递归规则在构建某给定平衡圆括号串的过程中被使用的次数进行归纳,以证明该命题。
4. 说出以下C语言运算符是前缀、后缀还是中缀运算符,以及它们是一元、二元还是k 元(k>2)运算符。
(a) <
(b) &
(c) %
5. 如果熟悉UNIX的文件系统或类似的系统,请对可能的目录/文件结构给出递归定义。
6. * 某整数集合S 可通过以下规则递归地定义。
依据。0在S 中。
归纳。如果i在S 中,那么i+5和i+7也在S 中。
(a) 不在S 中的最大整数是多少?
(b) 设j 是(a)小题的答案。证明:不小于j+7的整数都在S中。提示:要注意到这一题与2.4节习题中第8小题的相似性(虽然在这里我们只处理非负整数)。
7. * 通过对位串长度的归纳,递归地定义偶校验位串集合。提示:最好同时定义偶校验位串和奇校验位串这两个概念。
8. * 可以按照以下规则定义已排序整数表。
依据。由一个整数组成的表是已排序的。
归纳。如果已排序表L的最后一个元素是a,而且b≥a,那么L 后加上b 也是已排序表。
证明:如上所述的对“已排序表”的递归定义与之前对已排序表的非递归定义(即由整数a1≤a2≤…≤an组成的表是已排序表)是等价的。
请记住,这里需要证明(a)、(b)两个部分。(a)如果由递归定义得出表是已排序的,那么根据非递归定义它也是已排序的;(b)如果表由非递归定义可知是已排序的,那么根据递归定义它也是已排序的。(a)部分可以对递归规则的使用次数进行归纳,而(b)部分则可以对表的长度进行归纳。
9. ** 如图2-15所示,每当我们给出递归定义,就可以按照生成对象的“轮次”(也就是为得到对象而应用归纳步骤的次数)为已定义的对象分类。在示例2.15和示例2.16中,描述每一轮生成的结果是相当简单的。有时这项工作却更具挑战性。请问该如何刻画以下两种情况中第n轮生成的对象?
(a) 如示例2.17中描述的算术表达式。提示:如果熟悉第5章要介绍的树,可以考虑表达式的树表示。
(b) 平衡圆括号串。请注意,示例2.19中所描述的“递归规则应用次数”与找出圆括号串的轮次是不同的。例如,(())()使用了3次递归规则,但是在第二轮被找出的。
祁东网络公司哪家好【祁东企业网站百度SEO推广公司】祁东做网站开发价格、祁东淘宝店铺开店装修设计运营、公司网站制作方案流程改版维护费用、祁东高端企业网站页面制作设计专业公司需要多少钱
备案号: 苏ICP备11067224号
CopyRight © 2011 书生商友信息科技 All Right Reserved
24小时服务热线:400-111-6878 E-MAIL:1120768800@qq.com QQ:1120768800
网址: https://www.768800.com 网站建设:上往建站
关键词: 网站建设| 域名邮箱| 服务器空间| 网站推广| 上往建站| 网站制作| 网站设计| 域名注册| 网络营销| 网站维护|
企业邮箱| 虚拟主机| 网络建站| 网站服务| 网页设计| 网店美工设计| 网站定制| 企业建站| 网站设计制作| 网页制作公司|
400电话办理| 书生商友软件| 葬花网| 调温纤维| 海洋馆运营维护| 北京保安公司| 殡仪馆服务| 殡葬服务| 昌平殡葬| 朝阳殡葬|
欢迎您免费咨询,请填写以下信息,我们收到后会尽快与您联系
服务热线:400-111-6878