第2章 程序的灵魂-算法.ppt

《第2章 程序的灵魂-算法.ppt》由会员分享，可在线阅读，更多相关《第2章 程序的灵魂-算法.ppt（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章 程序的灵魂-算法1.什么是算法确定确定数据结构数据结构确定确定算法算法编写编写代码代码调试并调试并运行运行整理并写出整理并写出文档资料文档资料数据结构+算法=程序数据的逻辑结构和存储结构对数据运算的描述 算法(Algorithm)-是指为解决一个问题而采取的方法和步骤，或者说是解题步骤的精确描述。例1：求1+2+3+100=?1+2+3+4+5+100=5050 (100+1)+(99+2)+(51+50)=101*50=5050 执行算法所需的时间。执行算法所需的存储空间。算法应易于理解，易于编码，易于调试，具有通用性等等。99次加1次加，1次乘例2：求1*2*3*4*5=?方法1：

2、S1：求1*2=2；S2：步骤1的结果2*3=6；S3：求6*4=24；S4：求24*5=120，输出结 果。方法2：S1：使p=1；S2：使i=2；S3：使p*ip；S4：使i的值加1，即i+1i;S5：如果i=5,返回S3，否则输出结 果，结束。例3：求1*3*5*7*9=?方法2：S1：使p=1；S2：使i=3；S3：使p*ip；S4：使i的值加2，即i+2i;S5：如果i=9,返回S3，否则输出结 果，结束。例4：判断2000-2500年中是闰年的年份。闰年的条件能被4整除，便不能被100整除：2004(能被100整除)，且能被400整除：2000算法步骤：S1:2000y;S2:若y

3、能被4整除，不能被100整除，则输出y;S3:若y能被400整除，则输出y;S4:y+1y;S5:若y=2500，转S2，否则算法停止;例5：判断一个大于等于3的正整数是不是素数。素数的条件除了1和自身，不能被其它整数整除：13算法步骤：S1:输入n的值;S2:i=2(i为除数);S3:n被i除，得余数r;S4:如果r=0，表示n能被i整除，则打印n“不是素数”，算法结束；否则转S5；S5:i+1i;S6:如果i0，返回S3，否则结束。算法的确定性判断n是不是素数算法步骤：S1:输入n的值;S2:i=2(i为除数);S3:n被一个整数除，得余数r;S4:如果r=0，表示n能被i整除，则打印n“

4、不是素数”，算法结束；否则转S5；S5:i+1i;S6:如果i=n-1,返回S3；否则打印n“是素数”，结束;3.算法的描述3.1 自然语言3.2 流程图3.3 N-S流程图3.4 伪代码表示3.5 计算机语言表示3.算法的描述3.1 自然语言求1*2*3*4*5=?S1：使p=1；S2：使i=2；S3：使p*ip；S4：使i的值加1，即i+1i;S5：如果i=5，返回S3，否则结束。3.2 流程图输入输出框起止框处理框判断框流程线连接点注释框例：求1*2*3*4*5=?S1：使p=1；S2：使i=2；S3：使p*ip；S4：使i的值加1，即i+1i;S5：如果i0a0输出a0成立不成立输出a

5、=0循环结构pAab成立不成立当型(while)结构pab成立不成立直到型(until)结构A当型(while)结构直到型(until)结构例：求1+2+3+4+5=?i50 x1ix+ixi+1i3.3 N-S流程图:1973 1973 年由美国学者年由美国学者 I.I.N Nassiassi,B.B.S Shneidermanhneiderman A A B B A AB B 条件条件？Y YN N 条件条件？A A 条件？条件？A A顺序结构选择结构当型(while)结构直到型(until)结构例：求a+b=？输入a输入b输出a+b输入a输入b输出a+b例：判断a0输出a0输出a0a0？

6、Y YN N A AB B 条件条件？Y YN N选择结构a0输出a0成立不成立输出a=0 条件条件？A A当型(while)结构直到型(until)结构例：求1+2+3+4+5=?i=5x+ix成立不成立0 x1ii+1i 当当i50 x1ix+ixi+1i直到直到i5 i+1i x+ix 条件？条件？A A例1：请用N-S 图描述解决下列问题的算法 若输入若输入 a a b b两个整数两个整数然后将它们然后将它们 的值互换。的值互换。输入输入输入输入 a,b a,b t=at=aa=ba=bb=tb=t输出输出输出输出 a,ba,ba a100100b b200 200 t t100 10

7、0 200 200 100 100 例2：请用N-S 图描述解决下列问题的算法 m=cm=cm=bm=b输入输入输入输入 a,b,ca,b,cm=am=a a ba bY YN N m cm cY YN N输出输出输出输出 m m 若输入若输入 a a b,cb,c 三个整三个整数，请输出数，请输出 它们当中最它们当中最 大的一个大的一个 。例3：请用N-S 图描述解决下列问题的算法现有一函数如下现有一函数如下:+1 (x0)y=0 (x=0)-1 (x 0 x 0Y YN N输出输出输出输出 y y x=0 x=0Y YN Ny=-1y=-1y=0y=0例4：请用N-S 图描述解决下列问题的

8、算法输输输输出出出出y y为为为为非非非非闰闰闰闰年年年年20002000yyY Y y/400y/400的余数的余数的余数的余数=0=0Y YN Ny+1yy+1y判断判断2000-25002000-2500年中每一年是否年中每一年是否是闰年，将结果是闰年，将结果输出。输出。y/4y/4的余数的余数的余数的余数=0=0N Ny/100y/100的余数的余数的余数的余数!=0!=0Y YN N输出输出输出输出y y为为为为闰年闰年闰年闰年输出输出输出输出y y为闰年为闰年为闰年为闰年输出输出输出输出y y为为为为非闰年非闰年非闰年非闰年直到直到直到直到y2500y2500输输输输出出出出y y

9、为为为为非非非非闰闰闰闰年年年年20002000yyY Y y/400y/400的余数的余数的余数的余数=0=0Y YN Ny+1yy+1y y/4y/4的余数的余数的余数的余数=0=0N Ny/100y/100的余数的余数的余数的余数!=0!=0Y YN N输出输出输出输出y y为为为为闰年闰年闰年闰年输出输出输出输出y y为闰为闰为闰为闰年年年年输出输出输出输出y y为非闰为非闰为非闰为非闰年年年年 当当当当y=2500y2500y2500例4：当循环结构3.4 伪代码表示例：求5!BEGIN1t2iwhile i=5t*iti+1iprint tEND3.5 计算机语言表示程序例：求5！(C语言)main()int i,t;t=1;i=2;while(i=5)t=t*i;i=i+1;printf(“%d”,t);4.如何编写程序(结构化程序设计)自顶向下，逐步细化模块化设计，结构化编码输入n求n!输出结果例：求n!1i 当当i=n1tt*iti+1i1i 当当i=n1tt*iti+1i 输入输入n 输出输出t