计算机程序设计基础-第六讲

算法在可算性理中占有重要地位，它是算法

的有力工具，于拓展程思路非常有用。就算

法而言并不涉及高深数学知，只不初学者要建

立起概念不十分容易。S

我先M一个最的例子入°W

用一算法求i

定：函数fact(n)=n!g

fact(n-l)=(n-1)!

有fact(n)=nfact(n-l)

已矢口fact(l)=1

了表述得直清晰，我定两个点：或点与与

示的直性与思助力。

A“或点”，A依不同条件会有两不同的取B

或C。点曾表示

姿

3

与点可能有多个相的点，可描述下

A点日勺最D日勺，但J不D需先不B和C

M上看先求左的点才能求最右的点的，我

定最右D点的就是A点的°

7

下面画出了用和返回的示意

欲求fact(3),先要求fact(2);要求fact(2)先求

1fact(l)。就象到一白菜，融外向里，一孔I下

来，到了菜心，遇到1的乘，其1,到达了

的界。然后再用fact(n)=n*fact(n-l)个普遍公

式，M里向外倒推回去得到fact(n)的°

了把个得再透一点。我画了如下的流程

10■

11

了形象地描述程，将上改画成下

fact(3)

在个中“内”与“外”有着相同的构。它之

“你中有我，我中有你”，呈相互依存的系

了一步清的概念，将与推做一比。仍以

推是M已知的初始条件出，逐次去求所需要的三

如求3!1

初始条件fact(l)=1

fact(2)=2*fact⑴=2

fact(3)=3*fact(2)=6

相当于队菜心“推到”外。而算法的出点不

放在初始条件上，而放在求解的目上，队所求

的未知出逐次用本身的求解程，直到的

界(即初始条件)。就本例而言，者会算

法可能是多余的，力而不好。但多不可

能^^易找到而易的推系」算法就表

出了明的越性。下面我将会看到，算法比

符合人的思方式，性强，可将描述得扼

要，具有良好的可性，易于理解，多看来相当

,或以下手的，如果能使用算法就会使

得易于理。下面一个尽人皆知的例子哈

B(Hanoi)一

故事：相在古代印度的Bramah中，有位僧子整

天把三根柱子上的金倒来倒去，原来他是想把

64个一个比一个小的金队一根柱子上移到另一

根柱子上去。移程中恪守下述：每次只允

移一只，且大不得落在小上面。有人会得

很，真的手移就会，如以每秒移一只子

的，按照上述将64只子队一个柱子移至另

上一个柱子上，所需3800年°「

15

3、在A柱上有3只子，队小到大分1号，2号

整体MA移至B,3号造能一次移至c的机

步,.^_^=

move(2,A,C,B)

意思是籽上面的2只子作整体MA借助c移

一至B°三

步将3号AAA移至C,一次

—move3fromAtoC二

第(3)步于B上的作一个整体的2只子，再移

至C°一步

-movef2,B.A.C)

、

目的束条件看，大上可以随便小，相

反不允。在将1号和2号铸整人人A移至B

的程中m(0,是分解

第(1).1步:moveSteffis^to

第(1).2步：move2formAtoB;三___

第3步：move1formCtoB;三,

以上步,将1号和2号作整体队A移至B,

3号MA移至C造了条件。同,3号一旦

到了C,就要考如何将1号和2号旁整M

B移至C的程了。上move(2,B4O也要分

解三步

步

第(3).1move1formBtoA;

步

第(3).2move2formBtoC;

步

第(3).3move1formAtoC;20

5、看move(2,A,C,B)是要科2只盼自以A搬至

B,但没有C是不行的，因第(1)・1步就要

将1人人A移到C,2造条件队A移至B,然

后再把1MC移至B。看到里就能明白借助C

的含了。因此，在构思搬移程的参量，要把3

个柱子都用上二三

^^定搬移函数move(n,A,B,C)，物理意是籽丁

―s—

搬到cmove(n,A,B,C)

考/至U前

究的⑴⑵⑶

步，可以将搬

移程用如下

的与或点表

o

move(n-l,A,C,B)move(n-l,B,A,C)

一由一叁

n:AtoC

里用与或点的含是分解⑴(2)(3)步°3步是相

的，相互依存的，而且是有序的，队左至右行

O

move(n,A,B,C)分解3步二

⑴move(n-l,A,C,B)理解将上面的n-1只子作一

个整体MA

⑵出n:AtoC,理解将n号/\AA移至C,是

直接可解点；

⑶Move(n1B,A,C)理解将上面的n・l只子作一

个整体MBA移至C°

里然是一定，当着解move(n・l,A,GB)又

可想到，将其分解3步：

第1步：将上面的n・2只子作一个整体MAB

至C,move(n-2,A,B,C);=

第2步：第n-l号子直接移至塞即n-l:Ato

B;二

第3步：再籽上面的n・2只子作一个整体MCA

二移至B,move(n-2,C,A,B);二

下面，我是以3只子例画出的与或°

3

#include<stdio.h>//命令

mtstep=l;〃整型全局量，置1,步数

voidmove(int,char,char,char);〃严明要用至的被用函数

voidmain()〃主函数

〃主程序始

mtn;〃整型量，n数,

printf(n入数！＞=")；〃提示信息

scanf(H%dH,&n);//入正整数n

printf(H在3根柱子上移％d只的步//出提示信息

move(n/a,,,b,,,c,);//用函数move(n；a,,,b,,,c,)

〃主程序束

〃以下函数是被主程序用的函数

voidmove(intm,charp,charq,charr)〃自定函数，m,p,q,r形参，m整型量

//p,q,r字符型量

〃自定函数体始

if(m=l)〃如果m1,直接可解点,

printf("[%d]move1#from%cto%c\n”，step,p,r);〃直接可解点，出移信息

step=step+l;〃步效力口1

〃如果不1,要用move(m-l)

move(m-l,p,r,q);//用move(m-l)

prmtf(H[%d]move%d#from%cto%c\nM,step,m,p,r);〃直接可解点，出移信息

step=step+l;〃步数加1

move(m-l,q,p,r);//用move(m-l)

〃自定函数体束

青蛙河

是2000年全国青少年信息学奥林匹克的一道。叙述如下

一条小溪尺寸不大，青蛙可以队左岸跳到右岸，在左岸有一石

柱L,面只容得下一只青蛙落脚，同右岸也有一石柱

R,面也只容得下一只青蛙落脚。有一青蛙人人尺寸上一个

比一个小。我将青蛙人人小到大，用1,2,…，n号°

定初始青蛙只能在左岸的石L上，当然是一个落一个

,小的落在大的上面。不允大的在小的上面。在小溪中有

S小石柱，有y片荷叶，定溪中的柱子上允一只青蛙落脚

,如有多只同要求一个落一个，大的在下，小的在上。于

荷叶只允一只青蛙落脚，不允多只在其上。于右岸的石

柱R,与左岸的石柱L一允多个青蛙落脚，但一个落一

个，小的在上，大的在下。当青蛙人人左岸的L上跳走后就不

允再跳回来；同，人人左岸L上跳至右岸R,或M溪中荷

叶或溪中石柱跳至右岸R上的青蛙也不允再离°在已知

看起来，但是如果我真分析，理出思路，就可化

i、化，探索律。先队个再到一般，要善于多个因

素作分解，孤立出一个因素来分析，化易=

：/一^iJ数]

Juinp(S9y)最多可跳河的青蛙数

「其中：S河中柱子数1

「y荷叶数「

30

再看Jump(S,y)

先看一个最情况：S=1,y=l

M上看出需要9步，跳4只青蛙

了将河程描述得更清楚，我出了表1。表中L1

L2L3L4表示左岸石柱上落在一起的青蛙的高度位

置°L1在最上面，L4在最下面的位置。引入个

信息就可比容易地看出青蛙占位的束条件。同理

RIR2R3R4也是如此。水中石柱S,也分成两个

高度位置SIS2°荷叶Y无分，因它只允一只

青蛙落在其上°t=0初始亥U,青蛙八人小到大落在石

柱L上°t=l第一步：1#ML跳至荷叶Y上;L上

只剩2#3#4#°T=2第二步；2#ML跳至石柱

S上，在S2位置上，L上只剩3#和4#°T=3第

三步，1#人人丫跳至3,将丫清空。你看，S上有

1#、2#,L上有3#、4#,好象是原来在L上的4

只青蛙，分成了上下两部分，上面的2只通荷叶y

移到了S上°一程是一分二的程。即将L上的一

青蛙，分解两个，每各二只，且将上面的二只移

到了S上°是我可以考形成两个系，一个是L,

Y,R系，一个是S,Y,R系。前者二只青蛙号

5.将上述分析出来的律写成形式的与或点

^include<stdio.h>//命令

intJump(int,int);〃声明有被用函数

voidmain()〃主函数

//土程序始

ints,y,sum;〃