发表日期: 2021-03-27 16:21:23 浏览次数:78
祁东企业微信公众号小程序开发公司、祁东企业网页设计方案、祁东做网站开发价格、祁东微信公众号制作运营报价明细表、祁东网站设计公司费用、祁东网站推广大概需要多少钱
祁东县,隶属湖南省衡阳市,地处衡阳市西南部、湘江中游北岸,东西狭长,北高南低,总面积1872平方千米。 [1] 截至2020年6月,祁东县下辖4个街道、17个镇、3个乡。 [2] 共368个行政村(社区居委会),总人口105.8万。
祁东县,因县城在祁山之东而得名。古为扬越之地,春秋时属楚国。祁东境内祁剧为全国优秀剧种之一。明朝重臣宁良、陈荐,清廷尚书陈大受,红军将领王如痴,革命志士曹炎,画家管锄非等都孕育于此。当前有祁东籍将军14人,两院院士2人,省部级领导7人,司级领导78人,处级领导1300多人。
湘桂铁路、娄底—衡阳高速公路、泉州—南宁高速公路、祁永高速穿过祁东境内,另有祁东港归阳港区。 [1] 祁东县是“中国黄花之乡”、“将军之乡”、“黑色金属之乡”、“中国曲艺之乡”、“省级文明县城”、“全省城乡环境卫生十佳县”。2018年4月23日,湖南省政府批准祁东县退出贫困县序列。
while
循环的循环不变式在讲到形如
while (<condition>) <body>复制代码
的while
循环时,通常都可以为循环条件测试前的那一点找出合适的循环不变式。一般来说,我们会试着通过对循环次数的归纳来证明循环不变式成立。然后,当条件为假时,可以利用循环不变式以及条件为假的事实,得出一些关于while
循环终止后什么为真的有用信息。
不过,与for
循环不同的是,可能不存在为while
循环计数的变量。更糟的是,尽管for
循环可以保证最多只会迭代到循环的限制(例如,SelectionSort
程序的内层循环最多循环n-1次),我们却没理由相信while
循环的条件可能会变为假。因此,证明while
循环正确性的部分工作就是要证明while
循环最终会终止。一般要通过涉及程序中变量的某个表达式E,按照如下方式一起来证明循环的终止。
1. 每进行一次循环,E 的值至少会减少1。
2. 如果E 的值小到某个指定的常数(比如0),循环条件就为假。
阶乘函数,写作n!,表示的是整数1×2×…×n 的积。例如,1!=1,2!=1×2=2,5!=1×2×3×4×5=120。图2-13所示的简单程序片段就是用来计算n≥1时的n!的。
(1) scanf("%d", &n);(2) i = 2;(3) fact = 1;(4) while (i <= n) {(5) fact = fact*i;(6) i++; }(7) printf("%d\n", fact);复制代码
图 2-13 阶乘程序片段
首先,要证明图2-13中第(4)行至第(6)行的while
循环一定会终止。这里我们选择的表达式E 是n-i。请注意,每进行一次while
循环,i
的值在第(6)行会增加1,而n
的值则保持不变。因此,每进行一次循环,E 的值就会减少1。此外,当E 的值为-1或更小时,有n-i≤-1,或者说是i≥n+1。因此,当E 变为负值时,循环条件i≤n 就不再成立,循环就将终止。一开始并不知道E 有多大,因为不知道要读入的n
值为多少。不过,不管该值为多少,E 最终都能小到-1,而循环将会终止。
现在必须证明图2-13中的程序能够完成它应该做的工作。合适的循环不变式命题如下,我们要通过对变量i
的值的归纳来证明该命题。
命题 S(j )。如果在到达循环测试i≤n 时变量i
的值为j,那么变量fact
的值就是(j-1)!。
依据。归纳依据是S(2)。只有当从外部进入该循环时,在到达该测试时i
的值才为2。在循环开始前,图2-13中的第(2)行和第(3)行会将fact
的值置为1,并将i
的值置为2。由于1=(2-1)!,所以归纳依据得到证明。
归纳。假设S(j )为真,并证明S(j+1)为真。如果j>n,那么当i
的值为j 或更早之时,该while
循环就中断了,因此当i
的值为j+1时,我们根本无法到达该循环测试。在这种情况下,S(j+1)为平凡真(trivially true),因为它具有“如果我们到达……”这种形式。
因此,假设j≤n,并考虑一下在i
的值为j时,执行while
循环的循环体会发生什么。通过归纳假设,在第(5)行被执行之前,fact
的值为(j-1)!,而i
的值为j。因此,在第(5)行执行完之后,fact
的值为j×(j-1)!,也就是j !。
在第(6)行,i
增加了1,其值就达到了j+1。因此,当i
带着值j+1到达该循环测试时,fact
的值是j !。命题S(j+1)就是说,当i
等于j+1时,fact
等于((j+1)-1)!,也就是j !。因此,我们证明了命题S(j+1),并完成了归纳步骤。
之前已经证明了while
循环将终止。由此可见,它将在i
第一次具有大于n 的值时终止。因为i
是整数,而且每进行一次循环就会增加1,所以i
在循环终止时的值一定是n+1。因此,当到达第(7)行时,命题S(n+1)一定成立。不过该命题表示fact
的值为n!。因此,程序会打印出n!,正如我们想要证明的。
作为一个实际问题,应该指出,图2-13中的阶乘程序在任何计算机上都只能打印出少量几个n 的阶乘值n!作为答案。因为阶乘函数增长得特别快,答案的大小很快就超过了现实中任何一台计算机上整数的最大大小。
1. 以下程序片段会让sum
的值等于从1到n 的整数之和,为其找出合适的循环不变式。
scanf("%d",&n);sum = 0;for (i = 1; i <= n; i++) sum = sum + i;复制代码
通过对i 的归纳证明找出的循环不变式成立,并利用它证明程序可按照预期工作。
2. 以下程序片段可计算数组A[0..n-1]
中各整数之和:
sum = 0;for (i = 0; i < n; i++) sum = sum + A[i];复制代码
为其找出合适的循环不变式,利用该循环不变式证明程序可按照预期工作。
3. * 考虑如下片段:
scanf("%d", &n);x = 2;for (i = 1; i <= n; i++) x = x * x;复制代码
对应i≤n 的测试之前那点的合适循环不变式会满足如下条件:如果我们到达该点时变量i
的值为k,那么有x=22k-1。通过对k 的归纳,证明该不变式成立。在循环终止后,x
的值是多少?
4. * 图2-14中的程序片段会持续读入整数,直到读到负整数为止,然后会打印出这些整数的和。为循环测试之前的那点找出合适的循环不变式,利用该不变式证明该程序片段可按照预期工作。
sum = 0;scanf("%d", &x);while (x >= 0) { sum = sum + x; scanf("%d", &x);}复制代码
图 2-14 为一列整数求和,通过负整数来终止循环
5. 考虑图2-13所示程序中的n,找出自己的计算机能处理的n 的最大值。定长整数对证明程序的正确有什么影响?
6. 通过对图2-10中程序循环的次数进行归纳,证明在第一次循环后j>i+1。
在递归定义(或归纳定义)中,我们用一类或多类紧密相关的对象或事实本身来对它们进行定义。这种定义一定不能是无意义的,比如“某个部件是某个有某种颜色的部件”,也不能是似是而非的,比如“当且仅当某事物不是glotz时它才是glotz”。归纳定义涉及:
1. 一条或多条依据规则,在这些规则中,要定义一些简单的对象;
2. 一条或多条归纳规则,利用这些规则,通过集合中较小的对象来定义较大的对象。
在2.5节中我们通过迭代算法定义了阶乘函数:将1×2×…×n 相乘得到n!。其实,还可以按照以下方式递归地定义n!的值。
依据。1!=1。
归纳。n!=n×(n-1)!。
例如,依据告诉我们1!=1。这样就可以在归纳步骤中使用该事实,得到n=2时
2!=2×1!=2×1=2
对n=3、4和5,有
1!=3×2!=3×2=6
4!=4×3!=4×6=24
5!=5×4!=5×24=120
等等。请注意,虽然术语“阶乘”看起来就是用自身来定义的,但在实践中,可以只通过值较小的n 的阶乘,得到值逐步增大的n 对应的n!的值。因此,我们具备了有意义的“阶乘”定义。
严格地讲,应该证明,n!的递归定义可以得出与原来的定义相同的结果,
n!=1×2×…×n
要证明这一点,就要证明如下命题。
命题S(n)。按照上述方式递归地定义的n!,等于1×2×…×n。
通过对n的归纳来完成证明。
依据。S(1)显然成立。递归定义的依据告诉我们1!=1,而且1×…×1(即“从1到1”这些整数的积)的积显然也等于1。
归纳。假设S(n)成立,也就是说,由递归定义给出的n!等于1×2×…×n。而递归定义告诉我们
(n+1)!=(n+1)×n!
如果应用乘法交换律,就有
(n+1)!=n!×(n+1) (2.11)
由归纳假设可知
n!=1×2×…×n
因此,可以用1×2×…×n替换等式(2.11)中的n!,就可以得到
(n+1)!=1×2×…×n×(n+1)
这也就是命题S(n+1)。这样就证明了归纳假设,并证明了对n!的递归定义与迭代定义是相同的。
图2-15显示了递归定义的一般本质。它在结构上与完全归纳类似,都含有无限的实例序列,每个实例都依赖于之前的任一或所有实例。我们通过应用一个或多个依据规则开始。接下来的一轮归纳,要对已经得到的内容应用一条或多条归纳规则,从而建立新的事实或对象。再接下来的一轮归纳,再次对已经掌握的内容应用归纳规则,获得新的事实或对象,以此类推。
图 2-15 在归纳定义中,要一轮一轮地建立对象,在某一轮建立的对象可能会依赖于之前所有轮次建立的对象
在定义阶乘的示例2.15中,我们从依据情况得到了1!的值,应用一次归纳步骤得到2!,应用两次归纳步骤得到3!,等等。这里的归纳具有“普通”归纳的形式,在每一轮的归纳中,都只用到在前一轮归纳中得到的内容。
在2.2节中,定义了词典顺序的概念,当时的定义是具有迭代性质的。粗略地讲,通过从左起比较对应符号ci 和di,测试字符串c1…cn是否先于字符串d1…dm,直到找到某个值i 令ci ≠di,或者到达其中一个字符串的结尾。以下的递归定义定义了字符串对w 和x,其中w 在词典顺序上要先于x。从直观上讲,要对两个字符串从开头起相同字符对的数目进行归纳。
依据。该依据涵盖了那些我们能立即分出字符顺序先后的字符串对。依据包含如下两个部分。
1. 对任何不为ε 的字符串w,都有ε<w。回想一下,ε 表示空字符串,也就是不含字符的字符串。
2. 如果c<d,其中c 和d 都是字符,那么对任何字符串w 和x,都有cw<dx。
归纳。如果字符串w 和x具有w<x 的关系,那么对任意字符c,都有cw<cx。
例如,可以使用以上定义表明base<batter
。根据依据的规则(2),有c=s
,d=t
,w=e
,x=tter
,因此有se<tter
。如果应用递归规则一次,有c=a
,w=e
,以及x=tter
。最后,第二次应用递归规则,有c=b
,w=ase
,以及x=atter
。也就是说,依据和归纳步骤是如下这样的:
se < tter ase < atterbase < batter复制代码
还可以按照以下方式证明bat<tter
。依据的部分(1)告诉我们,ε<ter
。如果应用递归规则3次,其中c依次等于t
、a
和b
,就可以进行如下推理:
ε < ter t < tter at < atter bat < batter复制代码
现在应该对两个字符串从左端起相同的字符数进行归纳,证明当且仅当字符串按照刚给出的递归定义排在前面之时,才能按照2.2节中的定义得出它也排在前面的结论。我们还留了两个归纳证明的习题。
在示例2.16中,如图2-15所示的事实组是很大的。依据情况给出了所有w<x 的事实,不管是w=ε,还是w 和x 以不同字符开头。使用归纳步骤一次,就给出当w 和x 只有第一个字母相同时,所有w<x 的情况;第二次使用,就给出了那些当w 和x 只有前两个字母相同时的所有情况,以此类推。
各种算术表达式是递归定义的,我们为这种定义的依据指定了原子操作数可以是什么。例如,在C语言中,原子操作数既可以是变量,也可以是常量。然后,归纳过程告诉我们可应用哪些运算符,以及每个运算符可以应用到多少个操作数上。例如,在C语言中,运算符<可以应用到两个操作数上,运算符符号-可以应用于一至两个操作数,而由一对圆括号加上括号内必要数量的逗号表示的函数应用运算符,则可以应用于一个或多个操作数,比如f(a1,…,an) 。
通常将如下的表达式称作“算术表达式”。
依据。以下类型的原子操作数是算术表达式:
1. 变量;
2. 整数;
3. 实数。
归纳。如果E1和E2是算术表达式,那么以下表达式也是算术表达式:
1. (E1+E2)
2. (E1-E2)
3. (E1×E2)
4. (E1/E2)
运算符+、-、×和/都是二元运算符,因为它们都接受两个参数。它们也叫作中缀(插入)运算符(infix operator),因为它们出现在两个参数之间。
此外,我们允许减号在表示减法之外,还可以表示否定(符号改变)。这种可能性反映在了第5条,也是最后一条递归规则中:
5. 如果E 是算术表达式,那么 (-E )也是。
像规则(5)中的-这样只接受一个操作数的运算符,称为一元运算符。它也称为前缀运算符,因为它出现在参数之前。
图2-16展示了一些算术表达式,并解释了为什么它们都是表达式。请注意,有时候括号是不必要的,可以忽略。比如图2-16中最后的表达式(vi),外层括号和表达式-(x+10)两侧的括号都是可以忽略的,而我们可以将其写为y-(x+10)。然而,剩下的括号是必不可少的,因为y×-x+10按照约定会被解释为(y×-x)+10,这就不是与y×-(x+10)等价的表达式了(例如,试试y=1和x=1)。7
7如果运算符约定俗成的优先级(一元的减号优先级最高,接着是乘号和除号,再接着是加号和减号),以及“左结合性”的传统约定(即优先级相同的运算符——比如一串加号和减号——从左边开始结合)已经暗示了括号的存在,那么括号就是多余的。不管是C语言还是普通的算术,都遵守这些约定。
(i) x 依据规则(1)
(ii) 10 依据规则(2)
(iii) (x+10) 对(i)和(ii)应用递归规则(1)
(iv) (-(x+10)) 对(iii)应用递归规则(5)
(v) y 依据规则(1)
(vi) (y×(-(x+10))) 对(v)和(iv)应用递归规则(5)
图 2-16 一些算术表达式示例
更多运算符术语
出现在其参数之后的一元运算符,比如表达式n!中的阶乘运算符!,称为后缀运算符。如果接受多个操作数的运算符重复地出现在其所有参数之前或之后,那么它们也可以是前缀或后缀运算符。在C语言或普通算术中没有这类运算符的例子,不过我们在5.4节中将要讨论一些所有运算符都是前缀或后缀运算符的表示法。
接受3个参数的运算符就是三元运算符。举例来说,在C语言中,表示“若c 则x,否则y ”的表达式
c?x:y
中,运算符?:
就是三元运算符。如果运算符接受k 个参数,就称其是k 元的。
可以出现在表达式中的圆括号串称为平衡圆括号。例如,在图2-16的表达式(vi)中出现的模式,以及如下表达式
((a+b)×((c+d)-e))
具有的模式。空字符串ε 也是平衡圆括号串,例如,它的模式是表达式x。一般来说,判定圆括号串平衡的条件是,每个左圆括号都能与其右侧的某个右圆括号配对。因此,“平衡圆括号串”的一般定义由以下两个规则组成:
1. 平衡圆括号串中左圆括号和右圆括号的数量相等;
2. 在沿着括号串从左向右行进的过程中,该串的量变从不为负值,其中量变(profile)是对行进过程中已达到左括号数目减去已到达右括号数目的累计值。
请注意,统计值必须从0开始,以0结束。例如,图2-17a表示的是的量变,而图2-17b表示的是的量变。
图 2-17 两个括号串的量变
“平衡圆括号”的概念有着多种递归定义。下面的定义比较巧妙,不过我们将证明,该定义相当于之前提到的涉及统计值的非递归定义。
依据。空字符串是平衡圆括号串。
归纳。如果x 和y 是平衡圆括号串,那么(x )y 也是平衡圆括号串。
祁东企业微信公众号小程序开发公司、祁东企业网页设计方案、祁东做网站开发价格、祁东微信公众号制作运营报价明细表、祁东网站设计公司费用、祁东网站推广大概需要多少钱
备案号: 苏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