您所在位置：网站首页 > 中学教育 > 教学课件 > 初中课件林厚从信息学奥赛课课通第7单元第8课栈的应用课件

林厚从信息学奥赛课课通第7单元第8课栈的应用课件

13页

卖家[上传人]：ji****en

文档编号：126683715

上传时间：2020-03-27

文档格式：PPT

文档大小：100KB

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

20 金贝

/ 13 举报版权申诉马上下载

文本预览

下载提示

常见问题

1、第7单元第8课栈的应用例1 括号匹配 check 1s 256MB 假设表达式中允许包含两种括号圆括号和方括号其嵌套的顺序随意即或等为正确的格式或或均为不正确的格式本题的任务是检测一个给定表达式中的括号是否正确匹配输入一个只包含上述括号的字符串判断字符串中的括号是否匹配匹配就输出 OK 不匹配就输出 Wrong 输入格式一行字符只含有圆括号和方括号个数小于255 输出格式匹配就输出一行文本 OK 不匹配就输出一行文本 Wrong 输入样例输出样例 Wrong 问题分析一个匹配的括号序列必定是左右圆括号方括号的数量一样多但是反过来一样多不一定是匹配的定义一个字符型的栈来维护左括号按顺序处理括号序列 1 遇到左括号将它入栈 2 遇到右括号检查栈顶元素与右括号是否匹配如果匹配将栈顶左括号出栈否则判断出序列不匹配结束如果读到了左括号而栈为空也不匹配如果序列处理完毕栈非空也不匹配例2 表达式求值 NOIP2013普及组复赛 expr 1s 256MB 题目描述给定一个只包含加法和乘法的算术表达式请你编程计算表达式的

2、值输入格式输入仅有一行为需要你计算的表达式表达式中只包含数字加法运算符和乘法运算符且没有括号所有参与运算的数字均为0到2 31 1之间的整数输入数据保证这一行只有0 9 这12种字符输出格式输出只有一行包含一个整数表示这个表达式的值注意当答案长度多于4位时请只输出最后4位前导0不输出输入输出样例输入样例1 输入样例2 输入样例3 1 1 3 41 1234567890 11 1000000003 1输出样例1 输出样例2 输出样例3 878914说明对于30 的数据 0 表达式中加法运算符和乘法运算符的总数 100 对于80 的数据 0 表达式中加法运算符和乘法运算符的总数 1000 对于100 的数据 0 表达式中加法运算符和乘法运算符的总数 100000 问题分析由于只有加号和乘号只要从左往右扫一遍如果遇到乘号直接计算做乘法如果遇到加号若后面没有符号或者后面一个符号也是加号则直接计算做加法否则先把后面紧接着的连续的乘号算完最后再加算法实现中只要设置一个栈保存没有立即进行的加法扫描结束后再一起处理栈中的加法运算同时因

3、为把一个数字串转换成数也需要单独编写一个子程序最后还要注意实现过程中及时对10000取模例3 图的深度优先遍历 graph dfs 1s 256MB 问题描述读入一个用邻接矩阵存储的无向图输出它的深度优先遍历序列输入格式第1行 1个正整数n 表示图中的顶点数 2 n 100 接下来的n行是一个n n的邻接矩阵 a i j 1表示顶点i和顶点j之间有直接边相连 a i j 0表示没有直接边相连保证i j时 a i j 0 并且a i j a j i 输出格式输出1 n的某一种排列表示从顶点1开始对该图进行深度优先遍历得到的顶点序列每两个数之间用一个分隔输入样例 80110000010011000100000110100010001000100000110000010000100100010输出样例 1 2 4 6 5 3 7 8 练习1 瓷砖 tile 1s 256MB 问题描述在一个w h的矩形广场上每一块1 1的地面都铺设了红色或黑色的瓷砖小谢同学站在某一块黑色的瓷砖上他可以从此处出发移动到上下左右四个相邻的且是黑色的瓷砖上现在他想知道

4、通过重复上述移动所能经过的黑色瓷砖数输入格式第1行为两个数h和w 2 w h 50 之间有一个空格隔开以下为一个w行h列的二维字符矩阵每个字符为分别表示该位置为黑色的瓷砖红色的瓷砖以及小Y的初始位置输出格式 1行一个整数表示小Y从初始位置出发可以到达的瓷砖数输入样例输出样例 11959 练习2 最大黑区域 area 1s 256MB 问题描述二值图像是由黑白两种像素组成的矩形点阵图像识别的一个操作是求出图像中最大黑区域的面积请设计一个程序完成二值图像的这个操作黑区域由黑像素组成一个黑区域中的每个像素至少与该区域中的另一个像素相邻规定一个像素仅与其上下左右的像素相邻两个不同的黑区域没有相邻的像素一个黑区域的面积是其所包含的像素的个数输入格式第1行两个正整数n和m 1 n m 100 分别表示二值图像的行数和列数后面紧跟着n行每行含m个整数0或1 其中第i行表示图像的第i行的m个像素 0表示白像素 1表示黑像素同一行的相邻两个整数之间用一个空格隔开两个测试例之间用一个空行隔开最后一个测试例之后隔一个空行再接的一行含有两个整数0 标志输入的结束输出格式 1行 1个数表示相应的图像中最大黑区域的面积输入样例 56011001110101010010000111101110输出样例 7

《林厚从信息学奥赛课课通第7单元第8课栈的应用课件》由会员ji****en分享，可在线阅读，更多相关《林厚从信息学奥赛课课通第7单元第8课栈的应用课件》请在金锄头文库上搜索。

点击阅读更多内容

TA的资源

公司项目总结汇报模板

机电安装工程质量控制

第五章文化产业项目策划的基本流程

第十一章流水施工方法

第六章网络工程施工实用技术

第6讲MM440变频器的基本控制电路

C语言第三讲程序结构(下)

ch02半导体材料特性

2012年1月工作总结(质量安全部A)

项目五劳动力分配项目六下达指令

透析therebe的非谓语结构

建筑概论第一章建筑工程材料_第一讲材料的物理性质

电子设计工程师认证2

第五章项目执行与控制b

第十节景观工程、石作工程

第三讲串联谐振电路

第5章地籍控制测量

心理学的发展历史和流派

微型计算机技术陈慈发第7讲数据传送指令

计量经济学第七章误差序列相关

点击查看更多

新上传的PPT文档

有关爱心募捐倡议书戛洒镇中心小学2013年秋季学期科学实验教学计划企业计时人员薪酬制度实施细则 2019清洁取暖双替代（气代煤）取暖设备采购项目初中数学教学案例分析工程管理专业人才培养方案 2022学年度助推站年终工作总结功能模块线束项目申请报告写作参考模板个人信息管理系统课程设计报告鼓励退伍学生坚定信心向榜样看齐道路景观绿化工程施工设计方案集合竞价的秘密 2023年体育教案田径运动理论力学试卷B 县长履行党风廉政建设主体责任报告