1、第二章算法与问题 解决 1、算法的概念 2、算法的描述 3、算法的结构 本章重点：本章重点： 1.算法的特征 2.学会用自然语言和流程图描述算法 3.了解算法的三种基本结构及用算法解决问题的过程 简单地说，就是。 我们人找到算法之后，不能只是自己心知肚明，计算机 是不清楚的。我们必须明确的告诉它要处理的具体对象 和每一步的准确处理过程，否则计算机就无法工作，即 算法的描述要求尽可能。 什么是算法？什么是算法？ 算法的特征算法的特征 执行有限步之后结束，且每一步都执行时间都是有限的。 算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的。 有零个或多个输入。 至少产生一个输出。 原则上
2、能精确运行，用纸和笔做有限运算后可以完成。 算法的描述方法算法的描述方法 人们日常生活中使用的语言，汉语，英语，日语 等都是自然语言，这些自然语言描述算法符合我们的表达习惯， 且容易理解。 也叫程序框图，是算法的一种图形化表示方法，与 自然语言描述算法相比，用流程图描述算法形象、直观、更容易 理解。 简洁、易懂，容易修改，很容易转化为计算机程序 设计语言，缺点是不够直观。 计算机是人脑的延伸，要研究计算机解决问题的 过程，首先要从人解决问题的角度谈起。 自然语言描述自然语言描述： 如果某年份x能被4整 除但不能被100整除，或者 该年份x能被400整除，则 该年为闰年。 流程图描述：流程图描述
3、： 举例 流程图符号流程图符号 图形符号名称功能 起止框 表示算法的开始和结束 输入/输出框 表示算法中数据的输入 或输出 处理框 表示操作的内容（赋值、 计算等） 判断框 表示判断的条件，成立 出口处标Y/“是”，不成 立出口处标N/“否” 流程线 连接程序框 连接符 表示流程图的待续 算法的三种基本结构算法的三种基本结构 算法基本是由顺序结构、分支结构、循环结构这三种 基本结构组合而成。 大程序采用“自上而下，逐步细化”的方法，把大任 务拆分成若干个小任务组成，每一个小任务再分解为若 干个子任务，逐级分解，直至三种基本结构。 算法要素 （变量）、 计算模型 算法特征、 结构化程序 设计思想
4、 自然语言、 流程图及 伪代码 实例1 输入两个数a,b. 计算两个数的和S；（用流程图描述算法） 开始 输入a,b s=a+b 输出S 结束 实例2 你能通过流程图用自然语言描述吗？ 实例3 任意输入三个数，按从小到大的顺序依次输出这三个数 （用流程图描述算法）。 自然语言描述 第一步；输入3个整数a，b，c 第二步：将a与b比较，并把大者赋给b，小者赋给a 第三步：将a与c比较，并把大者赋给c，小者赋给a，此时a已是三者中最小的 第四步：将b与c比较，并把大者赋给c，小者赋给b，此时a，b，c已按从小到 大的顺序排列好 第五步：按顺序输出a，b，c 1.数据的存储 计算机需要的原始数据，计
5、算产生的中间结果。 2.计算的过程 先确定解决的问题，再将解决问题的方法步骤 化，并用计算机能够执行的指令实现对应的步骤。 6. 设计一个算法，根据邮件的重量和用户是否选择加急计算邮费。计 算规则：重量在1000克以内(包括1000克), 基本费8元。超过1000克 的部分，每500克加收超重费4元，不足500克部分按500克计算；如 果用户选择加急，多收5元。 输入两行，第一行输入一个整数代表邮件的重量；第二行输入一个字符 表示是否加急，其中字符 y 表示加急；字符 n 表示不加急。 输出一行，包含一个整数，表示邮费。 实例实例 按照用算法解决问题的过程分析如下： 已知数据：邮件的重量w，加
6、急标记字符f，其中y表示加急；n表示不加急。 求解目标：邮费cost。 计算模型： 输人邮件的重量w和加急标记字符f。 初始化邮费cost为8。 若w=1000，则6，其中7表示向上取整。 若f= y，则cost = cost + 5。 输出变量cost的值。 算法的描述方法。 算法的基本特征。 流程图符号。 算法的三种基本结构。 用算法解决问题的过程。 本章小结本章小结 巩固练习 开始 结束 s=s+i N s=0，i=1 Y i=i+1 i=100 输出s A.算法的基本特征是：有穷性，确定性，可行性，有零个或多个输 入，至少产生一个输出 B.算法独立于具体的程序设计语言，一个算法可以用多
7、种程序设计 语言来实现 C.算法就是程序，设计算法的过程就是程序设计的过程 D.常见的四种算法描述方法是自然语言法、流程图法、伪代码法和 计算机程序设计语言 C A.抽象与建模 B.问题界定 C.设计算法 D.描述算法 B A. 自然语言、流程图 B.伪代码、流程图 C.自然语言、伪代码 D.流程图、自然语言 A A.ab C.a=b D.ab B 6.（开放题）为了鞭策自己能每天早起，小明参加了一个为期100天的“早起 打卡赚积分”活动。每天早上5:00-6:00参加活动打卡赚积分，100天后根据积 分领取奖金。具体的赚取积分规则如下： 每天打卡成功可以获得1积分； 连续3天打卡成功，从第4
8、天起打卡积分翻1倍（每天2积分）。翻倍期间若有 1天没有打卡（即连续每天打卡行为中断），则翻倍权益取消，重新连续3天打 卡成功才能继续翻倍。 连续10天打卡成功，可获得1次抽奖机会，有1/10的概率获得100积分；连续 20天打卡成功，可获得1次抽奖机会，有1/9的概率获得100积分；以此类推， 连续90天打卡成功，可获得1次抽奖机会，有1/2的概率获得100积分；连续100 天打卡成功，可获得1次抽奖机会，有1/1的概率获得100积分。 请你根据上述描述，为“早起打卡赚积分”活动设计一个算法，根据小明每天 的打卡情况，计算100天后他获得的积分情况。 解析 本题是对教材“动动有奖”APP项目的一个模仿，已知数据包含了每天是 否成功打卡的标记。因为这些数据在事先都是不确定的，所以需要通过输 人将数据传递给算法,我们用F表示每天是否成功打卡( 1表示成功打卡，0 表示没有打卡)。问题的解决目标比较直接，就是统计100天过去后，小明 共拥有的积分总和。 解决该问题的计算模型如下: 已知100组数据: Fi (1 i 100)，计算积分总和total。 Thanks
