当前位置: 网站首页>小程序开发>400电话办理

祁东400电话申请开通【祁东企业网站建设】祁东微信公众号小程序开发运营价格、祁东微信公众号APP软件客户端设计运营、祁东网页页面设计公司费用、祁东公司网站制作方案流程改版维护大概需要多少钱

发表日期: 2021-03-27 16:27:40 浏览次数:83

祁东400电话申请开通【祁东企业网站建设】祁东微信公众号小程序开发运营价格、祁东微信公众号APP软件客户端设计运营、祁东网页页面设计公司费用、祁东公司网站制作方案流程改版维护大概需要多少钱

祁东县,隶属湖南省衡阳市,地处衡阳市西南部、湘江中游北岸,东西狭长,北高南低,总面积1872平方千米。 [1]  截至2020年6月,祁东县下辖4个街道、17个镇、3个乡。 [2]  共368个行政村(社区居委会),总人口105.8万。

祁东县,因县城在祁山之东而得名。古为扬越之地,春秋时属楚国。祁东境内祁剧为全国优秀剧种之一。明朝重臣宁良、陈荐,清廷尚书陈大受,红军将领王如痴,革命志士曹炎,画家管锄非等都孕育于此。当前有祁东籍将军14人,两院院士2人,省部级领导7人,司级领导78人,处级领导1300多人。

湘桂铁路、娄底—衡阳高速公路、泉州—南宁高速公路、祁永高速穿过祁东境内,另有祁东港归阳港区。 [1]  祁东县是“中国黄花之乡”、“将军之乡”、“黑色金属之乡”、“中国曲艺之乡”、“省级文明县城”、“全省城乡环境卫生十佳县”。2018年4月23日,湖南省政府批准祁东县退出贫困县序列。

习题

1. 我们可以按下以下方式递归地定义 n2

依据。对n=1,有12=1

归纳。如果n2=m,那么(n+1)2=m+2n+1。

(a) 编写C语言递归函数实现该递归。

(b) 通过对n 的归纳证明该定义能正确地计算n2

2. 假设有数组A[0..4],其中有按所述顺序排列的元素10、13、4、7、11。在每次调用图2-22所示的递归函数recSS之前,数组A的内容是怎样的?

3. 假设如1.3节所述,使用1.6节给出的DefCell(int,CELL,LIST)宏来定义整数链表的节点。回想一下,该宏会扩展为如下类型定义:

typedef struct CELL *LIST;struct CELL {
    int element;
    LIST next;};复制代码

编写递归函数find,接受LIST类型的参数,并在某个链表节点含有整数1698作为其元素时返回TRUE,如果没有则返回FALSE

4. 编写递归函数add,像习题(3)那样接受LIST类型的参数,并返回表中各元素之和。

5. 使用习题3中提到的节点,编写接受整数链表作为参数的递归选择排序函数。

6. 我们在习题8中提出,可以将选择排序一般化,以使用任意的keylt函数来比较元素。重新编写递归的选择排序算法以融入这种一般性。

7. * 给出递归算法,接受整数i,并生成i 的二进制表示形式(由0和1组成的序列),其中低位排在前。

8. * 两个整数i 和j 的最大公约数(greatest common divisor,GCD)是指能整除i 和j 的最大整数。例如,gcd(24,30)=6,而gcd(24,35)=1。编写递归函数,接受两个整数i 和j,其中i>j,并返回gcd(i,j )。

提示:大家可以使用如下所述的gcd 的递归定义,它假设i>j

依据。如果j 能整除i,则j 是i 和j 的最大公约数。

归纳。如果j 不能整除i,设k 是i 除以j 得到的余数。那么gcd(i ,j )就和gcd(j ,k )是相同的。

9. ** 证明:习题8中给出的最大公约数递归定义和它的非递归定义(整除i 和j 的最大整数)能得出相同结果。

10. 通常,递归定义可以相当直接地转化为算法。例如,考虑一下示例2.16中给出的字符串“小于”关系的递归定义。编写递归函数,测试两个给定字符串中的第一个字符串是否“小于”另一个字符串。假设字符串是用字符链表表示的。

11. * 根据2.6节的习题8中给出的已排序表的递归定义,创建一种递归排序算法。该算法与示例2.22中的递归选择排序相比如何?

分治法

有一种攻克问题的方式,是将问题分解成多个子问题,然后解决这些子问题,并将它们的解决方案结合成整个问题的解决方案。术语分治法就是用来描述这种问题解决技术的。如果这些子问题和原问题相似,那么我们也许能使用相同的函数递归地解决这些子问题。

要让这种技术起作用,有两点要求。首先是子问题必须比原问题简单。其次是在有限次细分之后,必须得到能立即解决的子问题。如果达不到这些条件,递归算法就会一直细分问题,而找不出解决方案。

我们注意到图2-22中的递归函数recSS就满足这两个条件。每当调用该函数,就是对少一个元素的子数列调用该函数,而在对只含一个元素的子数列调用它时,它就会返回而不再继续调用自己。类似地,图2-19中的阶乘程序会在每次调用时调用较小整数,而递归过程会在调用参数到达1时停止。2.8节讨论了分治法更为强大的应用——“归并排序”。在这种排序中,待排序数组的大小减小得非常迅速,因为归并排序在每次递归调用时会将数组大小砍掉一半,而不是减去1。

2.8 归并排序:递归的排序算法

现在要考虑一种名为归并排序的与选择排序有着天壤之别的排序算法。递归的方式能最好地描述归并排序,而归并排序展示了分治法的强大,在这种排序方法中,我们通过将问题“分为”大小减半的两个相似问题来为表(a1,a2,…,an)排序。从原则上讲,可以首先将原表分为两个元素任选的大小相等的表,不过在我们开发的程序中,将会将其分为一个含有奇数编号元素的表(a1,a3,a5,…),以及一个含有偶数编号元素的表(a2,a4,a6,…)。10接着单独为大小减半的两个表排序。要完成原表中n个元素的排序,要使用示例2.23中描述的算法来合并两个大小减半的表。

10请记住,“奇数编号”和“偶数编号”指的是元素在表中的位置,而非这些元素的值。

在第3章中,我们将看到,随着待排序表长度n的增加,归并排序所需时间的增长速度要远慢于选择排序所需时间的增长速度。因此,即便递归调用会额外耗费些时间,当n 很大时,还是应该优先使用归并排序而不是选择排序。在第3章中我们将分析这两种排序算法的相对性能。

2.8.1 合并

“合并”是指用两个已排序表生成一个只包含这两个表中所有元素的已排序表。例如,假设有表(1,2,7,7,9)和(2,4,7,8),合并后的表就是(1,2,2,4,7,7,7,8,9)。请注意,对未排序的表谈“合并”是没有意义的。

有一种合并两个表的简单方式,就是从表开头开始分析它们。在每一步中,我们找出两个表当前开头位置的两个元素中较小的那个,选择该元素作为合并后的表的下一个元素,并将该元素从它原来所在的表中删除,使该表具有一个新的“首位”元素。虽然我们在两个表开头的元素相同时会选取第一个表开头的元素,但是持平关系的打破是具有任意性的。

示例 2.23

考虑合并以下两个表。

L1=(1,2,7,7,9)和L2=(2,4,7,8)

两个表的第一个元素分别为1和2。因为1比较小,所以将其选作合并后的表M 的第一个元素,并将1从L1中删除,因此新的L1就是(2,7,7,9)。现在,L1L2的第一个元素都是2。可以任选其一。假设采取持平情况下总是从L1中选取元素的策略,那么合并后的表M 就变为(1,2),表L1变为(7,7,9),而L2仍为(2,4,7,8)。图2-23所示的表格展示了直到L1L2双双耗尽的整个合并步骤。

L1

L2

M

1,2,7,7,9

2,4,7,8

2,7,7,9

2,4,7,8

1

7,7,9

2,4,7,8

1,2

7,7,9

4,7,8

1,2,2

7,7,9

7,8

1,2,2,4

7,9

7,8

1,2,2,4,7

9

7,8

1,2,2,4,7,7

9

8

1,2,2,4,7,7,7

9

1,2,2,4,7,7,7,8

1,2,2,4,7,7,7,8,9

图 2-23 合并的例子

我们将会发现,如果把表表示为1.3节所介绍的链表,设计归并算法的工作会更简单。链表将会在第6章中得到更为详细的介绍。接着,要假设表的元素都为整数。因此,每个元素都能表示为一个“单元”,或者说是struct CELL类型的结构体,而表则表示为指向CELLLIST类型的指针。这些定义都是由我们在1.6节中讨论过的DefCell(int, CELL, LIST)宏来定义的。这种对DefCell宏的使用会扩展为:

typedef struct CELL *LIST;struct CELL {
    int element;
    LIST next;};复制代码

每个单元的element字段都含有一个整数,而next字段则含有指向表中下一单元的指针。如果当前的元素是表中最后一个元素,next字段就含有表示空指针的值NULL。然后整列整数就会用指向表第一个单元的指针(即一个LIST类型的变量)来表示。而空表会用值为NULL的变量(而不是指向第一个元素的指针)来表示。

图2-24是归并算法的C语言实现。merge函数接受两个表作为参数,并返回合并后的表。也就是说,形式参数list1list2是指向两个给定表的指针,而返回值是指向合并后的表的指针。递归算法可描述为如下形式。

     LIST merge(LIST list1, LIST list2)
     {(1)      if (list1 == NULL) return list2;(2)      else if (list2 == NULL) return list1;(3)      else if (list1->element <= list2->element) {
             /* 在这里,两个表都不为空,
                而且第一个表的首个元素更小。
                得到的结果就是第一个表的第一个元素,
                后面跟上其余元素的合并。*/(4)          list1->next = merge(list1->next, list2);(5)          return list1;
         }
         else { /* list2 的首个元素更小 */(6)          list2->next = merge(list1, list2->next);(7)          return list2;
         }
     }复制代码

图 2-24 递归的合并

依据。如果任一表为空,那么另一个表就是所需的结果。这条规则是通过图2-24中的第(1)行和第(2)行实现的。请注意,如果两个表都为空,就将返回list2。不过这是正确的,因为这里list2的值是NULL,而两个空表的结合还是空表。

归纳。如果两个表都不为空,那么每个表都有第一个元素。我们可以将两个表的第一个元素分别称为list1->elementlist2->element,即分别由list1list2指向的单元的element字段。图2-25展示了这种数据结构。返回的表从含有最小元素的单元开始。该返回表其余的部分由两个表中除这个最小元素之外的所有元素组成。

{%}

图 2-25 归并算法的归纳步骤

例如,第(4)行和第(5)行处理的是最小元素为表1中第一个元素的情况。第(4)行是对merge函数的递归调用。该调用的第一个参数是list1->next,也就是指向表1中第二个元素的指针(如果表1只有一个元素则为NULL)。因此,传入该递归调用的是由表1中除第一个元素之外的所有元素组成的表。第二个参数是整个表2。因此,第(4)行中对merge函数的递归调用会返回一个指针,指向合并后的表中其余所有元素,并将该指向合并后的表的指针存储在表1第一个单元的next字段中。在第(5)行,我们会返回指向上述单元的指针,该单元现在已经是合并后的表所有元素中的第一个单元。

图2-25展示了这种变化。虚线表示的箭头会在merge被调用时出现。特别要说的是,merge的返回值是指向最小元素所在单元的指针,而且该元素的next字段是指向第(4)行对merge的递归调用所返回的表。

最后,第(6)行和第(7)行会处理最小元素在表2中的情况。该算法的行为与第(4)行和第(5)行中的行为是一样的,只不过两个表的角色互换了而已。

示例 2.24

假设我们对示例2.23中的表(1,2,7,7,9)和(2,4,7,8)调用merge。图2-26展示了进行合并所产生的调用序列,是按照第一列中由上向下的顺序进行调用的。在图中我们省去了分隔表元素的逗号,不过在分隔进行合并的参数时要用到逗号。

调用

返回

merge(12779,2478)

122477789

merge(2779,2478)

22477789

merge(779,2478)

2477789

merge(779,478)

477789

merge(779,78)

77789

merge(79,78)

7789

merge(9,78)

789

merge(9,8)

89

merge(9,NULL)

9

图 2-26 对merge函数的递归调用

例如,因为表1的第一个元素比表2的第一个元素小,所以会执行图2-24的第(4)行,而且我们会归并除表1第一个元素之外的所有元素。也就是说,第一个参数是表1其余的部分,即(2,7,7,9),而第二个参数就是整个表2,即(2,4,7,8)。现在两个表开头的元素是相同的。因为图2-24中第(3)行的测试偏向表1,所以我们从表中移出2,而对merge函数的下一次调用中,第一个参数就是(7,7,9),第二个参数还是(2,4,7,8)。

返回的表在第二行中表示,是按从下向上的顺序看的。请注意,与图2-23中合并的迭代描述不同的是,递归算法会从尾部起组成合并后的表,而迭代算法则是从头开始组成合并后的表。



祁东400电话申请开通祁东企业网站建设祁东微信公众号小程序开发运营价格、祁东微信公众号APP软件客户端设计运营、祁东网页页面设计公司费用、祁东公司网站制作方案流程改版维护大概需要多少钱


400-111-6878
服务热线
顶部

备案号: 苏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