计算机语言与程序设计 (6).ppt

1、1.计算机编程基础；6.递归。2.递归算法在可计算性理论中起着重要的作用，可计算性理论是算法设计的有力工具，对于扩展编程思想非常有用。就递归算法而言，它不涉及高级数学知识，但对于初学者来说，建立递归的概念并不容易。让我们从最简单的例子开始。递归及其实现，用递归算法找到n！定义：函数事实(n)=n！事实(n-1)=(n-1)！然后是事实(n)=n事实(n-1)，并且事实(1)=1，3是已知的。为了直观清晰地表达它，我们定义了两个节点：或节点and和节点。图形表示的直觉和思维的帮助。1.或节点，a是“或节点”，根据不同的条件，a有两个不同的b或c值。节点由表示。4，如果有两个以上的值，可以使用下图

2、：假设Z1，Z2，Zn，这些值是B或C，或G，5，2和节点，它们应该涂成黑色，并且相关联的B和C应该用弧线连接。A是AND节点，A的最终值是C节点的值，但是为了找到C的值，我们必须首先找到B节点的值，而C是B的函数.6，还是n！例如，画下面的“与或”图，其中“或”是“或”节点；b是一个直接可解的节点，值为1；c是和节点。当n1时，a的值是c的值，c的值是e的值，为了找到e的值，必须先找到d的值。e的值是d值事实(n-1)乘以n.7，可能有多个点与该节点相关联，如下图所示。节点A的值最终是D的值，但是为了找到D，必须先找到B和C。从图中，我们只能通过找到左边的点来找到最右边的点的值。我们同意最右

3、边点D的值是节点a的值，8，我们取3！绘制“与/或”节点图的目的是理解递归的含义。C=1D=2 * C=2 B=D=2 E=3 * B=3 * 2=6 A=6，9。下面是调用和返回的递归图。10.从图中可以想象，如果你想要事实(3)，你必须首先要求事实(2)；事实(2)需要先找到事实(1)。这就像剥卷心菜，从外到内，一层一层地剥，到达卷心菜的中心，遇到值为1的阶乘1，到达递归的边界。然后，通过使用事实(n)=n *事实(n-1)的一般公式，通过从内向外推事实(n)的值来获得它。为了让这个问题更彻底。我们画了以下流程图：11，12。为了生动地描述递归过程，我们将上面的图改为下面的图13。在该图中

4、，“内层”和“外层”具有相同的结构。他们之间有一种相互依存的关系，那就是“你有我，我有你”。为了进一步阐明递归的概念，本文将递归与递归进行了比较。以阶乘为例。递归是从已知的初始条件中一个接一个地找到所需的阶乘值。如果你要3块！事实(1)=1事实(2)=2 *事实(1)=2事实(3)=3 *事实(2)=6，14的初始条件，相当于从白菜中心“推”外层。然而，递归算法的起点不是初始条件，而是求解的目标。从未知项开始，它一个接一个地调用自己的求解过程，直到递归的边界(即初始条件)。就这个例子而言，读者会认为递归算法可能是多余的、费力的和吃力不讨好的。然而，对于许多实际问题来说，要找到一个明显的递归关系

5、是不可能或很难的，递归算法显示出明显的优势。如下所述，递归算法更符合人们的思维方式，逻辑性强，能够简单明了地描述问题，可读性好，易于理解。如果可以使用递归算法，许多看似复杂或困难的问题将很容易处理。这是河内塔问题的一个众所周知的例子。故事：据说在古印度的布拉马寺，一个和尚整天把三根柱子上的金盘翻过来。原来他想把64个比一个小的金盘从一根柱子移到另一根柱子上。在移动过程中，请遵守以下规则：一次只能移动一个磁盘，大磁盘不得落在小磁盘上。有些人认为这很简单。如果你用手移动一个盘子，从一个柱子上移动64个盘子大约需要5800亿年如何编写这个程序？从思考的角度来看，我们应该从最简单的情况分析开始，走来走

6、去，慢慢理清思路。1。假设车牌号码为1，则a列上只有一个车牌。此时，只需要将板从A移动到C，这被记录为从A移动1到C，17，2。a柱上有两个盘子，一个是小盘子，另一个是大盘子。在步骤(1)中，1号盘从A移动到B，使得2号盘可以移动；步骤(2)将2号板从甲移至丙；在步骤(3)中，将1号磁盘从B移动到C；这三个步骤被记录为：从甲到乙移动1；将2从A移动到C；将表格三从乙移至丙；18，3。a柱上有三块板，从小到大分别是1号、2号和3号。在步骤(1)中，将1号板和2号板视为一个整体；首先，将两者作为一个整体从一个板块移动到另一个板块，为3号板块同时移动到另一个板块创造机会。该步骤标记为移动(2，A，C

7、，B)，这意味着通过C将上述两个板作为一个整体从A移动到B。在步骤(2)中，将3号板从A移动到C，并将其放置到位一次。标记为从A到C移动3(3)将b上的两个板作为一个整体，然后移动到C.这一步被标记为移动(2，B，A，C)，这意味着通过一种方式将两个板作为一个整体从B移动到C。所谓的帮助是什么意思？当它完成的时候，它就不言自明了。19，20，4。从话题的约束条件来看，小盘可以在大市场上随意堆放，但恰恰相反，这是不允许的。在从A到B整体移动1号和2号盘的过程中，移动(2，A，C，B)实际上被分解为以下三个步骤：步骤(1)。步骤(1).2:将表格2从甲移动到乙；步骤(1).3:从表格C移动到表格B

8、；在上述步骤之后，1号和2号盘作为一个整体从A移动到B，这为3号盘从A移动到C创造了条件。类似地，一旦3号盘到达C，有必要考虑如何实现将1号和2号盘作为一个整体从B移动到C的过程。实际上，移动(2，B，A，C)应该被分解成三个步骤：步骤(3)。步骤(3).2:将表格2从B移动到C；步骤(3).3:将表格1从A移动到C；查看移动(2，A，C，B)意味着将两个人从A移动到B，但是没有C是不可能的，因为在第一步(1).1中，一个板将从A移动到C，为两个板从A移动到B创造条件，然后一个板将从C移动到B。参见这里可以理解使用C的含义。因此，在构思移动过程的参数时，应该使用所有三列。6.定义移动功能移动(

9、n，A，B，C)。物理意义是通过b将N个板从A移动到C。考虑到前面研究的步骤(1)、(2)和(3)，移动过程可以用下面的“与或”节点图来表示。22，这里，“和”或“节点”的含义分为(1)、(2)和(3)步骤。这三个步骤是相关的、相互依赖的、有序的，并且从左到右执行。移动(n，A，B，C)被分解成三个步骤。(1)移动(n-1，A，C，B)被理解为将上述n-1个板作为一个整体通过C从A移动到B；(2)输出N: A到C，并理解将N个磁盘从A移动到C是一个直接可解的节点；(3)移动(n-1，B，A，C)是指将上述n-1个板通过A整体从B移动到C。23，这显然是一个递归定义，在求解move(n-1，A，

10、C，B)时可以分解为三个步骤：步骤1:从A到C整体移动(n-2，A，B，C)；第二步：不。n-1板直接从A移动到B，即N-1:A移动到B；第三步：将上述n-2块板作为一个整体从C通过A移动到B，移动(N-2，C，A，B)；接下来，我们画一个递归的“与或”图，以三块板为例。24，这个图非常像一个倒置的树，节点move(3，A，B，C)是树的根，节点和节点是树的分支，而叶子是直接可解的节点。25，26，27，#include /预编译命令int step=1；/整数全局变量，预置1，无效移动(int，char，char，char)；/声明被调用的函数void main()/main functio

11、n/main program start int n；/整数变量，n是磁盘数，printf(请输入磁盘数n=);/提示信息扫描(%d)，/递归调用move(m-1) /自定义函数体结束，28，29，讨论青蛙过河，这是2000年全国青年信息学奥林匹克的一个试题。它是这样描述的：一条小溪可以从左岸跳到右岸。左岸有一根只能容纳一只青蛙安家的石柱L，右岸也有一根只能容纳一只青蛙安家的石柱R。有一群青蛙，它们的体积都比对方小。我们用1、2和n从小到大给青蛙编号。规定这群青蛙一开始只能躺在左岸的石头上，当然是根据编号一个接一个，小的落在大的上。大的不允许放在小的上面。小溪里有S石柱和Y荷叶。根据规定，青蛙

12、可以在小溪的柱子上安家。如果有很多青蛙，也要按照数量一个一个地排列，大的在底部，小的在顶部。对于荷叶，只允许一只青蛙在上面定居，不允许有很多青蛙在上面。至于右岸的石柱R，就像左岸的石柱L一样，允许多个青蛙按照数量一个接一个地落下，小的在顶部，大的在底部。当青蛙从左岸跳下时，它们是不允许跳回来的。同样，从左岸跳至右岸的青蛙，或从溪流中的荷叶或石柱跳至右岸的青蛙也不允许离开。当你知道小溪里有石柱和荷叶时，你最多能跳过多少只青蛙？这个问题看起来很难，但是如果我们仔细分析并理清思路，我们就能使它变得容易。想法：1 .简化问题，探索规律。首先，从个体到整体，我们应该善于分解多个因素，孤立一个因素进行分析

13、，并使之变得容易。2.定义函数跳转(S，y)最多可以跳过河的青蛙数量，其中：S是河中柱子的数量，Y是荷叶的数量，31，3。先看看简单的情况，河里没有柱子：S=0，y=1时跳(0，y)，跳(0，1)=2；描述：河里有一片荷叶，可以让两只青蛙通过。一开始，L上有两只青蛙，1#在2#之上。第一步：1#跳到荷叶上；步骤2: 2#从左直接跳到右；步骤3: 1#从荷叶跳到r。下图：32，当y=2时，跳(0，2)=3；说明：当河里有两片荷叶时，你可以经过三只青蛙。开始时：1#、2#和3#青蛙落在L上，1: 1#从L跳到叶子1，2: 2#从L跳到叶子2，3: 3 #直接从L跳到R，4: 2#从叶子2跳到R，5

14、: 1#从叶子1跳到R。在河里没有石柱的情况下，青蛙过河的数量只取决于荷叶的数量，荷叶的数量是1。让我们看看最简单的情况：S=1，y=1。从图中可以看出，跳过4只青蛙需要9步。洛杉矶的1号青蛙；来自洛杉矶的2#青蛙；一只来自美国的青蛙；洛杉矶的3号青蛙；4#青蛙，产自洛杉矶；3号青蛙，来自纽约；来自纽约的1号青蛙；来自苏联的2#青蛙；1号青蛙，来自于纽约；34、表1、35。为了更清楚地描述过河的过程，我们给出了表1。在表格中，L1L2 L3 L4表示青蛙一起落在左边柱子上的高度位置。L1在顶部，L4在底部。通过介绍这些信息，我们可以很容易地看到青蛙入住的限制。R1 R2 R3 R4也是如此。水

15、柱也被分成两个高度位置S1S2。没有必要将荷叶Y分层，因为它只允许一只青蛙落在上面。T=0是初始力矩，青蛙从小到大落在l柱上。T=1是第一步：1#从L跳到荷叶Y；l上只剩下2# 3# 4#了。T=2是第二步；2#从l跳到s柱，在S2，l柱上只剩下3#和4#了。T=3是第三步，1#从y跳到s柱，y被清除。这时，你看，S上有1#和2#青蛙，L上有3#和4#青蛙，这好像是L上有四只青蛙，分成上下两部分，上面两只青蛙通过荷叶Y转移到S上。这个过程分为两部分。也就是说，L上的一群青蛙被分成两组，每组有两只青蛙，上面的两只青蛙被转移到S上.我们可以考虑形成两个系统，一个是L，Y，R系统，另一个是S，Y，R系统。前两只青蛙很大；后两只青蛙很小。先跳大的，然后跳小的。从第五步到第九步，我们可以看到情况确实如此。36，这相当于LYR系统的跳转(0，1)和SYR系统的跳转(0，1)，两个系统的和是2*跳转(0，1)，所以有：跳转(1，1)=2*跳转(0，1)=2*2=4。现在看S=2，y=1跳跃(2，1)。我们称S1河和S2河中的两个柱子为荷叶y。我们考虑通过S2和y将L上的一半青蛙转移到S1。当然，小青蛙的一半在S1，大青蛙留在L，37上，所以L S1 S2 y R系统可以分解为：(L S2 y R系统)(LS2YR系统)=2 * (L S2 y R系统)=2 *