算法与程序设计.

Presentation on theme: "算法与程序设计."— Presentation transcript:

1 算法与程序设计

2 微博的应用

3 二维码 定位服务

4 淘宝

5

6 第一章 如何用计算机解决问题 第一节 计算机解决问题的过程

7 什么是程序 计算机的任何动作都是在执行人给它的指令。人们针对某一需要而为计算机编制的指令序列称为程序

8 什么是程序设计语言 用于书写计算机程序的语言称为程序设计语言。 如vb、c、c++、pascal、java等

9 程序设计语言产生与发展过程 书P11 程序设计语言发展经历了机器语言、汇编语言和高级语言的过程。 机器语言是用“0”和“1”二进制代码表示的计算机能直接识别和执行的一种机器指令的集合 汇编语言（符号语言）是用一些简洁的英文字母、符号串来替代一个特定的指令中的二进制串 高级语言：接近于数学语言或人的自然语言，同时又不依赖于计算机硬件，编出的程序能在所有机器上通用 。例如:vb、pascal 、c 、c++等

10 面向对象语言 面向对象语言是比面向过程语言更高级的一种高级语言。面向对象语言的出现改变了编程者的思维方式，使程序设计的出发点有着眼于问题的过程转向着眼于问题中的对象及其相互关系，这种转变更加符合人们对客观事物的认识，因此，面向对象语言更接近于自然语言，面向对象语言是人们对于客观事物更高层次的抽象。 例:VB6.0 、C++ 、dephi

11 什么是软件 程序、数据连同有关的资料文档称为软件。

12 系统软件 是在计算机应用中，为了实现系统功能、充分利用资源、提高使用效率、便于使用而设计的与计算机系统资源有关的软件。 操作系统是重要的系统软件。 应用软件 是为用户应用目的而开发的软件。

13 新课引入----韩信点兵 “韩信点兵”问题1：求整除3余1、整除5余2、整除7余4的最小自然数。
韩信是我国西汉初著名的军事家。韩信点兵，多多益善，不仅如此，还能经常以少胜多，以弱胜强。在与楚军决战时韩信指挥诸侯联军，在垓下十面埋伏，击败楚军，楚霸王项羽因此自杀。 韩信说：“如果每3个人编为一队，那最后剩下1个人；如果每5个人编为一队，那最后剩下2个人；如果每7个人编为一队，最后剩下4个人。请大家算一下，有多少士兵？”（假设士兵总数不超过100人）他的这种巧妙算法，人们称为“鬼谷算”、 “隔墙算”、“秦王暗点兵”等。 “韩信点兵”问题1：求整除3余1、整除5余2、整除7余4的最小自然数。

14 分析问题(找出已知和未知、列出已知和未知之间的关系)
分析问题和解题步骤 ——算法1：穷举法求解 穷举法就是通过把需要解决问题的所有可能情况逐一试验来找出符合条件的解的方法 ，是效率最低的一种算法，优点是思路简单，编程容易。 分析问题(找出已知和未知、列出已知和未知之间的关系) 写出解题步骤     设所求的数为X，则X应满足： X整除3余1 X整除5余2 X整除7余4 1、令X为1 2、如果X整除3余1，X整除5余2，X整除7余4，这就是题目要求的数，则记下这个X 3、令X为X+1（为算下一个作准备） 4、如果算出，则结束；否则跳转2 5、写出答案 穷举法 算法：解决问题的方法与步骤。每一步都必须是确定的、能行的、不能有二义性。

15 用计算机解决问题 上机调试：启动Visual Basic程序设计环境，输入程序代码，并调试运行。 士兵数：67

16 拓展 士兵数：18232 “韩信点兵”问题2：求整除3余1、整除5余2、整除7余4、整除13余6、整除17余8的最小自然数。
上机调试：分析上述问题并写出算法， 修改程序，调试运行，检测结果。 士兵数：18232

17 算法2—最小公倍数法求解 在《孙子算经》中也有记载：“今有物不知其数：三三数之余二，五五数之余三，七七数之余二，问物几何?”
在《孙子算经》中也有记载：“今有物不知其数：三三数之余二，五五数之余三，七七数之余二，问物几何?”　 明代，数学家程大伟把这个问题的算法编成了四句歌诀： 三人同行七十稀，五树梅花廿一枝；七子团圆正半月，除百零五便得知 用现在的话来说就是：一个数用3除，除得的余数乘70；用5除，除得的余数乘21；用7除，除得的余数乘15。最后把这些乘积加起来再减去105的倍数，就知道这个数是多少。

18 算法2的正确性分析 被5、7整除，而被3除余1的最小正整数是70； 被3、7整除，而被5除余1的最小正整数是21； 被3、5整除，而被7除余1的最小正整数是15。 所以，这三个数的和是70×2＋21×3＋15×2，必然具有被3除余2，被5除余3，被7除余2的性质。但所得结果233（30＋63＋140＝233）不一定是满足上述性质的最小正整数，故从它中减去3、5、7的最小公倍数105的若干倍，直至差小于105为止。

19 人工解题与计算机解题 人工解题过程： 理解和分析所面临的问题； 寻找解题的途径和方法； 用笔、纸、计数器等工具进行计算； 验证计算结果。
计算机解题过程： 理解和分析所要求的问题； 寻找解题的途径和方法； 生成解题算法； 选用一种算法语言根据算法编写程序； 通过编辑、编译、连接产生计算机能够识别的指令序列； 在计算机上执行该指令序列; 检测结果。

20 人工解题与计算机解题的异同点 求解问题的方式 相同点 不同点 人工求解问题 分析问题、设计算法、得出结果、验算结果等
对题目进行解答、运算速度慢、不需要计算机等 用计算机求解问题 编写程序、调试程序、运算速度快等

21 小结 这节课，我们主要想向同学们说明两个问题： 1.我们为什么要用计算机程序来解决问题； 2.我们如何利用计算机程序解决问题。
用计算机程序解决问题的基本过程书P3图1-1 分析问题 设计算法 编写程序 调试程序 检测结果 人工解题与计算机解题的异同点 这节课，我们主要想向同学们说明两个问题： 1.我们为什么要用计算机程序来解决问题； 2.我们如何利用计算机程序解决问题。 同学们是否已经有了答案了呢？

22 　　中国有一本数学古书「孙子算经」也有类似的问题：「今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？」 　　答曰：「二十三」 　　术曰：「三三数之剩二，置一百四十，五五数之剩三，置六十三，七七数之剩二，置三十，并之，得二百三十三，以二百一十减之，即得。凡三三数之剩一，则置七十，五五数之剩一，则置二十一，七七数之剩一，则置十五，即得。」 　　孙子算经的作者及确实着作年代均不可考，不过根据考证，着作年代不会在晋朝之後，以这个考证来说上面这种问题的解法，中国人发现得比西方早，所以这个问题的推广及其解法，被称为中国剩余定理。中国剩余定理（Chinese Remainder Theorem）在近代抽象代数学中占有一席非常重要的地位。 韩信点兵