资源简介

第二章算法与问题解决
1、算法的概念
2、算法的描述
3、算法的结构
4、计算机解决问题的过程
本章重点：
1.算法的特征
2.学会用自然语言和流程图描述算法
3.了解算法的三种基本结构及用算法解决问题的过程
简单地说，算法就是解决问题的方法和步骤。
我们人找到算法之后，不能只是自己心知肚明，计算机是不清楚的。我们必须明确的告诉它要处理的具体对象和每一步的准确处理过程，否则计算机就无法工作，即算法的描述要求尽可能精确、详尽。
什么是算法？
算法有哪些特征呢？
算法的特征
有穷性
执行有限步之后结束，且每一步都执行时间都是有限的。
确定性
算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的。
输入项
有零个或多个输入。
输出项
至少产生一个输出。
可行性
原则上能精确运行，用纸和笔做有限运算后可以完成。

算法的描述方法
自然语言：人们日常生活中使用的语言，汉语，英语，日语等都是自然语言，这些自然语言描述算法符合我们的表达习惯，且容易理解。
流程图：也叫程序框图，是算法的一种图形化表示方法，与自然语言描述算法相比，用流程图描述算法形象、直观、更容易理解。
伪代码：简洁、易懂，容易修改，很容易转化为计算机程序设计语言，缺点是不够直观。
计算机是人脑的延伸，要研究计算机解决问题的过程，首先要从人解决问题的角度谈起。
怎么判断某一年是不是闰年？
首先我们要知道如果某年2月是28天则这一年是平年，如果某年2月是29天，则这一年是闰年。
自然语言描述：
如果某年份x能被4整除但不能被100整除，或者该年份x能被400整除，则该年为闰年。
流程图描述：
举例
流程图符号
美国国家标准化协会
(American National Standard Institute,简称ANSI)
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}图形符号
名称
功能
起止框
表示算法的开始和结束
输入/输出框
表示算法中数据的输入或输出
处理框
表示操作的内容（赋值、计算等）
判断框
表示判断的条件，成立出口处标Y/“是”，不成立出口处标N/“否”
流程线
连接程序框
连接符
表示流程图的待续
算法的三种基本结构
算法基本是由顺序结构、分支结构、循环结构这三种基本结构组合而成。
大程序采用“自上而下，逐步细化”的方法，把大任务拆分成若干个小任务组成，每一个小任务再分解为若干个子任务，逐级分解，直至三种基本结构。
抽象与建模
设计算法
描述算法
用算法解决问题的过程
算法要素（变量）、计算模型
算法特征、结构化程序设计思想
自然语言、流程图及伪代码
实例1
输入两个数a,b.
计算两个数的和S；（用流程图描述算法）
开始
输入a,b
s=a+b
输出S
结束
实例2
任意输入三个数，输出其中最小数（用流程图描述算法）。
自然语言描述：
Step1：输入3个数a，b，c；Step2：比较a和b；Step3：若a>b，则执行Step4。否则转向Step5Step4：若b>c，则输出c；否则输出b。Step5：若a>c，则输出c；否则输出a。
你能通过流程图用自然语言描述吗？
实例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.数据的存储
计算机需要的原始数据，计算产生的中间结果。
2.计算的过程
先确定解决的问题，再将解决问题的方法步骤
化，并用计算机能够执行的指令实现对应的步骤。
6. 设计一个算法，根据邮件的重量和用户是否选择加急计算邮费。计算规则：重量在1000克以内(包括1000克), 基本费8元。超过1000克的部分，每500克加收超重费4元，不足500克部分按500克计算；如果用户选择加急，多收5元。
输入两行，第一行输入一个整数代表邮件的重量；第二行输入一个字符表示是否加急，其中字符 'y' 表示加急；字符 'n' 表示不加急。
输出一行，包含一个整数，表示邮费。
实例
按照用算法解决问题的过程分析如下：

（1）抽象与建模
已知数据：邮件的重量w，加急标记字符f，其中'y'表示加急；'n'表示不加急。
求解目标：邮费cost。
计算模型：
（2）设计算法
①输人邮件的重量w和加急标记字符f。
②初始化邮费cost为8。
③若w>=1000，则6，其中7表示向上取整。
④若f= 'y'，则cost = cost + 5。
⑤输出变量cost的值。
（3）描述算法
算法的描述方法。
算法的基本特征。
流程图符号。
算法的三种基本结构。
用算法解决问题的过程。
本章小结
巩固练习
1.下面流程图是什么功能？
开始
结束
s=s+i
N
s=0，i=1
Y
i=i+1
i<=100
输出s
2.下列关于算法错误的是：
A.算法的基本特征是：有穷性，确定性，可行性，有零个或多个输入，至少产生一个输出
B.算法独立于具体的程序设计语言，一个算法可以用多种程序设计语言来实现
C.算法就是程序，设计算法的过程就是程序设计的过程
D.常见的四种算法描述方法是自然语言法、流程图法、伪代码法和计算机程序设计语言
C
3. 以下哪个步骤不属于用算法解决问题的过程（ ）
A.抽象与建模
B.问题界定
C.设计算法
D.描述算法
B
4. 如图所示，是求绝对值的算法，其描述方式分别是（ ）
A. 自然语言、流程图
B.伪代码、流程图
C.自然语言、伪代码
D.流程图、自然语言
A
5．将两位同学的身高放入变量a和b中，比较这两个变量的大小，最后把其中较大的数放到变量c中并输出，流程图如图所示。①中应填（ ）
A.aB.a>b
C.a=b
D.a<>b
B
6.（开放题）为了鞭策自己能每天早起，小明参加了一个为期100天的“早起打卡赚积分”活动。每天早上5:00-6:00参加活动打卡赚积分，100天后根据积分领取奖金。具体的赚取积分规则如下：
①每天打卡成功可以获得1积分；
②连续3天打卡成功，从第4天起打卡积分翻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