Scratch 趣味编程 趣味数学求墙面最大矩形面积（课件）小学信息技术课后服务课程通用版

老师： 墙面最大矩形面积 scratch数学篇 HI! 导读 问题背景：工人砌了一面奇特的砖墙，该墙由N列砖组成（1≤N≤106），且每列砖的数量为Ki（1≤Ki≤104，相邻两列砖之间无缝隙），每块砖的长宽高都为1。小蓝为了美化这面墙，需要在这面墙中找到一块面积最大的矩形用于涂鸦，那么请你帮助小蓝找出最大矩形，并输出其面积。 例如：当N = 6，表示这面墙有6列，每列砖的数量依次为3、2、1、5、6、2，如下图所示： 思路分析 本题目是求解最优性质问题，可以首先考虑是否采用动态规划算法。动态规划是一种将问题实例分解为更小的、相似的子问题，该算法是通过求解局部子问题的解达到全局最优解。不过本题目明显不需要对问题进行分解，可以考虑采用枚举算法，枚举所有的可能性，并找到最大值即可。我们最终可以把问题转化为把墙面的每一列当做矩形的宽度，分别向左右两边进行拓展，找到能够形成矩形的长度并计算其面积，最后找出最大面积值即可。根据用例输入的每一列砖块数据，可得每一列形成的矩形面积(宽度*高度=面积)值分别为：3*1=3；2*2=4；1*6=6；5*2=10；6*1=6；2*3=6。 walll 1：初始询问用户输入。同时新建变量（最大面积）初始值为0。 这面墙共有几列砖组成？假设用户输入6。 每一列砖块的数量是多少？假设用户输入3 2 1 5 6 2。 walll 注意输入数据的格式（3 2 1 5 6 2），这里要求每个数据之间用空格隔开。我们把每个数据值获取到同时保存到列表（每列砖数）中。通过遍历字符串的方式处理。程序如下： walll 遍历列表中的每项数值，采用克隆积木搭建出整个墙面的图形。思路就是当克隆出一列墙面后，坐标位置重新回到底部并且x坐标增大。本作品采用自制积木完成。程序如下： walll 核心算法程序部分。新建两个变量（向左）和（向右）分别表示以当前列的位置向左，向右拓展。当拓展列的砖块数小于当前列的砖块数时，拓展结束，因为此时已经无法构成以当前列砖块数为宽度的矩形。面积值计算公式如下： 面积值=当前每列砖块数*（右边位置-左边位置-1） 本作品依然采用自制积木完成，程序如下： walll 同时又使用了一个自制积木返回两个数之间的最大数用来求得每次比较后较大面积值，当程序结束后可得最大面积值。程序如下： 总结和思考 本作品是一个难度较大的数学题目，采用了枚举算法，涉及到知识点如下： 对列表和字符串进行遍历。 克隆积木的使用技巧。 自制积木如何定义函数方法。 枚举算法是日常中使用到的最多的一个算法，核心思想是枚举所有的可能性。枚举算法简单粗暴，它暴力的枚举所有可能，尽可能地尝试所有的方法。使用该算法需要满足两个条件： 可预先确定候选答案的数量。 候选答案的范围在求解之前必须有一个确定的集合。 谢谢观看 班主任： $$