信息技术基础模块（下册）任务1 认识算法精品ppt课件

这是一份信息技术基础模块（下册）任务1 认识算法精品ppt课件，文件包含11高教版信息技术《51初始程序设计任务1认识算法》PPT课件pptx、11高教版信息技术《51初始程序设计任务1认识算法》教案docx等2份课件配套教学资源，其中PPT共19页， 欢迎下载使用。

理解算法的概念。掌握算法的描述方法。理解算法的策略和解决问题的基本思想。
在计算机程序设计中，著名的科学家沃斯(Nikiklaus Wirth)曾提出一个公式：算法（algrithm）+数据结构=程序在早期构造程序时，程序设计者一般都会认真考虑和设计数据结构和算法。事实上，算法和数据结构是一个过程化的程序的两个主要要素。算法、数据结构、程序设计方法和语言工具4个方面是一个程序设计的必备内容。其中，算法是灵魂，解决做什么和怎么做的问题；数据结构是用于加工对象的；语言是工具；编程需要采用合适的方法。数据结构和算法存在着本质的联系，这里我们先介绍算法的相关内容。
算法是指对解决某一特定问题的操作步骤的具体描述。简单地说，算法就是解决一个问题而采取的方法和步骤。
如何把大象装进冰箱。算法描述：
（2） 把大象装进去。
以上过程就是解决“如何把大象装进冰箱”这一问题的算法。对于计算机科学来说，算法是由若干条指令组成的有限序列，并满足以下几点性质：
自然语言法利用日常生活中常用的语言、数字和符号来描述算法。
判断所输入的三角形三边长度A、B、C是否能构成三角形，若能构成三角形则输出其周长，若不能则输出“无法构成三角形”。算法描述：（1） 输入三边A、B、C的长度。（2） 根据三角形的性质判断，如果A、B、C能够构成三角形，则输出A+B+C，否则输出“无法构成三角形”。
由上述例子可以看出，用自然语言描述算法通俗易懂，但同时由于自然语言的冗长、多义等特性，其缺点也是显而易见的：
由于自然语言容易产生歧义，从而导致该算法无法正常执行下去。
自然语言语句较长导致算法的描述过于复杂、冗长。
难以清晰简便地描述分支和循环结构。
不便于翻译成计算机可运行的程序设计语言。
程序流程图也称流程图，是一种用图形化的符号框来代表不同性质的操作，并用流程线来连接这些操作的算法描述方法。表6-1列出了流程图中可以使用的各种符号框和流程线。流程图可以清晰地表示一个程序的运行过程和结构，较自然语言，流程图更加简洁明了，且很容易表示出算法中的分支和循环结构。
表6-1 流程图符号表
设计算法，输入一个数N，求其绝对值。
对于任意输入的数N来说，如果N>=0，其绝对值是N，如果N<0，则绝对值是-N。算法：(1) 输入数N(2) 判断数N是否小于0(3) 小于0输出-N(4) 否则输出N(5) 结束算法流程图如图6-1所示。显然，与自然语言相比，用流程图来描述算法更加直观、形象，便于理解。
伪代码是一种非正式的，用于描述模块结构图的语言。它由自然语言和类编程语言混合而成，采用了编程语言的结构和字符，介于自然语言和编程语言之间。用伪代码来描述算法更为简洁、精确，最重要的是能够很方便地转换成正规的编程语言，成为计算机可以识别运行的程序。
【例6-4】设计算法，判断某一年份是否为闰年，并用伪代码描述。问题分析：判断某一年是否是闰年的方法是：如果该年份能够被4整除，但不能被100整除，或者能被400整除，那么该年份为闰年。
迭代是程序中对一组指令（或一定步骤）的重复，其目的通常是为了逼近所需的目标或结果。每一次对过程的重复被称为一次迭代，而每一次迭代得到的结果会被用来作为下一次迭代的初始值。
【例6-5】一个饲养场引进一只刚出生的新品种兔子，这种兔子从出生的下一个月开始，每月新生一只兔子，新生的兔子也如此繁殖。如果所有的兔子都不死去，问到第12个月时，该饲养场共有兔子多少只？
分析：假设第i个月时兔子的只数为ri，则有：r1= 1, r2 = r1×2 = 2 , r3= r2×2 = 4，…… 根据这个规律，可以归纳出下面的迭代规则：rn = rn-1×2 （n≥2）对应rn和rn-1，定义两个迭代变量r1和r2，可将上面的公式转换成如下迭代关系：r2=r1*2 r1=r2让计算机对这个迭代关系重复执行11次，就可以算出第12个月时的兔子数。
穷举法又称列举法、枚举法，是蛮力策略的具体体现，是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解的方法。
【例6-6】百钱买百鸡问题。公鸡5文钱一只，母鸡3文钱一只，小鸡3只一文钱，用100文钱买一百只鸡，其中公鸡，母鸡，小鸡都必须要有，问公鸡，母鸡，小鸡要买多少只刚好凑足100文钱。
分析：设公鸡为x，母鸡为y，小鸡为z，那么可以得出如下的不定方程：x+y+z=1005x+3y+z/3=100根据题目，因为只有100文钱，容易确定x，y，z的取值范围：x的范围：0分治法求解问题的过程是将整个问题分解成若干个子问题后分而治之。如果分解得到的子问题相对来说还是太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。分治法的基本步骤如下：
（1） 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题。
（2） 解决：若子问题规模较小而容易被解决则直接解，否则再继续分解为更小的子问题，直到容易解决。
（3） 合并：将已求解的各个子问题的解，逐步合并为原问题的解。
【例6-7】找假币问题。有一个装了16枚硬币的袋子，已知16枚硬币中有一枚是假币，并且假的硬币比真的硬币要轻一些。你的任务是找出这枚伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。
算法一：采用穷举法。比较硬币1与硬币2的重量。假如硬币1比硬币2轻，则硬币1是伪造的；假如硬币2比硬币1轻，则硬币2是伪造的。这样就完成了任务。假如两硬币重量相等，则比较硬币3和硬币4。同样，假如有一个硬币轻一些，则寻找伪币的任务完成。假如两硬币重量相等，则继续比较硬币5和硬币6。按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币。
算法二：采用分治法。把从16枚硬币中找假币问题看成一个大的问题。第一步，把这一问题分成两个小问题，每个小问题中包含随机分配的8枚硬币，将每个小问题中的硬币分别分组，第一组称为A组，第二组称为B组。这样，就把16枚硬币的问题分成两个8枚硬币的问题来解决。第二步，判断A和B组中是否有假币。第三步，将较轻的一组中硬币等分为两份，重复上述做法。直到剩下两枚硬币，便可用天平直接找出假硬币。在硬币较多的情况下，显然算法二在大多数情况下具有更好的性能。