基础算法.docx

基础算法.docx

《基础算法.docx》由会员分享，可在线阅读，更多相关《基础算法.docx（187页珍藏版）》请在冰点文库上搜索。

基础算法

基础算法

一、算法分析

算法的复杂性

算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。

一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。

计算机的资源，最重要的是时间和空间（即存储器）资源。

因而，算法的复杂性有时间复杂性和空间复杂性之分。

不言而喻，对于任意给定的问题，设计出复杂性尽可能低的算法是我们在设计算法时追求的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是我们在选用算法适应遵循的一个重要准则。

因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。

简言之，在算法学习过程中，我们必须首先学会对算法的分析，以确定或判断算法的优劣。

1.时间复杂性：

例1：

设一程序段如下（为讨论方便，每行前加一行号）

（1）fori:

=1tondo

（2）forj:

=1tondo

（3）x:

=x+1

　　......

　　试问在程序运行中各步执行的次数各为多少？

　　解答：

行号　次数（频度）

（1）　　　n+1

（2）　　n*（n+1）

（3）　　n*n

　　可见，这段程序总的执行次数是：

f（n）=2n2+2n+1。

在这里，n可以表示问题的规模，当n趋向无穷大时，如果  f（n）的值很小，则算法优。

作为初学者，我们可以用f（n）的数量级O来粗略地判断算法的时间复杂性，如上例中的时间复杂性可粗略地表示为T（n）=O（n2）。

2.空间复杂性:

例2:

将一一维数组的数据（n个）逆序存放到原数组中,下面是实现该问题的两种算法:

算法1:

fori:

=1tondo

      b[i]:

=a[n-i+1];

    fori:

=1tondo

      a[i]:

=b[i];

算法2:

fori:

=1tondiv2do

       begin

      t:

=a[i];a[i]:

=a[n-i-1];a[n-i-1]:

=t

       end;

算法1的时间复杂度为2n,空间复杂度为2n

算法2的时间复杂度为3*n/2,空间复杂度为n+1

显然算法2比算法1优，这两种算法的空间复杂度可粗略地表示为S（n）=O（n）

信息学比赛中，经常是：

只要不超过内存，尽可能用空间换时间。

二、编程的一般原则

编程序首先就是强调程序的可维护性，即易读、易用、便于修改。

即使是初学者，也要遵循编程的一般原则，从一开始就养成良好的编程习惯。

良好的编程习惯包括以下几点:

（1）为基本常数定义常量标识符。

例如，当我们作一些近似计算时，经常要先定出取多少位有效数字，程序中可能有多个地方要根据这个位数来控制执行过程。

那么，把这个预定的有效数字的位数在程序的说明部份写义成一个常量标识符，作为该常数的同义词。

这样做的好处是常量的含义清楚，使程序的易读性增强。

而且当需要修改数值时，仅需在说明部分修改一下而无需各处去把它寻出来修改。

例如，你可以定义。

Const

YouXiaoShuZhi=4;

用“YouXiaoShuZhi”来代替直接写入4。

这样做会使程序稍长些，但好处是显然的。

因为4不一定是代表有效数字的，如果程序中好几处地方出现4，那么何处的4代表有效数字，何处的不是，你还得花功夫去搞清楚。

而且当有效数字由4位提高到6位时，如果定义了常量标识符的话，只要在说明部分改一个数字就可以了，否则你就得在程序一个一个地找出0应修改的数字4来把它改为6，万一有一处改错了或找漏了，程序就不能正确运行了。

（2）按变量的含义取定变量名。

初学者常常简单地把变量名写为单个的字母，但这并非是个好主意。

例如半径、面积之类的变量，写成Radius和Area则比简单地用x、y易读得多，如果需要多个单词才能表达清的意思，则可以用大小写混合（每个单词的第一个字母大写）的方法来表示。

例如，表示学生人数这个变量，可以写成“NumberOfStudents”。

（3）注意程序的书写格式。

坚持按缩进规则书写和键入程序，适当地使用空行，在必要的地方加些注释。

总而言之，你的程序应当尽量做到段落分明，这样对提高易读性很有好处的。

（当然，按缩进规则键入程序时注意不能太靠右，否则大量的程序超过了屏幕的右边界，反而增加了阅读程序的麻烦）。

（4）注意合理写出提示信息，安排尽量合式的输出格式，使人机之间的交流得以顺利进行。

例如，你要输入一个圆的半径，你当然可以只写一句

Readln（Radius）;

便足够，但如果在它前面加上一句

Write（'Enterradiusofacirde.'）;

使用者就会接到提示而输入一个圆的半径，而仅仅写了一个Readln过程可能会令使用者面对一个空白的屏幕不知所措。

除了程序的易读性和可靠性之外，我们还需要注意的是:

（1）只使用顺序结构、分支结构和循环结构，一般不要使用转移语句（GOTO），随意使用GOTO语句容易使程序的结构混乱，使程序难读难调试难修改。

（2）习惯“自顶向下，逐步求精”的设计方法。

自顶向下的方法首先定义程序的整个体系结构，然后具体实现其中的每一细节。

这个方法的方法的实质是，把求解的问题理解好之后，把它分解为若干个意义明确的，相对独立的子任务，完成所有这些子任务后，问题便得以解决。

对于这些子任务来说，各自所牵涉的范围已较前缩小，职能也更具体。

如果这些子任务中还有比较复杂的功能，我们把它分解为范围更小，职能更加具体的小任务。

这样，一直细分到每一个最基本的任务都能用简明的语句（包括过程语句）满意地实现为止。

这就是逐步求精的过程。

当然，这个过程还包括各层之间、各子任务之间的数据组织和数据交流，涉及到解决各基本的子任务采用的算法。

在程序的高层，子任务的完成往往由子程序的调用来表示。

不妨把子程序的名字看成是一种抽象的综合操作。

而子程序的定义说明则体现了在较低层次上程序的具体实现过程。

三、算法的多样性

要进行程序设计，最主要的就是设计算法。

著名的计算机科学家N·沃思曾经提出过一个著名的公式：

程序=算法+数据结构。

这就是说，程序离不开算法。

算法可以简单理解为解决问题的方法和具体步骤。

显然，不同的问题会有不同的算法，即使是同一个问题，也可能会有多个完全不同的算法。

不断理解和掌握解决各种问题的典型算法，是学习程序设计的主要方面。

例6-1求非负数K的算术平方根

（即求方程x2=k的非负根,k>=0）。

我们用各种不同的方法来寻求问题的解答。

[解法1]:

直接用标准函数sqrt（k）可得。

优点:

工具现成,直截了当。

缺点:

如果你对函数给出的精度不满意,希望提高精度,却完全无法可想,因为你不知道sqrt（k）的值到底是如何求出来的。

[解法2]:

牛顿迭代法。

把

改写成x=。

等式右边的x的任一个非0值都可以计算出左边的x,把计算所提的新x代入右边,又可算得新的x值,重复这个过程x就会逐步逼近真正的K值。

（对一般方程f（x）=0,牛顿迭代的公式是

。

）

优点:

算法简单,编程容易,如果要提高算法的精度,只须解决高精度数加法和除法即可。

缺点:

这种方法的理论根据比较深奥，算法为什么成立,不是三言两语能讲清楚的。

主要程序段落：

X:

=1;{不管K多大或绝对值多么小,都可先取1}

FORI:

=1TO50DOX:

=X/2+K/2/X;{循环50次是经验值}

WRITELN（，RESULTIS:

，,X）;

这里的循环次数50是个保险值,经验上循环20次就可以满足需要,但循环多少次才满足要求,得视初值的选择（不一定选1）和K值的大小而定。

另一种方法是首先提出精确度e，希望通过迭代求得的平方根与真正的平方根之间的误差不超过e。

为保证这点，一般通过控制|xn+1-xn|

ProgramLiu1_2;{牛顿迭代法求K的值}

Var

K,Sqrtk:

Real;{被开方数和结果}

Ofite:

Integer;{迭代次数}

Oldx,Newx:

Real;{前后两次迭代值,用于误差控制}

ConstE=1e-8;{精确度}

Begin

Write（'EnterRealK（K>0）:

'）;Readln（K）;

Ofite:

=0;Newx:

=1;{初值Newx取1}

Repeat{迭代开始}

Inc（Ofite）;{计算迭代次数}

Oldx:

=Newx;{记下前一次的迭代值以便计算误差}

Newx:

=（Oldx+K/Oldx）/2;{迭代}

Until（Abs（Newx-Oldx）50）;

{当|Xn+1-Xn|

为防止精度E要求太高而运算无法达到而形成死循环,再加上一个控制条件;迭代次数不多于50}

Sqrtk:

=Newx;{得到结果}

Writeln（'TheSquareRootOf',K:

14:

8,'Is',Sqrtk:

12:

8,'No.Ofite:

',Ofite）;

IfOfite>50ThenWriteln（'':

10,'MayBeUnusable!

'）;

{如果迭代次数超过50次,则精度未被满足。

}

End.

[解法3]:

逐步逼近法。

先取增量C,（如C=100）然后从X=0开始,每次增加C计算x2的值,肯定可以求出某一个x1使得

。

如果等号成立,即求出了准确解。

否则取增量C为原来的

从x=x1开始,每次加C又可求出某点x2,使

。

于是随着这一过程的不断执行,可使某一xn成为

的良好近似值。

[优点]:

方法直观,道理明白。

[缺点]:

编程稍有点麻烦。

如果要做高精度运算的话，程序运算量较大。

[程序]

ProgramLiu1_3;

Var

X,X1,X2,K,C:

Real;

Const

E=1E-8;

Begin

Write（'K='）;Readln（K）;

C:

=100000;

X:

=0;X1:

=0;X2:

=0;

Repeat

C:

=C/10;

X:

=X1;

Repeat

X1:

=X;

X:

=X+C;

X2:

=X*X;

UntilX2>=K;

UntilC

Writeln（'ResultIs',X:

12:

8）;

End.

解法4:

逐次减奇法。

这里我们利用了一条数学式：

　　n2=1+3+5+...+（2n-1）。

如果知道k=n2,要求n值的话,我们可以把k逐次减去1,3,5,...直至再减的话k就变成负数为止。

把所减的最后一个奇数加1后除以2,所得的就是原来的k的平方根。

如果原来的k并不是完全平方数的话,那么所得的就只是不大于N的近似值。

如果要提高运算精度的话,还得在小数点后补0再算。

这个算法的设想很好,但目前还很粗,得把它精细化。

首先,上述的数学公式是针对整数N的,如果被开方数K是小数的话这个方法就得改造。

解决这个问题的一个方法是，记下K的小数点的位置，然后把K除去小数点当成整数来处理。

完成这个任务可以有两种思路:

①把K与int（K）比较,如果它们不等,则K:

=K*100,直到它们相等为止。

记下乘法进行的次数t。

这样就可以对此K值运用上公式了,假设所减的最后一个奇数是P的话,则把连续t次除以10就得到近似解。

②把K值转换成一个定长的字符串,例如规定这个字符串的整数和小数自10位,这里有一个标准过程把数值K转化为字符串S:

str（k:

21:

10,s）。

k:

21:

10的意思是要求K值转换后总共有21个字符,其中小数部分占用10个字符,那么去掉小数点所占的字符后,整数部份也是10个字符。

如果K值的整数部份不足10位,则多余的位数用空格补足,如果K的小数不足10位,则多余的位数用0补足。

i值：

K的整数位：

的整数位：

然后从字符串S的左边开始逐个字符考查,直到这个字符不是"0"、"."、""假设在S左边第一个异于上述三个字符的位是第i位,那么就可判知K有多少位整数:

（S的第11位肯定是小数点）。

可以从字串S中抽出有效数字作为一个整数,然后逐次减去奇数.那么最后一个奇数P求得之后,把

按应有的整数部分加上小数点就可以。

这个整数位数J可以根据i值算出:

（0位整数的意思是说整数部分为0而第一位小数非0，1的意思是整数部分和第一位小数均为0而第2位小数非0，....，n的意思是直到第n位小数均为0而第n+1位小数非0）。

用这个方法,求出最后所减的奇数P之后,把p+1/2重新命名为p,把它再次变为字串（这时因为P为整数,求得的字串完全是P的有效数字）。

测出这个字串的长度f,即P为f位有效数字的整数,要使它在j位整数后添一个小数点。

得比较f和j的大小,若f>j,则要求P连续f-j次除以10（除法不能在整型数的P中进行,事前应把P赋给一个实型数,然后对此实型数来进行）。

否则的话,应当把P值连续j-f次乘以10。

如此解决了小数点问题之后,我们就可以着手编程了。

虽然如此编出的程序比较简单,但是难以达到较高的精度。

因为所减去的奇数越来越大，当它超过一个长整型数的许可范围，运作就不能再进行下去了。

因此，我们要把逐次减奇变为分段减奇。

即把被开方数从小数点开始，每两位分为一段，然后按段减去相应的奇数，这样的话，原则上可以不断地在后面补0而进行到任意位的精度。

我们的算法可用以下流程来描述：

　　1.L:

=8,如果k不是完全平方数,则取l位有效数字。

2.读入被开方数k,如果k为负数则停机。

3.执行str（k:

21:

10,s）把k值转化为字串S

4.探测S中左起哪一位首先出现1～9这些数字,记这个位为i。

5.根据i值计算出结果的整数位数j（计算方法前面已经给出）。

6.因为分段是从小数点开始两位地分段的,所以如果i值在小数点前为偶数的话,要把i值减一,在小数点后则i值为奇数时减1,这样才可以在S中从第i位开始每次截取2位。

7.开始分段减奇的过程。

首先置初始状态：

执行val（copy（s,i,z）,a,e）让a得到s串的前两位;

t:

=0（t用来统计运算进行了多少段。

每段是答案中的1位）；

p:

=0（p是减数,它将从1,3,5,...这样变下去）。

　　　flag:

=Ture（flag是一个记号,如果a已变为0,且后面各位都设有非0数字的,flag

取值false,以使这个逐次相减的过程终止）。

　　8.当flag为Ture，或a>0，而且还得求得的有效数字的位数t小于要求的t,重复执行9-13步。

当这条件不满足跳至14步。

9.p:

=p*0（每一段减完之后,把所得的最后的减数乘以10以便进行以后的减法）

10.判断被减数a是否大于减数P,当结果为:

a>p，则p:

=p+1让p取到该段的第1个奇数。

然后只要当a>=p，就进行a:

=a-p，p:

=p+2（即p增加2），这两个操作。

（因为最后一次p增加2之后并没有被a去减,所以最后的减数应是当前p值减2）。

把最后所得的奇数加1,以便继续。

a<=p，减法不能进行,无动作。

11.t增加1（记录结果已多了1位）

i增加2（轮到下一段）,但当i=11时是小数点的位置,让i变到12。

12.从第i位开始到第21位,如果有一位大于'0',则flag为真,（'1'～'9'都大于'0',而空格和小数点都小于'0'）,否则flag为假。

13.执行val（copy（s,i,z）,f,e）;a:

=a*100+f，

让本段剩余值与下一段值合并为新的被减数a。

14.循环结束,得到了最后的奇数。

（第10步时这个最后所得的奇数已被加了1,所以循环之后所得的P值已是被减的最后的奇数加1）

　　　让p:

＝p/2，则p为不计小数点的结果。

　　15.根据p的位数和它应有的整数位数j,补回小数点。

16.打印结果。

结束。

　　[程序]

ProgramLiu1_4;

Var

K:

Real;

I,J,F,T,L,E:

Integer;

A,P:

Longint;

S:

String[21];

Flag:

Boolean;

Begin

L:

=8;

Write（'K='）;Readln（K）;

IfK>=0Then

Begin

Str（K:

21:

10,S）;F:

=0;I:

=1;

While（Copy（S,I,1）=''）Or（Copy（S,I,1）='.'）Or（Copy（S,I,1）='0'）Do

Inc（I,1）;

IfI<11ThenBeginJ:

=6-（I+1）Div2;IfOdd（I+1）ThenDec（I）End

ElseBeginIfI=22ThenJ:

=1ElseJ:

=6-IDiv2;

IfOdd（I）ThenDec（I）End;

Val（Copy（S,I,2）,A,E）;P:

=0;T:

=0;Flag:

=True;

While（FlagOr（A>0））And（T

Begin

P:

=P*10;

IfA>PThenBeginP:

=P+1;

WhileA>=PDoBeginA:

=A-P;Inc（P,2）End;

P:

=P-1;

End;

Inc（T）;

Inc（I,2）;IfI=11ThenI:

=12;Flag:

=False;

ForF:

=ITo21DoIfCopy（S,F,1）>'0'ThenFlag:

=True;

Val（Copy（S,I,2）,F,E）;

A:

=A*100+F;

End;

P:

=PDiv2;Str（P,S）;

F:

=Length（S）;K:

=P;

IfF>JThenForI:

=1ToF-JDoK:

=K/10

ElseBeginForI:

=1ToJ-FDoK:

=K*10;F:

=JEnd;

Writeln（'ResultIs',K:

F+1:

F-J）;Readln

End;End.

解法5:

用数学课本介绍的开平方的方法.（略）

我们对一个很简单的问题给出了5种截然不同的解法,这个问题的解法并不止这5种,但最奇特应是牛顿迭代法吧,它既简单又好用。

这说明了算法是多样的，问题的解决依赖于采用什么算法,选用一个合适的算法是很重要的。

第三节注意减少数值计算的误差

虽然电脑是前所未有的计算工具，它的运算速度快，而且通常都很准确。

但是，并非使用电脑来进行计算就可以高枕无忧。

一方面，程序设计时的一个小小的疏忽就可以“差之毫厘而谬以千里”。

另一方面，即使程序设计思路正确，算法无懈可击，算出来的结果也不一定就可靠。

我们先来看一个例子。

例6-2求方程X2-（1017+1）X+1017=0的解。

[说明]：

一方面，很容易知道这个方程的两个解分别是1和1017。

但是，这是一个二次方程，它是有求根公式的，下面我们就用求根公式

X1,2=

来求解，这里A=1，B=-1017-1，C=1017。

[程序]

ProgramLiu2;

VarA,B,C,D,X:

Real;

Begin

A:

=1;

B:

=-1e17-1;

C:

=1e17;

D:

=Sqrt（B*B-4*A*C）;

Writeln（'X1=',（-B+D）/2/A）;

Writeln（'X2=',（-B-D）/2/A）;

End.

[运行]

X1=1.0000000000E+17

X2=0.0000000000E+00

从运行结果可以看到，我们求出来的两个解只有X1=1.0000000000E+17是正确的，而另一个解应当为1却变成了0。

显然求根公式是没有错的，那么问题出在哪里呢？

原来，程序里不小心把两个相差得太远的数相加减了。

一个是B的值-1017-1，1017与1的和用只有7、8位有效数字的Real型变量是无法准确表示的，它只好4舍5入处理，这样一来，1017与1相加其实是把1丢掉了。

同样的事情在计算D值时也出现了一次（B*B与4*A*C相差太远，两者相减实际上得到的还是B2，4AC给丢弃了）。

这样，由于计算上的误差，我们计算结果根本不对。

所以，注意控制误差是使用计算机进行计算时必须注意的，一方面要注意变量的有效数字范围，另一方面还要注意有恰当的计算步骤。

例6-3计算下式的值：

。

[说明]计算这个算式并不困难，但也有几种不同的思路。

我们尝试用3种方法来进行：

A．分别求出分子的乘积A和分母的乘积B，然后再把A除以B；

B．为了避免出现过大的中间结果，把算式按下步骤计算：

1/2/4/6/.../100*3*5...*99。

C．把算式整理为如下步骤计算：

（1/2）*（3/4）*（5/6）*...*（99/100）。

[程序A]

ProgramLiu3A;

VarA,B,I:

Longint;

X:

Real;

Begin

A:

=1;B:

=1;I:

=1;

WhileI<100Do

Begin

A:

=A*I;

I:

=I+1;

B:

=B*I;

I:

=I+1;

End;

Writeln（'A=',A,'B=',B,'A/B=',A/B）;

End.

[运行]

A=-373459037B=0A/B=Runtimeerror200at0BEE:

012E.

[程序B]

Programliu3B;

VarI:

Integer;

X:

Real;

Begin

I:

=2;X:

=1;

WhileI<=100Do

Begin

X:

=X/I;

Inc（I,2）;

End;

I:

=1;

WhileI<100Do

Begin

X:

=X*I;Inc（I,2）;

End;

Writeln（X）;

End.

[运行]

0.0000000000e+00

[程序C]

ProgramLiu3c;

VarI:

Integer;

X:

Real;

Begin

I:

=1;X:

=1;

WhileI<100Do

Begin

X:

=X*I/（I+1）;

Inc（I,2）;

End;

Writeln（'ResultIs',X）；

End.

[运行]

ResultIs7.9589237387e-02

从这3个程序的运行结果来看程序A和程序B都不正确。

程序A还发生了意想不到的错误：

在运行发现了用0做除数，（这是因为B超出了允许范围之后发生的一种意外）。

把程序A的变量A和B的类型改为REAL的话，错误会更明显，因为运行时报告发生的错误是“Error205:

Floatingpointoverflow.（浮点上溢出，即这里的浮点运算超过了变量的上界）。

而程序