发表日期： 2021-04-10 15:24:01 浏览次数：112
邯郸网站推广【邯郸办理400电话】邯郸SEO优化、邯郸微信公众号APP客户端小程序开发、邯郸网站托管、邯郸APP开发
邯郸，是河北省地级市，国务院批复确定的中国河北省南部地区中心城市 [1] 。截至2019年，全市下辖6个区、11个县、代管1个县级市，总面积12073.8平方千米，常住人口954.97万人，其中城镇人口555.36万人，城镇化率58.15%。 [2]
邯郸位于河北省南端、太行山东麓，西依太行山脉，东接华北平原，与晋、鲁、豫三省接壤，是晋冀鲁豫四省要冲和中原经济区腹心、华北地区重要的交通枢纽，京广铁路、京广高铁纵贯南北，邯长铁路、邯济铁路横跨东西，邯黄铁路直通黄骅港口 [111] ，京深高速公路、大广高速公路、太行山高速公路贯穿南北，青兰高速公路、邯大高速公路横跨东西，107国道、106国道、309国道、230国道（原定魏公路） [3] 及234国道、514国道 [4] （原邯临公路）、515国道（原沙曹公路） [112] 形成国省干线公路网，邯郸机场是国家重点发展的支线机场。 [5]
邯郸是国家历史文化名城，有3100年的建城史，8000年前孕育了新石器早期的磁山文化；战国邯郸为赵国都城，魏县为魏国都城；汉代与洛阳、临淄、南阳、成都共享“五大都会”盛名；邯郸临漳县先后为曹魏、冉魏、前燕、东魏、北齐都城；北宋，大名府成为北宋陪都；清代，大名府为直隶省第一省会。 [6-9]
邯郸是国家园林城市、中国优秀旅游城市、全国绿化模范城市、全国双拥模范城市、全国社会治安综合治理优秀城市和中国成语典故之都，拥有涉县娲皇宫、广府古城2处5A级景区。
在本章中，我们将介绍以下主要概念。
迭代程序设计（2.2节）。
归纳证明（2.3节和2.4节）。
归纳定义（2.6节）。
递归程序设计（2.7节和2.8节）。
证明程序的正确性（2.5节和2.9节）。
除此之外，通过这些概念的例子，我们还会着重介绍计算机科学中一些有趣的重要思想。其中包括：
排序算法，包括选择排序（2.2节）和归并排序（2.8节）。
奇偶校验及数据错误的检测（2.3节）。
算术表达式及其代数变形（2.4节和2.6节）。
平衡圆括号（2.6节）。
新手程序员都会学习使用迭代，采用某种循环结构（如C语言中的for语句和while语句）。在本节中，我们将展示一个迭代算法的例子——“选择排序”。在2.5节中，我们还将通过归纳法证明这种算法确实能排序，并会在3.6节中分析它的运行时间。在2.8节中，我们要展示如何利用递归设计一种更加高效的排序算法，这种算法使用了一种称作“分而治之”的技巧。
常见主题：自定义和依据-归纳
在学习本章时，大家应该注意到有两个主题贯穿多个概念。第一个是自定义（self-definition），就是指概念是依据其自身定义或构建的。例如，我们提到过，表可以定义为空，或一个元素后跟一个表。
第二个主题是依据-归纳（basis-induction）。递归函数通常都含有某种针对不需要递归调用的“依据”实例，以及需要一次或多次递归调用的“归纳”实例进行测试。众所周知，归纳证明包括依据和归纳步骤，归纳定义也一样。依据-归纳这一对非常重要，在后文中每次出现依据情况或归纳步骤时，都会突出标记这些词语。
运用恰当的自定义不会出现悖论或循环性，因为自定义的子部分总是比被定义的对象“更小”。此外，在经过有限个通向更小部分的步骤后，就能到达依据情况，也就是自定义终止的地方。例如，表L 是由一个元素和比L 少一个元素的表构成的。当我们遇到没有元素的表，就有了表定义的依据情况：“空表是表”。
再举个例子，如果某递归函数是有效的，那么从某种意义上讲，某一函数调用的参数必须要比调用该函数的函数副本的参数“更小”。还有，在经过若干次递归调用后，我们必须要让参数“小到”函数不再进行递归调用为止。
要排序具有n个元素的表，我们需要重新排表中的元素，使它们按照非递减顺序排列。
假设有整数表{3，1，4，1，5，9，2，6，5}。我们要将其重新排列成序列{1，1，2，3，4，5，5，6，9}，实现对该表的排序。请注意，排序不仅会整理好各值的顺序，使每个元素的值小于等于接下来那个元素的值，而且不会改变每个值出现的次数。因此，排序好的表中有两个1和两个5，而原表中只出现一次的数字都只有一个。
只要表的元素有“小于”的顺序可言，也就是具备我们通常用符号<表示的关系，就可对这些元素排序。例如，如果这些值是实数或整数，那么符号<就表示实数或整数的小于关系；如果这些值是字符串，就按字符串的词典顺序来排列（“词典顺序”的介绍详见下文附注栏）。有时候，当元素比较复杂，比如当元素是结构体时，就可能使用每个元素的一部分（比如某个特定字段）来进行比较。
词典顺序
要比较两个字符串，通常是依据它们的词典顺序进行比较的。假设c1c2…ck和d1d2…dm是两个字符串，其中每个c 和每个d 都只代表一个字符。字符串的长度k 和m 不一定是相同的。我们假设对字符而言也有<顺序，例如，在C语言中，字符就是小的整数，所以字符常量和字符变量可以在算术表达式中作为整数使用。因此，我们可以使用整数间惯有的<关系，区分两个字符中哪个字符“小于”另一个字符。这种顺序包含这样一个自然的概念，出现在字母表靠前位置的小写字母，要“小于”出现在字母表中靠后位置的小写字母，同样的道理对大写字母也成立。
这样我们可以将字符串的这种顺序称为字典、词典或字母表顺序，如下所示。如果以下任意一条成立的话，我们就说c1c2…ck< d1d2…dm 。
1. 第一个字符串是第二个字符串的真前缀（proper prefix），这表示k< m，而且对i =1，2，…，k而言，都有ci =di。根据这条规则，就有
bat<batter。作为这条规则的特例，可能有k=0，这样第一个字符串就不含任何字符。我们用希腊字母ε 表示空字符串这种不含字符的字符串。当k=0时，规则(1)表示对任何非空字符串s 而言，都有ε＜s。2. 对某个i>0的值，两个字符串的前i-1个字符都相同，但第一个字符串的第i 个字符要小于第二个字符串的第i 个字符。也就是说，对j=1, 2, …, i-1，都有cj =dj，而且cj < dj。根据这条规则，
ball<base，因为这两个单词是从第3个字母起开始不同的，而ball的第三个字母是l， 要比base的第三个字母s更小。
a≤b这一比较关系总是表示，要么a< b，要么a 和b 具有相同的值。如果a1≤a2≤…≤an，也就是说，如果这些值有着非递减顺序，那么我们就说表（a1, a2, …, an）是已排序的。排序是这样一种操作，它接受任意表（a1, a2, …, an），并生成满足如下条件的表（b1, b2, …, bn）。
1. 表（b1, b2, …, bn）是已排序的；
2. 表（b1, b2, …, bn）是原表的排列。也就是说，表（a1, a2, …, an）中的每个值出现的次数，和那些值出现在（b1, b2, …, bn）中的次数是一模一样的。
排序算法接受任意的表作为输入，并生成对输入进行过排列的已排序表作为输出。
