资源简介

(共25张PPT)
01 初识编程
程序设计基础
学习目标
Scratch 编程绘制正方形
0 1
什么是程序和编程
0 2
什么是编程语言
0 3
编译执行和解释执行
0 4
编译器和解释器
0 5
Bug 和 Debug
0 6
第一个程序
题目：绘制一个边长为100的正方形
究竟什么是程序？什么是编程？
先看个故事
一个文化人，他有一个仆人是聋子… …
幸好他们都不是瞎子… …
仆人也认识几个有限的词汇… …
主人想让仆人做点事，他应该怎么做？
任务书
1、……2、……
程序就是计算机的任务书
现在你就是主人，计算机就是你忠实的仆人
你要是聪明，就将任务交给仆人去做
否则…，你就自己干活，让仆人歇着去吧…
程序
1、……2、……
编程就是用人和计算机都能够理解的语言为计算机编制完成任务所需的任务书
计算机只认识 0 和 1，所有任务书必须由0 和 1 组成，计算机才能看懂
有两个办法编写任务书
直接用 0 和 1组成的语言编写，这样的语言叫机器语言
用人熟悉的语言编写任务书，然后再找一个翻译
编程和语言
编程语言有很多种
可以用不同的语言编写程序，完成相同的任务，但是不同的语言需要不同的翻译。
C/C++语言
JAVA语言
其他语言
翻译1
翻译2
翻译n
机器语言
011001
01
一次将整个程序翻译成机器语言，然后计算机执行程序，完成任务
这时的翻译叫“编译器”
任务书哪怕有一丁点“翻译”看不懂，翻译工作也不能完成，程序当然也不能执行，这时叫发生了“编译错误”
编译执行
02
解释执行
将程序翻译一句，计算机马上执行一句
这时的翻译叫“解释器”
翻译看懂一句，翻译一句，执行一句。遇到不懂的语句，就会停止工作
解释执行通常会比编译执行慢一些
两种完成任务的方式
编程的一般流程
任务期望
结果
编写/修改
程序
编译/解释
执行
实际执行
结果
编程中有很多问题会导致程序结果与期望不一致，这些问题叫 bug（虫子），检查程序消除问题的过程叫 debug（除虫） 或调试。
语法决定指令可以通过什么方式和顺序组合在一起
指令告诉计算机要完成什么具体的操作（任务）
语言由一定数量的词汇（指令集）和语法组成
编程语言
将代表指令的图块组合在一起的方式
凡是允许的，就是正确的
因此， Scratch 编程语言中没有语法错误
但是在其它编程语言中，语法错误是初学者最常犯的错误
这也是我们为什么以Scratch 作为第一门编程语言的一个重要原因
语法
Scratch 编程语言 3-1
指令
Scratch 编程语言 3-2
分为动作、外观、声音、事件、控制、侦测、运算、变量、自制积木等九种类型
每类指令通过不同颜色的图块表示
Scratch 编程语言 3-3
有的指令很简单
有的需要选择（“面向”中可以选择不同的角色、颜色侦测中通过点击颜色选择）
有的指令还有参数，参数告诉指令任务的细节，比如10代表移动的距离；参数有的需要输入
让代码尽量简洁
同一任务，完成的方法有很多种，程序的写法也有很多种；
学会使用“重复执行”，当主人才会很轻松
“重复执行”和其内部指令构成“循环结构”
怎样画正三角形？ 2-1
从一个点，沿着某个方向出发，经过n次旋转又回到原来的方向，总共旋转了多少度？
怎样画正三角形？2-2
正方形旋转了4次，每次旋转角度相同，因此每次旋转90度
正三角形需要旋转几次？每次旋转多少度？
怎样画正多边形？
一个正多边形，假设有n个边，每次旋转的角度都是相同的，所以每次旋转的角度等于 360/n ，现在明白了吗？
你能画圆吗？
每次前进一小步，旋转一个小角度，走下来就是圆。
实际画的是边长为2的正180边形。直与曲是可以相互转换的。直线短了，就变为曲。曲线长了，就变为直。都知道地球是圆的，但我们的马路很直。
1
把任务分解为计算机可以理解的，能够按照一定顺序执行的步骤或操作的过程，叫算法设计
3
编程的核心是“算法设计”，你认为这种说法对吗？
2
算法：完成任务所需要的，由计算机可以理解的基本操作及规定的执行顺序所构成的完整的解题步骤
算法和算法设计
1、有穷性
2、确切性
算法的有穷性是指算法必须能在执行有限个步骤之后终止，能够结束，不能够无限执行下去
算法的每一步骤必须有确切的定义，必须是计算机可理解执行的操作
算法的 7 个特征 4-1
3、输入(Input)
一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件。
4、输出(Output)
一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。
算法的 7 个特征 4-2
算法的 7 个特征 4-3
前面的程序都没有输入，只有输出
这个程序根据输入的边数画正多边形，既有输入也有输出
对不同的输入数据都能够响应正确
健壮性（Robustness） 　　
7
执行速度快，占用资源少　　
高效性（High efficiency） 　　
6
算法中即每个步骤都可以在有限时间内完成；（也称之为有效性） 　　
可行性(Effectiveness)
5
算法的 7 个特征 4-4
但算法设计的思想和技巧是不变的
这也是编程学习最核心的内容
可以编程解决的问题有很多很多
编程语言有很多很多
进入编程的世界，你会发现：
总有些东西是不变的
总结
Scratch 编程绘制正方形
什么是程序和编程
什么是编程语言
编译执行和解释执行
编译器和解释器
Bug 和 Debug
Scratch 编程语言
算法和算法设计(共20张PPT)
02 舞台和角色
程序设计基础
学习目标
弹球游戏
0 1
舞台和角色
0 2
屏幕和坐标
0 3
绘制一排小松树
0 4
程序的初始化
0 5
弹球游戏 4-1
绘制背景中的红色底边
绘制挡板角色
导入小球角色，调整小球大小
为小球角色导入水滴声音 water_drop
弹球游戏 4-2
为挡板角色添加脚本
脚本实现了用鼠标控制挡板左右水平移动的功能
原理是不断地将挡板的x坐标设置为鼠标指针的x坐标
弹球游戏 4-3
为小球角色添加脚本
首先，程序将球移到(13,157)这个位置
然后不断地重复移动4步这一动作。在此过程中，如果碰到舞台边缘，球就会被反弹回来；如果碰到红色，游戏结束运行；
弹球游戏 4-4
小球如果碰到挡板，播放声音water_drop（水滴落），改变当前球的运动方向为 （180-方向），实现反弹效果。
如果原方向为150度，则新方向为30度，原运动方向和新运动方向以竖直方向0度为对称轴，就像光线反射一样，如下图所示
然后，移动5步，在随机旋转一个正负10度之间的一个角度
游戏要素
动画、音乐和人物控制
碰撞检测
挑战性和趣味性
随机性和运气
输赢机会的平衡… …
改进思路
增加爆炸物（碰到游戏结束）和礼品（碰到加分）
增加键盘控制，通过键盘控制实现双人对战（两人一左一右，球碰到自己这边的底线为输），得分显示及历史记录，时间限制，实现多关游戏、难度逐渐增加，等等
舞台和角色 7-1
编写 Scratch 程序，就像是设计一场演出。所有的演出活动都在舞台上进行
舞台的宽度为480，高度为360 单位，并以x-y 的网格线分割。舞台中央的x, y 坐标为0,0。
舞台和角色 7-2
通过移动鼠标 (光标)，并且查阅舞台下方所显示的鼠标x, y 坐标值，可得知舞台任何一点的坐标值
舞台有小、大、演示三种模式，通过以下三个按钮切换
舞台和角色 7-3
舞台有脚本、多个背景和声音
背景可通过绘制或导入图片生成
脚本可控制背景的切换，实现动画效果
声音可通过录制或导入声音文件生成
脚本可播放音乐文件，实现背景音乐
舞台和角色 7-4
在舞台上演出的各种演员，称为角色
角色可以在舞台上移动，以及跟其它的角色互动
角色可有多个造型，造型决定角色的外观
造型可绘制
造型也可通过导入图片来生成：譬如可以由硬盘导入图片、或是由某一网站下载图片
舞台和角色 7-5
脚本可控制角色移动、播放音乐、或是与其它的角色互动
角色可有自己的声音，可通过录制或导入声音文件生成
脚本可播放音乐文件，实现不同音效
舞台和角色 7-6
默认角色是小猫
角色有位置（x，y）坐标和方向两个属性
下图中按钮可控制角色允许的旋转方式
箭头代表角色当前方向，鼠标拖动箭头可改变角色方向
舞台和角色 7-7
编辑角色造型，会出现下图所示对话框
点击设定旋转范围，会出现十字线，角色位置实际是十字线交叉点的位置
角色旋转的中心也是十字线交叉点
绘制一排小松树
程序的初始化
程序在开始完成主要任务前，往往需要做一些准备工作
这些准备工作称为“程序的初始化”
任务分解
图中总共有 4 棵松树，所以可以通过重复 4 次完成，每次画一棵松树
每棵松树由一根线段和一个三角形组成
绘制线段
绘制松树
每棵松树绘制完成后，绘制起点右移，准备绘制下一棵树
绘制完松树，绘制代表大地的线段
任务分解
绘制松树代码
见右图
绘制“大地”代码
见下图
总结
弹球游戏
舞台和角色
屏幕和坐标
绘制一排小松树
程序的初始化(共17张PPT)
03 变量和计算
程序设计基础
学习目标
认识和使用变量
0 1
四则运算
0 2
简单累加计算
0 3
求阶乘
0 4
科学计数法
0 5
测试
0 6
怎样让小猫数数字，从1数到100呢？
小猫数数
在编程中，变量是用来存放某个值的占位符，很像数学里常见的变量如
x 和 y
在 Scratch 中，变量用拉长的圆形图块来表示，名称由你来指定
变量通常分为局部（local） 和 全局（global）变量。
在 Scratch中，局部变量只能被一个角色使用
全局变量在所有角色的代码中都可以使用
变量 5-1
变量可以暂时存放数据，如
输入、输出、临时（中间）结果等
变量可以作为参数传递数据
变量 5-2
变量有不同的类型，叫变量的数据类型
有的变量是数字类型，如1、2.5、-3.4，0等
如果一个变量的值只能是真（可用1表示）或假（可用0表示），这种变量就被称为逻辑变量（或布尔变量）
有的变量是字符或字符的集合（字符串），如 Hello
变量 5-3
数字变量可以进行加、减、乘、除四则运算
运算结果可以保存到相同或不同的变量中
如果现在n为10，执行右面指令后，n是多少？
复杂算式可以嵌套实现
a = (n + 1) x 5
变量 5-4
怎样让小猫数数字，从1数到100且仅数偶数呢？
怎样让小猫数数字，从1数到100且仅数奇数呢？
变量 5-5
谁知道1+2+…+100的结果？
谁能编程让小猫计算出结果？
高斯的难题
变量有三种显示方式，鼠标双击可切换
第三种，可通过拖动滚动条改变变量值
变量在舞台上可以显示或隐藏
方法一：勾选变量名前复选框
方法二：通过命令
变量的显示
小练习：编程计算20的阶乘，即20！或1×2×3×4×…×20？
答案是：2432902008176640000，你算对了吗？
50 的阶乘比较大，自动显示为科学计数法
代表3.041409320171337乘10的64次方
练习
实际问题的答案是不可能事先知道的，那怎样才能知道程序结果对不对呢？
检查程序正确性的方法是测试：
选取有限的，有代表性的输入，如果程序输出有错误，就代表程序有错误
例如，计算阶乘的程序可计算3的阶乘，测试一下结果是否正确，如果结果不等于6，说明程序计算有错误
测试 2-1
因为测试所有可能的输入是不可能或无意义的，所以测试一般只能证明程序有错，不能证明程序是正确的
程序必须进行测试
测试 2-2
计算1+2+…+100的结果，容易出错的地方：
加数和和的初始值设置为多少
重复的次数为多少？
所谓边界问题，就是怎样开始和怎样结束的问题
例如，在路边栽树，每隔3米载一棵，路长30米，共栽几棵树？如果是围绕湖边栽树呢？
测试中，边界值一般是必须要测试的
边界问题
编程计算1至100所有奇数的和
编程计算1至100所有偶数的和
作业
随机数
在一个范围内，以相同的机会、机率出现的数字
在动画和游戏编程中，随机数的应用非常广泛
作业
绘制随机位置出现的、随机改变颜色的、同等机率出现的正方形、圆和五角星
本作业中需要在三个地方使用随机数：位置、颜色、图形种类
随机数应用
认识和使用变量
四则运算
简单累加计算
求阶乘
科学计数法
测试
随机数应用
总结(共21张PPT)
04 比较和逻辑运算
程序设计基础
学习目标
比较运算符
0 1
逻辑运算符
0 2
程序的控制结构
0 3
用户输入两个数，
计算并输出两个数中的较大者。
比较两个数大小
只有两个截然相反取值的情况在数学及电子技术中称为布尔量或逻辑量，布尔量的取值称为布尔值。
布尔值只有两种可能的取值，常见表示方式
true/false，真/假，成立/不成立，0/1
布尔值之间的运算称为逻辑运算
日常生活中，存在很多使用布尔量的例子，如判断题，只有对或错
布尔量
比较运算符有三个，如右图
可比较两个数的大小，每个数可以是常量或变量
比较结果为布尔量：要么为真，要么为假
不仅数字可以比较，字符串也可以比较，按字典顺序，排在前面的小于排在后面的，如A小于B
比较运算符
逻辑运算符有三个
“与”运算
两个条件都为真，结果为真，否则结果为假
“或”运算
两个条件只要有一个为真，结果为真，否则结果为假
“非”运算，也叫“取反”
条件为真，取反后为假；条件为假，取反后为真；
逻辑运算符
比较运算和逻辑运算的结果都是布尔量(六边形）
布尔量可以作为判断的条件，用在控制结构中,改变程序的执行顺序
当条件满足时，执行这组操作，当条件不满足时，执行另外一组操作
条件
顺序结构
顺序结构的程序设计是最简单的，只要按照解决问题的顺序写出相应的语句就行，它的执行顺序是自上而下，依次执行。
程序的控制结构 5-1
循环结构
循环结构可以减少源程序重复书写的工作量，用来描述重复执行某段算法的问题，这是程序设计中最能发挥计算机特长的程序结构 。
程序的控制结构 5-2
分支结构
对于要先做判断再选择的问题就要使用分支结构。
分支结构的执行是依据一定的条件选择执行路径，而不是严格按照语句出现的先后顺序。
程序的控制结构 5-3
分支结构
程序设计方法的关键在于构造合适的分支条件和分析程序流程，根据不同的程序流程选择适当的分支语句。
分支结构适合于带有逻辑或关系比较等条件判断的计算，设计这类程序时往往都要先绘制其程序流程图，然后根据流程图写出源程序，这样做把程序设计分析与语言分开，使得问题简单化，易于理解。
介绍流程图画法和读法
程序的控制结构 5-4
顺序结构、分支结构和循环结构并不彼此孤立的，在循环中可以有分支、顺序结构，分支中也可以有循环、顺序结构
在实际编程中常将这三种结构相互结合以实现各种算法，设计出相应程序
程序的控制结构 5-5
年份如果不能够被4整除，肯定是平年。年份如果能够被4整除，通常就是闰年。但是有个例外，就是如果年份也能够被100整除，就不再是闰年。年份能够被100整除，通常是平年，但也有个例外，就是如果年份还可以被400整除，那么年份就又是闰年了。简单的说就是四年一闰，百年不闰，四百年再闰。
编一个程序，判断输入的年份是平年还是闰年。如果你的程序说：2000年是闰年、2004年是闰年，1900年是平年，你的程序才有可能是正确的。
平年闰年算法 4-1
平年闰年算法 4-2
平年闰年算法 4-3
平年闰年算法 4-4
考虑全面，不要遗漏任何分支
分类标准统一，严格，不要有重叠和交叉
分类判断时要有一个清晰的思路和方向，比如从4整除、100整除到400整除，或者从400整除、100整除到4整除
可用排除法，一类一类去排除。
注意事项
遗漏分支处理
常见问题 3-1
重复判断：一个数如果既被4整除又不能被100整除，程序先输出平年，再输出闰年
常见问题 3-2
类型不对，图块不能结合
条件需要布尔量，而余数是和数字，类型不对，应放入比较运算符中
整除判断方法不对
常见问题 3-3
比较运算符
逻辑运算符
程序的控制结构
顺序结构
循环结构
分支结构
程序注释
总结(共16张PPT)
05 循环分支运用
程序设计基础
学习目标
循环分支综合运用
0 1
穷举法应用
0 2
如果两个数都能够被一个数整除，则这个数就是两个数的公约数。
如，8 和 4 都可以被2整除，2就是 8 和 4的公约数。
公约数中最大的称为最大公约数。
如 8 和 4 都可以被2或4整除，2和4都是8 和 4的公约数。其中4最大，4就是8 和 4的最大公约数。
最大公约数 5-1
编程求204和85的最大公约数，有两种办法可以解决这个问题
应用穷举法。穷举法也叫枚举法或列举法。这种方法的主要思想是：在要解决的问题是由有限种情况组成时，把所有的情况一一列举出来，再对其一一进行判断和解决。
依次判断从1到85之间的数字，是否能够同时整除204和85
答案应该是17
最大公约数 5-2
最大公约数 5-3
应用辗转相减法。
辗转相减法的原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。
例如，252和105的最大公约数是21（252 = 21 × 12；105 = 21 × 5）；因为252 105 = 147，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。
最大公约数 5-4
你认为两种算法，哪一种比较好？为什么？
最大公约数 5-5
如果两个数都可以整除一个数，则这个数就是那两个数的公倍数。
如 6和8都可以整除48，48就是6和8的公倍数。公倍数中最小的称为最小公倍数。如 48、24都是6和8的公倍数，24是公倍数中最小的，是6和8的最小公倍数。
编程求204和85的最小公倍数。（答案应该是1020）
一种办法是穷举法，自己尝试编程序
最小公倍数 3-1
也可以借助最大公约数求最小公倍数，步骤： 　　
一、利用辗除法或其它方法求得最大公约数； 　　
二、 最小公倍数等于两数之积除以最大公约数。 　　
举例：12和8的最大公约数为4 　　
12×8/4=24 　　两数的最小公倍数是24
最小公倍数 3-2
你认为两种算法，哪一种比较好？为什么？
最小公倍数 3-3
素数，又叫质数，是除了1和它本身之外再不能被其他数整除的自然数。
由于找不到一个通项公式来表示所有的素数，所以对于数学家来说，素数一直是一个未解之谜。
求素数的方法有很多种，最简单的方法是根据素数的定义来求。对于一个自然数N，用大于1小于N的各个自然数都去除一下N，如果都除不尽，则N为素数，否则N为合数。但是，如果用素数定义的方法来编制计算机程序，它的效率一定是非常低的，其中有许多地方都值得改进。
求素数 5-1
利用素数定义，编程求50个素数
试着改进算法，提高效率
求素数 5-2
求素数 5-3
改进建议：
第一，对于一个自然数N，只要能被一个非1非自身的数整除，它就肯定不是素数，所以不必再用其他的数去除。
第二，对于N来说，只需用小于N的素数去除就可以了。例如，如果N能被15整除，实际上就能被3和5整除，如果N不能被3和5整除，那么N也决不会被15整除。
第三，对于N来说，不必用从2到N一1的所有素数去除，只需用小于等于√N(根号N)的所有素数去除就可以了。
求素数 4-3
求素数 4-4
循环分支综合运用
最大公约数
最小公倍数
求素数
穷举法应用
总结(共20张PPT)
06 循环分支运用
程序设计基础
学习目标
数字进制转换
0 1
回文数判别
0 2
十进制数(Decimal Number)
十进制数是生活中使用最广的计数制。组成十进制数的符号有0，1，2，3，4，5，6，7，8，9等共十个符号，我们称这些符号为数码。　　
在十进制中，每一位有0～9共十个数码，所以计数的基数为10。超过9就必须用多位数来表示。十进制数的运算遵循：“逢十进一”。
数字进制 10-1
二进制数(Binary Number)
二进制数仅有两个不同的数码，即0,1；规则为：逢二进一。
将8位(bit)二进制数称为一个字节,字节是计算机存储信息的基本数据单位。这就要说到存储器的容量单位：
1024B(byte)=1K 1024KB=1M 1024MB=1G
数字进制 10-2
十六进制
是计算机系统中除二进制数之外使用较多的进制
二进制数在计算机系统中处理很方便，但当位数较多时，比较难记忆及书写，为了减小位数，通常将二进制数用十六进制表示
十六进制有0,1,2,3,4,5,6,7,8,9,A,B,C,D,E，F等共十六个数码，分别对应于十进制数的0～15;　　
逢十六进一。　　
数字进制 10-3
进制表示
在数制使用时，常将各种数制用简码来表示：如十进制数用D表示或省略；二进制用B来表示；十六进制数用H来表示
如：十制数123表示为：123D或者123;二进制数1011表示为:1011B；十六进制数3A4表示为:3A4H。
数字进制 10-4
十进制 二进制 十六进制
0 0000 0
1 0001 1
2 0010 2
3 0011 3
4 0100 4
5 0101 5
6 0110 6
7 0111 7
数字进制 10-5
十进制 二进制 十六进制
8 1000 8
9 1001 9
10 1010 A
11 1011 B
12 1100 C
13 1101 D
14 1110 E
15 1111 F
16 10000 10
二进制与十进制的转换
二进制数1101等于1*2^0+0*2^1+1*2^2+1*2^3=1+0+4+8=13 。转化成十进制要从右到左用二进制的每个数去乘以2的相应次方，从2的0次方开始
这种做法称为“按权相加”法。
数字进制 10-6
数字进制 10-7
二进制与十六进制的转换
原则：每4位二进制对应1位16进制，高4位不足的前面补0
39H= 00111001B
4FH= 01001111B
11111B = 00011111B = 1FH
数字进制 10-8
十进制与十六进制的转换
先除2取余，将十进制转换成二进制，再按照4位二进制对应1位16进制，转换成十六进制数
十六进制转换成十进制：
226H = 2×162+2×161+6×160 = 550D
数字进制 10-9
1101 如果是二进制数字
表示 1*23 + 1*22 + 0*21 + 1*20
1101 如果是十进制数字
表示 1*103 + 1*102 + 0*101 + 1*100
1101 如果是十六进制数字
表示 1*163 + 1*162 + 0*161 + 1*160
1101 如果是W进制数字
表示 1*W3 + 1*W2 + 0*W1 + 1*W0
每个1代表的含义是不同的。十进制中十位的1代表10，百位的1代表100，每位数字中1代表的大小，叫该位的权重。
W进制数字中从右向左数第n位数字的权重是 Wn-1
数字进制 10-10
接受用户输入的二进制数据，转换为十进制数字输出
练习1: 二进制转十进制
练习1: 二进制转十进制
练习2：十进制转二进制
"回文数"是一种数字，其特点是正读倒读一样。如: 98789, 正读是98789,倒读也是98789
练习3：判断用户输入的数字是否为回文数
一种思路是将用户输入的数字当作字符串。然后将字符串的每个字符从头到尾依次取出来，然后从后到前再拼成一个新的字符串，如果两个字符串相同，则用户输入的数字为回文数。
另一种思路是把用户输入的数字当作数字，通过取余数得到各位数字，颠倒顺序后再重新组装为新的数字，如果两个数字相同，则用户输入的数字为回文数。
回文数判别
办法一
回文数判别
方法二
回文数判别
编程实现二进制和十六进制的互相转换
编程实现十进制和十六进制的互相转换
作业
数字进制转换
十进制
二进制
十六进制
回文数判别
非字符串分解方式
总结(共13张PPT)
07 多重循环运用
程序设计基础
学习目标
循环嵌套
0 1
多重循环运用
0 2
循环和算法效率
0 3
穷举法运用
0 4
下面两段代码都使用了循环结构
第一段代码说 i = 0 直到 i = 4
第二段代码说 j 等于 0 直到 j 等于 4
循环嵌套 5-1
将第二段代码拖入第一段代码中的循环结构
循环结构内又包含循环结构，这叫循环结构的嵌套
第二段代码作为一个子任务，加入第一段代码的循环，也要重复执行5次
循环嵌套 5-2
结果显示顺序如下
i = 0
j 等于 0
j 等于 1
j 等于 2
j 等于 3
j 等于 4
i = 1
j 等于 0
j 等于 1
j 等于 2
j 等于 3
j 等于 4
......
直到i = 4
j 等于 0
j 等于 1
j 等于 2
j 等于 3
j 等于 4
循环嵌套 5-3
代码执行顺序分析如下
将变量 i 设为 0
重复5 次[
任务1 [
说 i = 变量 i 的值
将变量 i 加 1
将变量 j 设为 0
]
任务2[
重复5 次[
说 j 等于变量 j 的值
将变量 j 加 1
]
]
]
循环嵌套 5-4
循环嵌套的一个例子：
本学期有16个星期（外层循环重复16次）
周六休息一日
周日休息一日
周一至周五上课五日（内层循环重复5次）
上午 8:30 上课一次
中午 12:00 吃午饭
下午 13:30 上课一次
本学期共上课多少次？
循环嵌套 5-5
有一个算式 1 3 x 32 = 39 83 ，其中问号代表的数字看不清了。你能不能编写一个程序，算出三个 代表的看不清的数字是多少？
本程序采用穷举法。每个问号代表的数字可能是从0到9的十个数字之一。因此，每个问号有十种可能。根据乘法原理，总共有1000种可能性，通过三重循环来实现，每一种可能试一下就找到答案了。
丢失的数字 5-1
新建三个变量 i, j, k，代表三个问号，那么三个数字可分别表示为：103+i*10、320+j、39083+k*100。
使(103+i*10)*(320+j) = 39083+k*100 的 i ,j , k 就是我们要找到数字
丢失的数字 5-2
i, j, k 变化顺序
i = 0
j = 0
k = 0,1,2,...9
i = 0
j = 1
k = 0,1,2,...9
… …
i = 9
j = 9
k = 0,1,2,...9
含义是依次判断
103 x 320 = 39083, 39183,39283...39983
103 x 321 = 39083, 39183,39283...39983
… …
193 x 329 = 39083, 39183,39283...39983
丢失的数字 5-3
答案是：
123 x 321 = 39483
丢失的数字 5-4
修改程序，判断 1 7 x 32 = 39 83 有没有解？看看你的程序是否还能正确运行？
修改程序，判断 x 1 = 6？ 有几个解？看看你的程序是否还能正确运行？
丢失的数字 5-5
循环嵌套
多重循环运用
循环和算法效率
穷举法运用
总结(共20张PPT)
08 列表简介
程序设计基础
学习目标
列表及其操作
0 1
常见数据结构
0 2
手工方式
新建和删除
导入和导出数据
添加删除元素
显示和隐藏
改变显示大小
命令方式
见下页
列表及其操作 2-1
列表及其操作 2-2
新建列表 chengji，通过程序
清空列表所有元素
提示用户输入5个数字，并将数字保存到列表
计算输出所有列表元素的和、最大值、最小值和平均值
列表应用练习 2-1
链表元素输入
查找计算
列表应用练习 2-2
数据结构是计算机存储、组织数据的方式。
数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。
数据结构往往同高效的检索算法和索引技术有关。
数据结构 3-1
一个数据结构是由数据元素依据某种逻辑联系组织起来的。
对数据元素间逻辑关系的描述称为数据的逻辑结构；
数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；
讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。
数据结构 3-2
常见数据结构
集合
数据元素除了同属于一种类型外，别无其它关系
线性结构
线性结构中元素之间存在一对一关系
树形结构
树形结构中元素之间存在一对多关系
图形结构（网状结构）
图形结构中元素之间存在多对多关系
数据结构 3-3
性质
由一组相同数据类型的成员组成
同一集合的成员必须互不相同
集合中的成员一般是无序的，没有先后次序关系
应用举例
实现一个生字本，记录不熟悉的英语单词，同一单词只记录一次
集合
性质
除起始元素外,线性表中的其他元素仅有一个直接前驱元素
除终端元素外,线性表中的其他元素仅有一个直接后继元素
应用举例
输入并保存班级英语成绩，计算平均成绩
线性结构 6-1
分类
1、数组 (Array)
在程序设计中，为了处理方便， 把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组
数组大小一般是“静态”的，插入、删除操作比较困难
线性结构 6-2
分类
2、栈 (Stack)
是只能在某一端插入和删除的特殊线性表
它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）
插入删除只能从一端进行
线性结构 6-3
线性结构 6-4
分类
3、队列 (Queue)
一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列
先进先出
插入从一端进行，删除从另一端进行
线性结构 6-5
分类
链表 (Linked List)
是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
插入、删除可从任意位置进行
线性结构 6-6
树 (Tree)
包含n（n>0）个结点的有穷集合K，且在K中：
（1）有且仅有一个结点 k0，没有前驱，称K0为树的根结点。简称为根（root）　
（2）除k0外，k中的每个结点，有且仅有一个前驱 　　
（3）K中各结点，可以有m个后继（m>=0）
C 盘下所有文件夹和文件构成一棵树
树形结构
图 (Graph)
图是由结点的有穷集合V和边的集合E组成
其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点
边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系
简单图 ：不含多重边和自环的图
应用举例：多个城市，道路相连，最短路径选择
图（网状结构）
不同的数据结构其操作集不同，但下列操作必不可缺： 　　
1. 结构的生成　
2. 结构的销毁 　　
3. 在结构中查找满足规定条件的数据元素
4. 在结构中插入新的数据元素　
5. 删除结构中已经存在的数据元素　　
6. 遍历
数据结构的操作
列表及其操作
常见数据结构
总结(共12张PPT)
09 查找
程序设计基础
顺序查找
二分查找
学习目标
查找是计算机中常见的操作之一
例如，查找文件，查找资料，字典中查找单词等
查找练习
在一组数字中查找指定数字，找到则报告其位置。如果找不到，也要给出恰当提示，说明查找的数字不存在。
问题
怎样存储待查找的数字？
查找
创建一个列表，依次加入数字 23 、32 、56 、12 、17、28六个数字，编写程序在这组数字中查找用户输入的数字。
例如：用户输入查找12，返回其在列表中的位置。用户输入查找查找19，要能够显示不存在该数字
练习
第一个数字开始，依次查找第二个、第三个数字，直到找到要找的数字或查完所有数字为止。
顺序遍历查找，不要求数字是有顺序的，但是查找效率比较低。一组数字中数字越多，所用的时间可能越长。
顺序查找 3-1
顺序查找 3-2
代码二：
增加“存在”变量作为查找目标是否存在的标志
开始假设不存在，将“存在”变量值设置为0
如果找到变量，将“存在”变量值设置为1
最后如果“存在”变量值仍为0，说明查找目标在列表中不存在
顺序查找 3-3
二分查找又称折半查找，它是一种效率较高的查找方法，应用二分查找要求：
1.必须采用顺序存储结构
2.必须按关键字大小有序排列　　
优点是比较次数少，查找速度快，平均性能好
缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表 　　
二分查找 4-1
算法思想
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；
否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功
二分查找 4-2
first 存放子表的起始元素位置
last 存放子表的结束元素位置
middle 存放子表的中间元素位置
Target 存放待查找的目标
二分查找 4-3
二分查找 4-4
遍历查找
不要求数据有序
效率低
二分查找
要求数据有序
效率高
上网查询：还有哪些查找算法？各适用于什么情况？
总结

展开更多......

收起↑