第6章算法基础与实现

第6章算法基础与算法实现上海海事大学2016年9月目

录上海海事大学2016年9月6.1算法初步6.2经典算法6.3算法复杂度6.1

引言上海海事大学2016年9月用计算机求解问题有两个关键：问题的求解方法和程序设

计。能在计算机实现的问题求解方法通常能找出相应的算法。

也就是说，有些方法能用算法求解，进而根据算法设计出程序，从而问题能在计算机上求解。6.2

算法初步算法就是“求解某种问题的任何专门的方法”。所谓算法，是一个有穷规则的集合。它表现为一个解决某个特

定类型问题的运算序列。通俗地讲，算法定义了解决某个问题

的一系列步骤或方法，如果遵循它就可以完成一项特定的任务。算法是定义在逻辑结构上的操作，是独立于计算机的，而它的具体实现是在计算机上进行的。6.2.1

算法的特性上海海事大学2016年9月有穷性一个算法必须是在执行有穷步后结束，且每一步都能在有限的时间内完成。确定性算法中的每一步骤都必须具有确切的定义。有零个或多个输入有一个或多个输出能行性（或称可行性）算法中所有有待实现的运算都必须是能够精确执行，且用纸和笔做有穷次即可完成。AB图6.1

顺序结构开始A=>TB=>A输入A和BT=>B输出A和B结束图6.2

A和B交换上海海事大学2016年9月6.2.2

算法的三种结构1.

顺序结构例6.1

设计一个算法，实现数A和和B的交换。Private

Sub

Form_Click()a=InputBox("输入a数据")b=InputBox("输入b数据")Print"交换之前a="

&a,

"b="&

bt=aa

=

bb

=

tPrint"交换之后a="

&

a,"b="&

bEnd

Sub2

X

+1

X

‡

0X

<

0Y

=

-

X条件ABYN图6.3选择结构NY开始输入xx≥0-x=>y2*x+1=>y输出y结束图6.4

求解表达式流程图上海海事大学2016年9月2.

选择结构选择结构，或称为分支结构，它根据给定的条件判断选择哪一条分支，执行相应的步骤。例6.2

设计求解如下表达式的算法。Private

Sub

Form_Click()x=InputBox("输入x数据")If

x

>=

0

Theny

=

2

*

x

+

1Elsey

=

-xEnd

IfPrint

"y="

&

yEnd

Sub3.

循环结构循环结构，它又称重复结构，即反复执行某一部分的操作。循环结构有两类：NY条件A图6.5

当型循环结构YNA条件图6.6

直到型循环结构上海海事大学2016年9月例6.3设计在10个数中选出最大数和最小数并输出的算法。Private

Sub

Form_Click()x=Val(InputBox("输入第1数据"))Print

x;Min

=

xMax

=

xFor

i

=

2

To

10x=Val(InputBox("输入第"&

i

&"数据"))Print

x;If

x

>

Max

Then

Max

=

xIf

x

<

Min

Then

Min

=

xNext

iPrintPrint"最大值=";Max,"最小值=";MinEnd

SubNYYNYN开始读第一个数=>xx=>maxx=>min2=>i读下一个数=>xmax<xx=>maxx=>minmin>xi+1=>ii≤10输出max、min结束图6.7

求最大值、最小值2016年9月上海海事大学6.2.3算法的表示为了表示一个算法，可以用不同的方法。常用的有自然语言、流程图、伪代码和程序设计语言等。1.

用自然语言表示算法自然语言（Natural

Language）就是人们日常使用的语言，可以使汉语、英语或其他语言。例6.4

求任意两个正整数的最大公因数的算法。我们先来看一下著名的欧几里德算法。古希腊数学家欧几里德曾出了求解两个数的最大公因子的算法，用自然语言描述如下：步骤1：输入两个正整数，分别放在变量P和Q中。步骤2：如果P<Q

，则交换P和Q的值（T=P，P=Q，Q=T）。2016年9月步骤3：将P/Q的余数放在R中（R=P

mod

Q）。步骤4：如果R等于0，则执行第6步，否则执行第5步。步骤5：让P=Q，Q=R，执行第3步。步骤6：输出Q的值。上海海事大学流程图（Flow

Chat）也称为程序框图，是用几种几何图形、线条和文字来表示不同的操作和处理步骤。欧几里德算法用流程图如图6.9。Y结束输入p、qp>qNp=>t,

q=>p,

t=>qp

mod

q=>rYr=0Nq=>p,

r=>q输出q开始图6.9

欧几里德算法2.用流程图表示算法2016年9月上海海事大学伪代码（Pscudo

Code）介于自然语言和计算机语言之间，用你熟悉的计算机语言的语句加上自然语言构成（尽可能地融入编程语言的函数和语法）。Read

p,qIf

p<q

than

t=p:

p=q:

q=tr=p

mod

qdo

while

r<>0p=q:

q=rr=p

mod

qloopprint

q3.

用伪代码表示算法2016年9月上海海事大学程序设计语言（Programming

Language）表示算法就是用计算机高级语言编写程序，程序是可以在计算机上经过编译、连接、运行得出结果的算法表示。下面是用Vb程序设计语言实现欧几里德算法。Private

Sub

Form_Click()p=InputBox("输入p")q=

InputBox("输入q")'

m>nIf

p

<

q

Thent

=

p

:p=

q:

q

=

tEnd

IfDor

=

p

Mod

qIf

r

=

0

Then

Exit

Dop

=

qq

=

rLoopPrint "最大公约数为";qEnd

Sub4.

程序设计语言2016年9月上海海事大学6.3

经典算法6.3.1

求和求和是计算机程序设计中经常用到的一个算法。10012

3

41

-

1

+

1

-

1

+

-YN计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。对于一个给定的问题，需要找到行之有效的算法。开始0=>sum1=>k1=>signk≤100sum+sign*1/k=>sumk+1=>k-sign=>sign输出sum结束Private

Sub

Form_Click()Dim

k,

sign

As

IntegerDim

sum

As

Doublesum

=

0sign

=

1Fork

=

1

To

100sum

=

sum

+

sign

*

1

/

k'Print

sign

*1/

ksign

=

-signNext

kPrint

sumEnd

Sub图6.10求和流程图2016年9月上海海事大学++1

+

2

+

3

+ +

n11

+

2 1

+

2

+

31

1s

=

1

++

-

+上海海事大学2016年9月1

1

13

5

74p

»

1

-思考：如何计算下式：i=0

i!

i=1

i!¥

me

=1+

1

+

1

+

1

+...+1+...

=1

1

1»

+1!

2!

3!

i!NY开始1=>t1=>kk≤5t×k=>tk+1=>k输出t结束图6.11

累乘流程图上海海事大学2016年9月6.3.2累乘累乘就是求一系列数的乘积，即在循环中使用乘法运算。例6.6

计算5！分析：n!=1×2×3×…×nPrivate

Sub

Form_Click()Dim

k,

t

As

Integert

=

1For

k

=

1

To

5t

=

t

*

kNext

kPrint

tEnd

Sub思考：如何计算下式6.3.3

穷举法“穷举法”也称为“枚举法”，它的基本思想是，根据所提出的问题，列举所有可能的情况，并依据题目的部分条件确定答案的大致范围，然后在此范围内对所有可能的情况逐一验证，直到全部验证结束为止。若验证后有符合题目条件的情况，则是本题的一个答案；若验证后均不符合题目的条件，则无解。例6.7

百元买百鸡问题。假定公鸡每只5元，母鸡每只3元，3只小鸡1元。现在有100元钱要求买100只鸡，列出所有可能的购鸡方案。假设公鸡、母鸡、小鸡各为x、y、z只，根据题目要求，列出方程为：x+y+z=1005x+3y+z/3=100三个未知数，两个方程，此题有若干个解。根据题意不难看出，100元钱最多可以买20（0~20）只公鸡，或者33（0~33）只母鸡，而z=100-x-y将其作为约束条件，列出全部购买方案。解决此类问题采用“枚举法”，把每一种情况都考虑到。计算机工作时就是将上述34*21种方案全部虑一遍，找出并输出符合百钱买百鸡条件的结果，该算法的流程图如图6.12所示。2016年9月NYYNN开始y≤33Y0=>yx≤20100-x-y=>z5*x+3*y+z/3=100输出x,y,zy+1=>yx+1=>x0=>x结束图6.12

百元买百鸡流程图Private

Sub

Form_Click()Dim

x%,

y%,

z%For

x

=

0

To

20For

y

=

0

To

33If

5

*

x

+

3

*

y

+

(100

-

x

-

y)

/

3

=

100

ThenPrint

x,

y,

100

-

x

-

yEnd

IfNext

yNext

xEnd

Sub2016年9月上海海事大学例6.8

给定一个数m，判断m是否素数。判别某数m是否为素数最简单的方法是：对于m从i=2，3，…，m-1判别m能否被i整除，只要有一个能整除，m不是素数，否则m是素数。YYYNNN开始输入m2=>ii<mm能被i整除i≥mm不是素数m是素数i+1=>i结束上海海事大学2016年9月图6.14

判别m是否素数Private

Sub

Command1_Click()Dim

i

As

Integer,

m

As

Integerm=Val(InputBox("输入一个正整数:"))For

i=2

To

m-1If

(m

Mod

i)

=

0

ThenPrint

m

&"能被"&

i

&"整除，该"&

m

&"不是素数"Exit

ForEnd

IfNext

i'm不能被If

i>m-1

Then

Print

m

&"是素数"i=2～m-1整除，m是素数，显示

End

Sub思考：如何找出m~n（m<n）之间的所有素数？6.3.4

递推法2n-1nx

=

1

x

-1+1)

·

2nn-1x

=

(x“递推法”又称为“迭代法”，是利用问题本身所具有的某一种递推关系来求解问题。其基本思想是从初值出发，找出新旧值间直到最后值为止存在的关系，从而把一个复杂的计算过程转化为简单过程的多次重复。例6.9小猴子吃桃问题。有一天小猴摘了若干个桃子，当即吃掉一半，还不过瘾，又多一个；第2天接着吃了剩下的桃子的一半后又多吃一个；以后每天都吃尚存桃子的一半零一个，到第10天早上要吃时只剩下一个了，问小猴第1天共摘下了多少个桃子？设第n天的桃子为xn，它是n-1天桃子数的一半减1个上海海事大学2016年9月Private

Sub

Form_Click()Dim

n%,

i%x=1

'第10天的桃子Print"第10

天的桃子数为:1只"Fori

=

9To

1Step-1x

=

(x

+

1)

*

2Print"第";i;"天的桃子数为:";x;"只"Next

iEnd

SubYN开始1=>x,10=>ii≥1(x+1)*2=>xi-1=>i输出x结束图6.15

小猴子吃桃流程图上海海事大学2016年9月6.3.5

递归法人们在解决一些复杂问题时，为了降低问题的复杂程度，一般总将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归法的基本思想。数学中的许多函数都是用递归来定义的。例6.10

年龄问题。有5个人坐在一起，问第5个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比底3个人大2岁。问第3个人岁数，他说比底2个人大2岁。问第2个人岁数，他说比底1个人大2岁。最后问第1个人，他说是10岁。请问第5个人多大？显然，这是一个递归问题。要求第5个人的年龄，就必须先知道第4个人的年龄，而第4个人的年龄也不知道，要求第4个人的年龄必须先知道第3个人的年龄，而第3个人的年龄有取决于第2个人的年龄，第2个人的年龄取决于第1个人的年龄。而且每一个人的年龄都比其前1个人的年龄大2岁。即:age(5)=age(4)+2age(4)=age(3)+2age(3)=age(2)+2age(2)=age(1)+2age(1)=102016年9月上海海事大学可以用式子表示如下：age(n)=10

n=1age(n)=age(n-1)+2

n>1可以看到，当n>1时，求第n个人的年龄的公式是相同的，它的递推和回推上海海事大学2016年9月'调用递归函数，显示出age(5)=18上海海事大学2016年9月程序如下：Private

Sub

Command1_Click()Print

"age(5)=";

age(5)End

SubPublic

Function

age(n

As

Integer)

As

IntegerIf

n

=

1

Thenage

=

10Elseage

=

age(n

-

1)

+

2End

IfEnd

Function例6.11

利用递归求阶乘n!。根据n!的定义n!=n(n-1)!进行求解。该定义可给出具体形式如下1n(n

-

1)!(n

=

0,1)(n

>

1)n!=

分析：这是一个“递归”问题，从求n!逐层递推为求(n-1)!，求(n-2)!，…，最后成为求1!这个简单问题，再沿着原来分解逆过程逐层相乘进行回归，得出结果。写成递归函数：>1n

*

fac(n

-1)

nn

=1fac(n)

=

14！递归和回归过程如图6.18所示。上海海事大学2016年9月'调用递归函数，显示出fac(4)=24上海海事大学2016年9月程序如下：Sub

Command1_Click()Print“fac(4)=”；fac(4)End

SubFunction

fac(n

As

Integer)

As

IntegerIf

n

=

1

Thenfac

=1Elsefac

=

n

*

fac(n

-

1)End

IfEnd

Function6.3.6排序上海海事大学2016年9月排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。排序可以分为内部排序和外部排序。若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。1.选择排序选择排序算法的基本思想：从待排序的n个数据的列表（R1,R2,R3,…,Rn）中选择最小的元素（按升序）或最大的元素（按降序），将它与R1交换；然后再从剩余的n-1个元素中选出次小的元素（是所有元素第二小的）与R2进行交换；第i趟排序时（R1,R2,…,Ri-1）已排好序，在当前无序的（Ri,…,Rn）中再选出最小（或最大）的元素，将它与Ri元素交换，使（R1,R2,…,Ri）成为有序。以此类推，进过n-1趟排序后，全部数据就递增（或递减）有序了。65

97

76

13例6.12

用选择排序法将N（N=8）个无序数据（49

3827 50）按升序排列。按照选择排序的思想，图6.19说明了排序的全过程。第1趟排序是在N个数中找出最小的数13，然后将13与第1个位置上的数49进行交换；第2趟排序是在剩余的N-1个数中找出最小的数27，然后将27与第2个位置上的数

38进行交换；以此类推，经过N-1趟排序，全部数据就排序好了。初始值为 【49

38

65

97

76

13

27 50】上海海事大学2016年9月第一趟排序后13【38

65

97

76492750】第二趟排序后13

27【65

97

76493850】第三趟排序后13

27

38【97

76496550】第四趟排序后13

27

38

49【76976550】第五趟排序后1327384950【97

65

76】第六趟排序后1327384950

65【97 76】第七趟排序后1327384950

65

76【97】最后排序结果1327384950

65

76

97选择排序程序如下：Private

Sub

Command1_Click()Dim

iA()

As

VariantDim

i,

j,

k,

n,

iMin

As

IntegeriA=Array(49,38,65,97,76,13,27,50)‘利用Array对数组各元素赋值n

=

7For

i

=

0

To

n

-

1iMin

=

iFor

j

=

i

+

1

To

n'进行n-1遍比较'对第i遍比较时，初始假定第i个元素最小'在数组i~n个元素中选最小元素的下标If

iA(j)

<

iA(iMin)

Then

iMin

=

jNext

j'i~n个元素中选出的最小元素与第i个元素交换t

=

iA(i)iA(i)

=

iA(iMin)iA(iMin)

=

tFor

k

=

0

To

nPrint

iA(k);Next

kPrintNext

iEnd

Sub上海海事大学2016年9月2.冒泡排序冒泡排序的基本思想：将待排序的n个数据列表（R1,R2,R3,…,Rn）依次比较相邻的两个数，将数据值小的放在前

面，数据值大的放在后面。这样值小的就会像冒泡一样逐步升起。按此方法对数据经过一轮比较移位后成为一趟冒泡，第1趟冒泡的效果是将数据值最最小的元素交换到了最前的位置。n个数据最多需要进行n-1趟冒泡。算法描述：将待排序的n个数据放入列表（R1,R2,R3,…,Rn）第1趟：从列表的结尾处开始，依次比较相邻的两个数值的大小，若发现小者在下、大者在上，则交换二者的位置。即对每对气泡

(Ri+1，Ri)，若Ri+1<Ri

，则交换Ri+1和Ri的内容。当第一趟扫描完毕时，最小的数据元素被放在位置R1上。第二趟：按上述方法扫描R2到Rn

，扫描的结果将使次小的数存放于R2中。最后，经过n-1趟扫描，可以得到排序后的数据列表。上海海事大学2016年9月例6.13

用冒泡排序法将N（N=8）个无序数据（49

38

65

97

76

1327

50）按升序排列。根据以上算法描述，第一趟冒泡排序过程如图6.21所示。初始数据493865977613

27

50第1次比较493865977613

27

50上海海事大学2016年9月第2次比较第3次比较第4次比较第5次比较第6次比较第7次比较图6.2149

38

65

97

76

13

27

5049

38

65

97

13

76

27

5049

38

65

13

97

76

27

5049

38

13

65

97

76

27

5049

13

38

65

97

76

27

5013

49

38

65

97

76

27

50第1趟冒泡排序第1趟冒泡后13【49

38

65

97762750】第2趟冒泡后13

27【49

38

65977650】第3趟冒泡后13

27

38【49

50659776】第4趟冒泡后13

27

38

49【50657697】上海海事大学2016年9月第5趟冒泡后1327384950【65

76

97】第6趟冒泡后1327384950

65【76

97】第7趟冒泡后1327384950

65

76【97】最后排序结果

13

27

38

49

50

65

76

97图6.22

冒泡排序全过程冒泡排序程序如下：Private

Sub

Command1_Click()Dim

iA()

As

VariantiA=Array(49,38,65,97,76,13,27,50)'利用Array对数组各元素赋值n

=

7'进行n-1遍比较‘从n~i个元素进行两两比较‘若次序不对，则进行交换位置For

i

=

0

To

n

-

1For

j

=

n

Toi

+1

Step

-1If

iA(j)

<iA(j

-

1)

Thent

=

iA(j)iA(j)

=

iA(j

-

1)iA(j

-

1)

=

tEnd

IfNext

jFor

k

=

0

To

nPrint

iA(k);Next

kPrintNext

iEnd

Sub上海海事大学2016年9月3.

插入排序插入排序方法的基本思想是：把n个待排序的数据{R1，...，Rn}分为有

序和无序两个序列，开始时，有序序列为{R1}，无序序列为{R2，...，Rn}，假定当插入第i个数据时，前面的R1，R2...，Ri-1已经排好序了，而后面的Ri，Ri+1，...，Rn仍然无序。这时将Ri与Ri-1进行比较，若Ri小于Ri-1，则将Ri-1向后移动一个单元；再用Ri与Ri-2比较，若Ri小于Ri-2，则将Ri-2向后移动一个单元，依次比较下去，直到找到插入位置即将Ri插入。按此方法，把无序列表的数据元素逐个插入到有序表中。例6.14

用插入排序法将N（N=8）个无序数据（49

38

65

97

7613

27

50）按升序排列。按照插叙排序的思想，图6.24说明了插入排序的全过程。初始数据【49】38 65

97

76

13

27

50第1步【3849】65

97

76

132750第2步【3849

65】97

76

132750第3步【3849

65

97】76

132750第4步【3849

65

76

97】132750第5步【13

38

49

65

76

97】27

50第6步【132738496576

97】50第7步【132738495065

76

97】最后结果13

27

38

49

50

65

76

97图6.24

插入排序过程2016年9月插入排序程序如下：Dim

n

As

IntegerPrivate

Sub

Text1_keypress(keyascii

As

Integer)Static

bb!(1

To

20)Dim

i%If

n

=

20

ThenMsgBox"数据太多!",1,"警告"EndEnd

IfIf

keyascii

=

13

Thenn

=

n

+

1insert

bb(),

Val(Text1)'打印刚输入的数

'打印插入后的有序数Picture2.Print

Text1For

i

=

1

To

nPicture1.Print

bb(i);Next

iPicture1.PrintText1

=

""End

IfEnd

SubSub

insert(a()

As

Single,ByValx!)Dim

i%,

j%j

=

1'查找x应插入的位置j'n-j个元素往右移Do

While

j

<

n

And

x

>a(j)j

=

j

+

1LoopFor

i

=

n

-

1

To

j

Step

-1a(i

+

1)

=

a(i)Next

ia(j)=x

'x插入数组中的第i个位置

End

Sub2016年9月6.3.7查找上海海事大学2016年9月查找是在给定的列表中找到指定的数据及该数据在列表中的位置。使用不同的查找算法，所花费的时间是有很大差别的。查找的算法很多，而顺序查找和二分查找是常见的两种查找方法。1.

顺序查找顺序查找是最普通也是最简单的查找算法。其基本思想是：从数据列表的第1个元素开始将给定的数据与列表中元素逐个进行比较，若某个元素的值和给定数据相等，则查找成功；反之，若直到最后一个元素都没有和给定数据相等的，则说明列表中不存在满足条件的数据，查找失败，结束查找。顺序查找算法的vb程序描述如下：上海海事大学2016年9月'单击命令按钮运行该事件函数Private

Sub

Command1_Click()Dim

b()

AsVariantb=Array(18,85,21,34,48,56,77,43,87,29)

'利用Array对数组各元素赋值Dim

i,index,

key

AsIntegerkey=Val(InputBox("输入要查找的数:"))For

i=0

To

9'找到，元素的下标在index中，结束查找'找不到，index形参的值为-1If

key

=

b(i)

Thenindex

=

iExit

ForEnd

IfNext

iIf

i

>

9

Then

index

=-1Print

indexEnd

Sub在该算法中，当查找列表中的元素个数n很大时，其平均查找长度为n/2。即每次查找平均要比较一半数据元素。2.

二分查找二分查找又称折半查找，是一种查找效率较高的查找方法，该方法要求数据列表中的数据是有序的。二分查找的基本思想是：由于查找列表中数据元素是有序的（假设

递增有序），则在查找时不需逐个比较，而采用跳跃的方式即先与“中

间位置”的数据比较，若相等，则查找成功；若给定值大于“中间位置”的数据时，则在后半部分继续进行二分查找；否则在前半不继续进行二

分查找。二分查找的过程是：先确定待查数据元素所在区域，然后逐步缩小区域，直到查找成功或失败为止。假设待查元素所在区域的下界为low，上界为high，则中间位置mid=(low+high)/2（整除）。二分查找算法的自然语言描述如下：①设置查找区域的下界为low=0，上界为high=表长度值-1；②设置中间位置mid=（low+hig）/2。③若mid元素值等于给定值Key，则查找成功，返回mid

；④若Key>mid元素值，则令low=mid+1后执行步骤②；⑤若key<mid元素值，则令high=mid-1后执行步骤②；⑥若当low=high时，key不等于mid元素值，则查找失败。上海海事大学2016年9月例6.15

在给定的10个数{8

15

21

34

48

56

77

81

87

99}的列表中查找数77。①Low=0，high=9，mid=(0+9)\2=4，将77与48比较，77大于48，所以忽略48之前的一半列表；②Low=4+1=5，high=9，mid=(5+9)\2=7，将77与81比较，77小于81，所以忽略81之后的一半列表；③Low=5，high=7-1=6，mid=(5+6)\2=5，将77与56比较，77大于56，所以忽略56之前的一半列表；④Low=5+1=6，high=6，mid=(6+6)\2=6，将77与77比较，相等查找成功。二分查找的优点是比较次数少、查找速度快。它的平均查找长度为log(n+1)-1，但快速查找所付出的代价是要对数据元素进行排序，排序一般是很费时的，所以

二分查找适用于一经建立就很少变动而又经常需要查找的有序表。上海海事大学2016年9月二分查找程序如下：Private

Sub

Command1_Click()Dim

low,high,

mid

,index

As

IntegerDim

b()

As

Variantb=Array(8,

15,

21,

34,

48,

56,

77,

81,

87,

99)

‘利用Array对数组各元素赋值low

=

0:

high

=

9key=Val(InputBox("输入要查找的数据"))Do

While

high