高中信息技术算法与程序设计第一课.ppt

算法与程序设计 个人计算机的另一个称呼是什么 电脑 为什么称计算机是电脑 计算机能模拟人的大脑的活动 算法初步 算法与程序框图基本算法算法案例 揭开计算机解决问题的神秘面纱程序设计基础可视化编程算法与程序实现面向对象程序设计程序设计实践 算法与程序设计 如何用计算机解决问题 当我们用计算机解决问题时 首先要分析问题 然后根据问题的要求选择合适的软件 如果现有的软件能满足我们的要求 我们会直接用这些软件来完成任务 例如 学校财务处要制作一份工资表 工资表中许多数据 我们可以用Excel解决 学生要设计一个报刊设计 可以使用word 网络上的网页是使用网页制作工具完成的 记事本要输入代码 Frontpage和Dreamweaver可以直接使用可视化工具 除此之外 现实生活中还有许多工作往往比较特殊 现有的软件不能很好地完成 或者由于其他方面的原因无法使用 这就需要我们编写程序来解决问题 计算机解决问题的步骤 分析问题 可采用建立数学模型的方式使问题变得更明确 易理解 设计算法 数学模型确定了应该 做什么 接下来就要为它寻找一个 如何做 的算法 编写程序 用一种计算机能接受的程序设计语言来描述问题求解的算法 调试程序 查找和改正程序中存在的错误 使程序能顺利地执行 得出正确结果 算法的概念 加法口诀表 农夫过河问题 一个农夫带着一只狼 一只羊和一棵白菜过河 河边只有一条船 由于船小 农夫一次只能带其中的一样过河 如无人看管 狼要吃羊 羊要吃菜 问农夫如何安排过河 才能使狼 羊 菜都安然无恙 渡河的方法与步骤 第一步 农夫带着羊渡过河去 第二步 农夫划船回来 第三步 农夫带着菜渡过河去 第四步 农夫带着羊划船回来 第五步 农夫带着狼渡过河去 第六步 农夫划船回来 第七步 农夫带着羊渡过河 一个笼子里有鸡和兔 现在只知道里面一共有35个头 94只脚 问鸡和兔各有多少只 X Y a2X 4Y b解方程组得 X 2a b 2 Y b 2 a 鸡兔同笼问题 设计算法 输入a和b的值求X 2a b 2求Y b 2 a输出X Y的值结束 a1X b1Y c1a2X b2Y c2输入a1 b1 c1 a2 b2 c2的值求X b2 c1 b1 c2 a1 b2 a2 b1 求Y a1 c2 a2 c1 a1 b2 a2 b1 输出X Y的值结束 算法 算法是在有限步骤内求解某一问题所使用的一组定义明确的规则 算法是解决问题的方法和步骤 算法的特征 输入确定有穷性输出能行性 判断整数n n 2 是否为质数 第一步 给定大于2的整数第二步 令i 第三步 用i除n 得到余数r 判断余数r是否为 若是 则n不是质数 结束算法 否则 将i的值增加1 仍用i表示第四步 判断i是否大于 n 1 若是 则n是质数 返回第三步 著名数学家华罗庚 烧水泡茶 算法一第一步 烧水 第二步 水烧开后 洗刷茶具 第三步 沏茶 算法二第一步 烧水 第二步 烧水过程中 洗刷茶具 第三步 水烧开后沏茶 求最大公约数辗转相除法穷举法 算法在解决问题中的地位和作用 见书 13表1 6 两个程序的效率比较 计算机只懂得根据人的命令来执行相关的程序 而我们要编写程序 首先要分析问题 对问题进行详细地分析 通过分析 弄清楚已知条件下的初始状态及要达到的目标 找出求解问题的方法和过程 并抽取出一个数学模型 形成算法 然后要设计算法 将这个数学模型连同它要处理的数据用计算机能识别的方式描述出来 使之成为计算机能处理的对象 最后 编写程序 用程序设计语言设计出具体的问题求解过程 形成计算机程序 这样 计算机就会按照我们给定的指令一条一条地进行处理了 设计一个软件的步骤是 开始 分析问题 设计算法 编写程序 运行程序验证结果 问题解决 无论使用现成的软件解决问题 还是自己动手编程解决问题 其实质都是一样的 现有的计算机软件同样也经历了这些过程 其差别在于 用程序设计解决问题需要我们亲自动手设计软件 而使用现成的软件 是别人已经给我们设计好了的 算法的描述 自然语言流程图伪代码 1 用自然语言来描述 什么是自然语言 人们日常生活中使用的语言 算法描述 以 韩信点兵问题 为例 今有物 不知其数 三三数之 剩二 五五数之 剩三 七七数之 剩二 问物几何 答曰 二十三 算法分析 以 韩信点兵问题 为例 自然语言的优点 通俗易懂 缺点 容易产生歧义 例如 这个人连老张也不认识 意思之一 这个人不认识老张 意思之二 老张不认识这个人 2 用流程图来描述 流程图也称程序框图 算法的一种图形化表示方法 流程图 流程图的优缺点 与自然语言相比 用流程图描述算法形象 直观 更容易理解 3 用伪代码描述算法 例如 给定一个四位数的年份 判断它是否为闰年 如果用伪代码来描述算法 可以表示如下 算法分析 我们知道 如果2月是28天 则这一年是平年 如果是29天 则这一年是闰年 判断闰年的条件是 如果该年份能被4整除但不能被100整除 或者能被400整除 则该年为闰年 算法描述 输入年份 yIFy能被4整除THENIFy不能被100整除THEN输出 是闰年 ELSEIFy能被400整除THEN输出 是闰年 ELSE输出 不是闰年 ENDIFENDIFELSE输出 不是闰年 ENDIF 使用伪代码描述算法没有严格的语法限制 书写格式也比较自由 只要把意思表达清楚就可以了 它更侧重于对算法本身的描述 在伪代码描述中 表示关键词的语句一般用英文单词 其他语句可以用英文语句 也可以用汉语语句 伪代码的优缺点 用伪代码描述的算法简洁 易懂 修改起来也比较容易 并且很容易转化为程序语言代码 缺点是不是很直观 INPUTm nr mmodnDOWHILEr 0m nn rr mmodnLoopPRINTn 程序的基本结构 顺序结构选择结构循环结构 分析问题 建立模型 设计算法 编写程序 具体问题 程序设