計(jì)算機(jī)程序設(shè)計(jì)基礎(chǔ)-第六講

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

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

法而言并不涉及高深數(shù)學(xué)知，只不初學(xué)者要建

立起概念不十分容易。S

我先M一個(gè)最的例子入°W

用一算法求i

定：函數(shù)fact(n)=n!g

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

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

已矢口fact(l)=1

了表述得直清晰，我定兩個(gè)點(diǎn)：或點(diǎn)與與

示的直性與思助力。

A“或點(diǎn)”，A依不同條件會(huì)有兩不同的取B

或C。點(diǎn)曾表示

姿

3

與點(diǎn)可能有多個(gè)相的點(diǎn)，可描述下

A點(diǎn)日勺最D日勺，但J不D需先不B和C

M上看先求左的點(diǎn)才能求最右的點(diǎn)的，我

定最右D點(diǎn)的就是A點(diǎn)的°

7

下面畫(huà)出了用和返回的示意

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

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

來(lái)，到了菜心，遇到1的乘，其1,到達(dá)了

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

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

了把個(gè)得再透一點(diǎn)。我畫(huà)了如下的流程

10■

11

了形象地描述程，將上改畫(huà)成下

fact(3)

在個(gè)中“內(nèi)”與“外”有著相同的構(gòu)。它之

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

了一步清的概念，將與推做一比。仍以

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

如求3!1

初始條件fact(l)=1

fact(2)=2*fact⑴=2

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

相當(dāng)于隊(duì)菜心“推到”外。而算法的出點(diǎn)不

放在初始條件上，而放在求解的目上，隊(duì)所求

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

界(即初始條件)。就本例而言，者會(huì)算

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

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

出了明的越性。下面我將會(huì)看到，算法比

符合人的思方式，性強(qiáng)，可將描述得扼

要，具有良好的可性，易于理解，多看來(lái)相當(dāng)

,或以下手的，如果能使用算法就會(huì)使

得易于理。下面一個(gè)盡人皆知的例子哈

B(Hanoi)一

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

天把三根柱子上的金倒來(lái)倒去，原來(lái)他是想把

64個(gè)一個(gè)比一個(gè)小的金隊(duì)一根柱子上移到另一

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

移一只，且大不得落在小上面。有人會(huì)得

很，真的手移就會(huì)，如以每秒移一只子

的，按照上述將64只子隊(duì)一個(gè)柱子移至另

上一個(gè)柱子上，所需3800年°「

15

3、在A柱上有3只子，隊(duì)小到大分1號(hào)，2號(hào)

整體MA移至B,3號(hào)造能一次移至c的機(jī)

步,.^_^=

move(2,A,C,B)

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

一至B°三

步將3號(hào)AAA移至C,一次

—move3fromAtoC二

第(3)步于B上的作一個(gè)整體的2只子，再移

至C°一步

-movef2,B.A.C)

、

目的束條件看，大上可以隨便小，相

反不允。在將1號(hào)和2號(hào)鑄整人人A移至B

的程中m(0,是分解

第(1).1步:moveSteffis^to

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

第3步：move1formCtoB;三,

以上步,將1號(hào)和2號(hào)作整體隊(duì)A移至B,

3號(hào)MA移至C造了條件。同,3號(hào)一旦

到了C,就要考如何將1號(hào)和2號(hào)旁整M

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

解三步

步

第(3).1move1formBtoA;

步

第(3).2move2formBtoC;

步

第(3).3move1formAtoC;20

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

B,但沒(méi)有C是不行的，因第(1)?1步就要

將1人人A移到C,2造條件隊(duì)A移至B,然

后再把1MC移至B?？吹嚼锞湍苊靼捉柚鶦

的含了。因此，在構(gòu)思搬移程的參量，要把3

個(gè)柱子都用上二三

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

―s—

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

考/至U前

究的⑴⑵⑶

步，可以將搬

移程用如下

的與或點(diǎn)表

o

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

一由一叁

n:AtoC

里用與或點(diǎn)的含是分解⑴(2)(3)步°3步是相

的，相互依存的，而且是有序的，隊(duì)左至右行

O

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

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

個(gè)整體MA

⑵出n:AtoC,理解將n號(hào)/\AA移至C,是

直接可解點(diǎn)；

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

個(gè)整體MBA移至C°

里然是一定，當(dāng)著解move(n?l,A,GB)又

可想到，將其分解3步：

第1步：將上面的n?2只子作一個(gè)整體MAB

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

第2步：第n-l號(hào)子直接移至塞即n-l:Ato

B;二

第3步：再籽上面的n?2只子作一個(gè)整體MCA

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

下面，我是以3只子例畫(huà)出的與或°

3

#include<stdio.h>//命令

mtstep=l;〃整型全局量，置1,步數(shù)

voidmove(int,char,char,char);〃嚴(yán)明要用至的被用函數(shù)

voidmain()〃主函數(shù)

〃主程序始

mtn;〃整型量，n數(shù),

printf(n入數(shù)！＞=")；〃提示信息

scanf(H%dH,&n);//入正整數(shù)n

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

move(n/a,,,b,,,c,);//用函數(shù)move(n；a,,,b,,,c,)

〃主程序束

〃以下函數(shù)是被主程序用的函數(shù)

voidmove(intm,charp,charq,charr)〃自定函數(shù)，m,p,q,r形參，m整型量

//p,q,r字符型量

〃自定函數(shù)體始

if(m=l)〃如果m1,直接可解點(diǎn),

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

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);〃直接可解點(diǎn)，出移信息

step=step+l;〃步數(shù)加1

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

〃自定函數(shù)體束

青蛙河

是2000年全國(guó)青少年信息學(xué)奧林匹克的一道。敘述如下

一條小溪尺寸不大，青蛙可以隊(duì)左岸跳到右岸，在左岸有一石

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

R,面也只容得下一只青蛙落腳。有一青蛙人人尺寸上一個(gè)

比一個(gè)小。我將青蛙人人小到大，用1,2,…，n號(hào)°

定初始青蛙只能在左岸的石L上，當(dāng)然是一個(gè)落一個(gè)

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

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

,如有多只同要求一個(gè)落一個(gè)，大的在下，小的在上。于

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

柱R,與左岸的石柱L一允多個(gè)青蛙落腳，但一個(gè)落一

個(gè)，小的在上，大的在下。當(dāng)青蛙人人左岸的L上跳走后就不

允再跳回來(lái)；同，人人左岸L上跳至右岸R,或M溪中荷

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

看起來(lái)，但是如果我真分析，理出思路，就可化

i、化，探索律。先隊(duì)個(gè)再到一般，要善于多個(gè)因

素作分解，孤立出一個(gè)因素來(lái)分析，化易=

：/一^iJ數(shù)]

Juinp(S9y)最多可跳河的青蛙數(shù)

「其中：S河中柱子數(shù)1

「y荷葉數(shù)「

30

再看Jump(S,y)

先看一個(gè)最情況：S=1,y=l

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

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

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

置°L1在最上面，L4在最下面的位置。引入個(gè)

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

RIR2R3R4也是如此。水中石柱S,也分成兩個(gè)

高度位置SIS2°荷葉Y無(wú)分，因它只允一只

青蛙落在其上°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ái)在L上的4

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

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

青蛙，分解兩個(gè)，每各二只，且將上面的二只移

到了S上°是我可以考形成兩個(gè)系，一個(gè)是L,

Y,R系，一個(gè)是S,Y,R系。前者二只青蛙號(hào)

5.將上述分析出來(lái)的律寫(xiě)成形式的與或點(diǎn)

^include<stdio.h>//命令

intJump(int,int);〃聲明有被用函數(shù)

voidmain()〃主函數(shù)

//土程序始

ints,y,sum;〃