2020年青少年信息学python教案-p12-教案——《贪心算法》.pdfVIP

p12教案——《贪⼼算法》

【上节课衔接语】

好的上节课呢我们了解了什么是算法，并结合取余循环绘制出了彩⾊多边形。那么

这节课呢，我们将结合贪⼼算法的思想和取余取整运算来完成找零程序的编写。

1、知识点

2、课前导⼊、任务说明部分

【知识概览】

3、任务清单

视频1：取整运算

【创作任务】试验⼀下取余取整的效果。

【知识点】

1、符号：

除法符号：/

取余符号：%

取整符号：//

2、当被除数⼩于除数时，取整结果为0，取余结果为被除数本身。

⽐如：2➗50……2，取整为0，取余为2

【视频任务】

【效果截图】

【代码块】

1print(5//2,5%2)

2print(2//5,2%5)

【提问】

Q：当被除数⼩于除数时，取整和取余的结果分别是什么呢？

A：当被除数⼩于除数时，取整结果为0，取余结果为被除数本身。

⽐如：2➗50……2，取整为0，取余为2

【课中练习】

以下代码运行的结果是什么？

a=2

b=3

c=5

d=a+b*c//a

print(d%2)

A.2

B.3

C.5

D.1

答案：

D.1

答案解释：

d的值为2+3*5//2的结果9，所以最终运行结果是9%2得到1

【下⼀个衔接话术】

好的，那么我们以及知道了取余取整的含义。接下来我们⼀起来建⽴⼀下找零任务的规则，看

完视频可以告诉⽼师。

视频2：找零钱问题的思路

【任务】确定找零钱算法的规则。

【知识点】

1、对于算法来说，⼀定要简化问题、设定⼀个能找到最优解的规则

2、找零钱：

【下⼀个衔接话术】

看完视频我们知道，为了简化问题，就要设定⼀个能找到最优解的规则。现在确定好了找零钱

的规则，那接下来我们⼀起来完成找零程序的编写。

视频3：找零钱程序

【创作任务】完成找零钱程序的编写。

【知识点】

1、利⽤取整，来得到当前纸币种类能找的张数。

2、利⽤取余，来得到剩下还没找的钱数

【视频任务】

【效果截图】

【代码块】

1#找零钱目标数

2target=99

3#纸币种类

4money=[50,20,10,5,2,1]

5#结果

6number=[0,0,0,0,0,0]

7#循环，从最大面值的纸币开始找零钱

8foriinrange(6):

9number[i]=target//money[i]#取整，算出当前面值可以找的最大张数

10target=target%money[i]#取余，算出当前面值找零后剩下的钱数

11#循环打印出不同面值对应的张数

12foriinrange(6):

13print(money[i],元的张数为:,number[i],张)

【代码截图】

【下⼀个衔接话术】

接下来啊来我们详细的来了解⼀下什么是贪⼼算法吧。

视频4：认识贪⼼算法

【知识点】

1、贪⼼算法：它每⼀步都是⽤最简单的规则取考虑，得到在当前规则下的最优解。

2、贪⼼算法有时并⾮是最好的结果，但⼀定是最⽅便快捷的。

【提问】

Q：运⽤贪⼼算法得到的结果⼀定是最好的吗?

A：贪⼼算法有时并⾮是最好的结果，但⼀定是最⽅便快捷的。刚才的视频中也有印证这⼀

点。

【图⽚任务】

【提示】需要导⼊海⻳库，设置好画笔粗细。再创建⼀个颜⾊列表，颜⾊和对应的⾯值要⼀⼀

对应，在第⼆个for循环中去调⽤颜⾊列表中的颜⾊。

【答案】

【效果截图】

【代码块】

1importturtle

2myPen=turtle.Pen()

3myPen.pensize(5)

4target=99#找零钱目标数

5money=[50,20,10,5,2,1]#纸币种类

6number=[0,0,0,0,0,0]#