当前位置: 首页 > >

7、算法与程序设计_图文

算法与程序设计
浙江理工大学 计算机技术教研部 2009年9月

算法的概念
? 算法的概念:算法是为解 决一个问题而采取的方法 和步骤。 ? 算法的分类: 1. 数值运算算法 2. 非数值运算算法 Nikiklaus Wirth 程序=数据结构+算法

算法设计

? 关于算法有两个阶段 – 第一个是设计算法 – 第二是这个算法的实现

算法设计
? ? ? ? ? 国际奥委会是如何通过投票决定主办权归属的问题 如何证明哥德巴赫猜想 一道智力题 如何判断一个正整数是否是素数? 若干趣味题

从一个实际的问题开始
? 北京获得了2008年第29届奥运会主办权,你知道在申 办奥运会的最后阶段,国际奥委会是如何通过投票决定 主办权归属的吗? ? 先确定基本的申办城市 ? 对选出的5个申办城市进行表决
– 操作程序是:首先进行第一轮投票,如果有一个城市得票超过 总票数的一半,那么该城市就获得主办权 。否则将得票最少的 城市淘汰(若票数最少的城市有若干,则继续针对这些城市投 票,决定哪个被淘汰)。重复上述过程,直至选出一个申办城 市为止。

关于一个数学的猜想
? 哥德巴赫猜想
– 1742年6月7日哥德巴赫写信给当时的大数学家欧拉,提出了 以下的猜想:
(a)任何一个>=6之偶数,都可以表示成两个奇质数之和。 – 质数:大于1的自然数,除了1与它自身外,再没有其它的正 约数了,这样的自然数叫做质数。 – 例如6=3+3 ,8=3+5,10=3+7,12=5+7 (b)任何一个>=9之奇数,都可以表示成三个奇质数之和。 这就是著名的哥德巴赫猜想。

– 欧拉在6月30日给他的回信中说,他相信这个猜想是正确的, 但他不能证明。 – 计算机可以帮助我们轻松验证它

歌德巴赫猜想的证明
? 下面的一个程序可以验证2000以内的大于6的正偶数都 能分解成二个素数之和,即验证歌德巴赫猜想在2000 范围内的正确性。 ? 方法:
– 先将整数分解成二部份,然后判断二个素数是否均为素数,若 是则满足题意,否则需要重新分解和判断。 – 判断一个数是否为素数有很多方法,从定义上说,判断一个整 数n是否为素数就是要判断其是否能被1和n之外任意整数整除; 若不能被所有满足条件数整除,则n为素数。 – 在程序里不必从1到n-1的数一个个去试,只用从2开始到该整 数的一半去试即可,这样可以大缩短判断的时间。

判断一个整数是否为素数的问题
思路:素数只能被1和它本身整除

判断方法:将m(设m是要被判断的整数) 作为被除数,用 2 到( m-1)的各个整数轮 流去除,如果都不能整除,则m是素数。

算法的表示方法
? ? ? ? ? 用自然语言表示算法 用流程图表示算法 用N-S流程图表示算法 用伪代码表示算法 用计算机语言表示算法

用自然语言表示算法
? ? ? 用人们日常使用的语言,如汉语、英语等描述算法。 问题:在两个数中找出较大的那个数。 描述:
1. 2. 输入任意两个数a和b 如果a大于b,那么输出大数是a,否则输出大数是b。

用自然语言表示算法
? 关于奥运会主办权的决策算法(自然语言描述)
1. 投票计票; 2. 若有某城市得票大于半数,则该城市取得主办权; 3. 若没有超过半数的城市,则淘汰一个城市;
– 得票最少者被淘汰 – 得票最少者有若干城市则在这些城市中再投票直到选出一个被 淘汰者

4. 若没有选出则重复上述步骤直到选出为止

用自然语言表示算法
求素数的算法(自然语言表示) 给出大于2的正整数m,求它是否是素数
1. 输入m的值 2. i=2(用i去除m) 3. m被i除(m除以i),得到余数a 4. 如a=0,表示m能被i整除,显示信息“m不是素 数”,算法结束;否则进入下一步。 5. 将i加1送回给i。 6. 如果i<m,则跳到3执行,否则显示“m是素数”的 信息,算法结束

用流程图表示算法——基本结构图
? 顺序结构 ? 选择结构 ? 循环结构

流程图符号说明

用流程图表示算法
? 关于奥运会主办权的决策算法(流程图表示)
开始 投票 淘汰一个城市
有票数过半城市? 否


输出该城市 结束

? 循环结构

用流程图表示算法
在两个数中找出较大的那个数

用N-S图表示算法—— N-S图符号
? 顺序结构 ? 选择结构 ? 循环结构

用N-S图表示算法
在两个数中找出较大的那个数

用N-S图表示算法
? 判断整数m是否是素数
输入m 初始化计数器:i=2 素数标记:flag=true i≦m-1
且 flag=true

yes flag=false

i整除m?

no

i=i+1 yes flag=true? no

M是素数

M不是素数

用伪代码表示算法

Pseudo Code

begin input a,b;

书写方便,格式紧凑, 无语法限制,便于向 计算机语言算法(程 序)过渡。

if a>b then max=z else max=b;
output max; end

用计算机语言表示算法
# include <stdio.h> void main() { int a,b,max; scanf("%d,%d",&a,&b); 必须严格遵循 所用语言的语 法规则。

if(a>b) max=a;
else max=b; printf("max is %d\n",max); }

程序设计语言

面向过程的高级语言
? 高级语言是一种与机器指令系统无关,表达形式更接近于 被描述问题的语言

? 高级语言可分为两种类型 :
– 面向过程 – 面向对象

面向过程的高级语言
? Basic(Beginner ALL-Purpose Symbolic Instruction Code)
– 在计算机技术发展史上应用得最广泛的语言一 – 适于编程初学者编程,简单易学 – 非计算机专业出身的编程者广泛使用

? C语言

– C是一种高级语言,被广泛用于专业程序设计 – 既有高级语言的优点,又有汇编语言的效率,因此也有人把它 定位为“中级语言” – 它的命令可直接对计算机内存单元中的数据进行位操作,适合 编写较接近硬件操作又要求处理速度的程序

面向过程的高级语言
? Pascal语言
– Pascal——为纪念计算机先驱Pascal命名的 – 作为一种教学和应用开发语言被普遍接受

?

Fortran语言
– 第一个高级语言:IBM公司在1957年开发的 – 更适合于科学、数学和应用工程方面的应用,编程人员可用它方便地描 述数学问题,解决数学计算

?

Cobol语言
– COBOL是一种专门的商用的高级程序设计语言,于1960年问世 – 大部分命令都与英语类似 – 比较适用于存储、检索公司的财务信息,实现票据管理和工资报表等功 能

面向对象的程序设计语言(Cont)
? Visual Basic
– 简称VB,BASIC引入了面向对象的设计方法 – 为开发图形界面的应用程序而设计的 – 它比较简单易学,功能强大,得到广泛应用 – Sun Microsystem公司开发 – 具有纯面向对象、平台无关性、多线程、高安全性等特点 – 解决了困扰软件界多年的软件移植问题 – 传统的C语言进行面向对象的扩展而成的语言 – 它在C语言的基础上增加了面向对象程序设计的支持

? JAVA

? C++

其他语言
? 函数型语言——主要有LISP和Scheme ? 说明型语言——也叫逻辑语言,它被用于根据逻辑推理的 原则回答问题 ? 超文本链接标记语言(HTML)——由一种格式标记何超 链接组成的“伪语言”,主要用于网络上的信息服务

怎样编写程序
? ? ? 一个好的程序员网站http://www.csdn.net 程序设计不是简单的编写程序代码,它是一个系统过程 一般可以把这个系统过程分为六个步骤
1. 2. 3. 4. 5. 6. 问题的定义或叫做程序说明 设计解决问题的方案 编写程序代码 进行程序测试 程序的文档 程序应用

理解问题:程序说明
? 程序设计中最重要的部分 ? 设计一个程序是为了解决某个特定的问题,那么应该 做什么,如何做——系统分析员 ? 主要是要弄清以下几个问题
– – – – 程序目标是什么?即程序需要解决什么样的问题 可能需要输入哪些数据? 数据具体的处理过程和要求是什么? 程序可能产生的数据输出以及输出形式是什么?

一个程序代码的例子 C语言
#include <stdio.h> /* C 语言编译系统的库函数 */ main() /* 程序开始 */ { int i,fac; /* 定义变量 */ fac=1; /* 变量 fac 被赋值 1 */ for( i =2;i<=5;i++) /* 从2到5,循环执行乘法得到5的阶乘*/ fac=fac*i; printf( “the 5! = %d ” ,fac ); /* 输出结果 */ }

一个程序代码的例子 VB语言
‘ 定义 i 、fac为整型数变量

? Private Sub Form_Click()
Dim i As Integer, fac as integer

fac=1
for i=2 to 5 step 1

‘ 变量fac赋值1
‘ 循环,从2到5,每次步长为1

fac=fac*i next i
print “fac=”;fac End Sub

‘ 计算5的阶乘

‘ next和for构成循环体
‘ 输出阶乘结果

编写程序文档
? 程序文档 – 对前面所做的各种设计形成完整的手册 – 设计程序阶段中形成的流程图、变量列表、代码、运 行结果等编写文档,供日后的程序维护、升级使用 – 程序的功能、操作说明编写成册——程序使用手册

结束!




友情链接: year2525网 工作范文网 QS-ISP 138资料网 528200 工作范文网 baothai 表格模版