算法与程序设计

《算法与程序设计》由会员分享，可在线阅读，更多相关《算法与程序设计（22页珍藏版）》请在金锄头文库上搜索。

1、算法与程序设计算法与程序设计微博的应用微博的应用l二维码二维码 定位服务定位服务l淘宝淘宝第一章 如何用计算机解决问题 第一节第一节 计算机解决问题的过程计算机解决问题的过程什么是程序什么是程序计算机的任何动作都是在执行人给它的指令指令。人们针对某一需要而为计算机编制的指令序列称为程序程序 用于书写计算机程序的语言称为程序设计语言。程序设计语言。如vb、c、c+、pascal、java等什么是程序设计语言什么是程序设计语言程序设计语言产生与发展过程程序设计语言产生与发展过程 书书P11 程序设计语言发展经历了机器语言、汇编语言和高级语言的过程。 机器语言机器语言是用“0”和“1”二进制代码表示

2、的计算机能直接识别和执行的一种机器指令的集合 汇编语言汇编语言（符号语言）是用一些简洁的英文字母、符号串来替代一个特定的指令中的二进制串 高级语言高级语言：接近于数学语言或人的自然语言，同时又不依赖于计算机硬件，编出的程序能在所有机器上通用 。例如:vb、pascal 、c 、c+等面向对象语言是比面向过程语言更高级的一种高级语言。面向对象语言的出现改变了编程者的思维方式，使程序设计的出发点有着眼于问题的过程转向着眼于问题中的对象及其相互关系，这种转变更加符合人们对客观事物的认识，因此，面向对象语言更接近于自然语言，面向对象语言是人们对于客观事物更高层次的抽象。例:VB6.0 、C+ 、dep

3、hi面向对象语言面向对象语言什么是软件什么是软件程序、数据连同有关的资料文档称为软件软件。系统软件系统软件是在计算机应用中，为了实现系统功能、充分利用资源、提高使用效率、便于使用而设计的与计算机系统资源有关的软件。 操作系统是重要的系统软件。应用软件应用软件是为用户应用目的而开发的软件。新课引入新课引入-韩信点兵韩信点兵 韩信是我国西汉初著名的军事家。韩信点兵，多多益善，不仅如此，还能经常以少胜多，以弱胜强。在与楚军决战时韩信指挥诸侯联军，在垓下十面埋伏，击败楚军，楚霸王项羽因此自杀。 韩信说：“如果每3个人编为一队，那最后剩下1个人；如果每5个人编为一队，那最后剩下2个人；如果每7个人编为一

4、队，最后剩下4个人。请大家算一下，有多少士兵？”（假设士兵总数不超过100人）他的这种巧妙算法，人们称为“鬼谷算”、 “隔墙算”、“秦王暗点兵”等。 “韩信点兵韩信点兵”问题问题1：求整除：求整除3余余1、整除、整除5余余2、整除整除7余余4的最小自然数。的最小自然数。 分析问题和解题步骤分析问题和解题步骤 算法算法1：穷举法求解：穷举法求解分析问题(找出已知和未知、列出已知和未知之间的关系)写出解题步骤 设所求的数为X，则X应满足：X整除3余1X整除5余2X整除7余41、令X为12、如果X整除3余1，X整除5余2，X整除7余4，这就是题目要求的数，则记下这个X3、令X为X+1X+1（为算下一

5、个作准备）4、如果算出，则结束；否则跳跳转转2 25、写出答案算法：解决问题的方法与步骤。算法：解决问题的方法与步骤。每一步都必须是确每一步都必须是确定的、能行的、不能有二义性。定的、能行的、不能有二义性。穷举法穷举法穷举法就穷举法就是通过把是通过把需要解决需要解决问题的所问题的所有可能情有可能情况逐一试况逐一试验来找出验来找出符合条件符合条件的解的方的解的方法法 ，是，是效率最低效率最低的一种算的一种算法，优点法，优点是思路简是思路简单，编程单，编程容易。容易。 用计算机解决问题用计算机解决问题 上机调试：上机调试：启动Visual Basic程序设计环境，输入程序代码，并调试运行。 士兵数

6、：士兵数：67拓展拓展“韩信点兵韩信点兵”问题问题2：求整除：求整除3余余1、整除、整除5余余2、整除整除7余余4、整除、整除13余余6、整除、整除17余余8的最小自的最小自然数。然数。 上机调试：上机调试：分析上述问题并写出算法， 修改程序，调试运行，检测结果。士兵数：士兵数：18232算法算法2最小公倍数法求解最小公倍数法求解l在孙子算经中也有记载：“今有物不知其数：三三数之余二，五五数之余三，七七数之余二，问物几何?”l明代，数学家程大伟把这个问题的算法编成了四句歌诀： 三人同行七十稀，五树梅花廿一枝；七子团圆正半月，除百零五便得知 l用现在的话来说就是：一个数用3除，除得的余数乘70；

7、用5除，除得的余数乘21；用7除，除得的余数乘15。最后把这些乘积加起来再减去105的倍数，就知道这个数是多少。 l被5、7整除，而被3除余1的最小正整数是70；被3、7整除，而被5除余1的最小正整数是21；被3、5整除，而被7除余1的最小正整数是15。 l所以，这三个数的和是702213152，必然具有被3除余2，被5除余3，被7除余2的性质。但所得结果233（3063140233）不一定是满足上述性质的最小正整数，故从它中减去3、5、7的最小公倍数105的若干倍，直至差小于105为止。算法算法2的正确性分析的正确性分析人工解题与计算机解题人工解题过程：人工解题过程：1.理解和分析所面临的问

8、题；2.寻找解题的途径和方法；3.用笔、纸、计数器等工具进行计算；4.验证计算结果。计算机解题过程：计算机解题过程：1.理解和分析所要求的问题；2.寻找解题的途径和方法；3.生成解题算法；4.选用一种算法语言根据算法编写程序；5.通过编辑、编译、连接产生计算机能够识别的指令序列；6.在计算机上执行该指令序列;7.检测结果。人工解题与计算机解题的异同点求解问题的方式相同点不同点人工求解问题 分析问题、设计算法、得出结果、验算结果等 对题目进行解答、运算速度慢、不需要计算机等用计算机求解问题 编写程序、调试程序、运算速度快等小结小结l用计算机程序解决问题的基本过程书用计算机程序解决问题的基本过程书

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

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