第1 章单片机概述
一、单片机的概念P.12
在一块芯片上集成了CPU、RAM、ROM、定时/计数器、中断控制器以及串行口，并行I/O接口等，构成的一个完整的微型计算机系统。
二、单片机的特点P.12
（1）小巧灵活、成本低、易于产品化
（2）可靠性高、适用的温度范围宽
（3）易扩展、控制功能强
（4）指令系统相对简单，较易掌握
三、单片机的分类P.8-11
1.按片内不同程序存储器的配置来分
（1）片内带Mask ROM（掩膜ROM）型（2）片内带EPROM型（3）片内无ROM（ROMLess）型
2.按片内不同容量的存储器配置来分
（1）51子系列型（2）52子系列型
3.按芯片的半导体制造工艺上的不同来分
（1）HMOS工艺型（2）CHMOS工艺型
4.A T89系列单片机分类
第2 章 MCS-51 系列单片机的内部结构
一、MCS-51单片机的内部结构
P.13-17
中央处理器CPU ：8位，运算和控制功能
内部RAM ：共256个RAM 单元，用户使用前128个单元，存放可读写数据，后128个单元被SFR 占用。通常内部RAM 指的是前128B,即00H-FFH 。
内部ROM ：4KB FLASH ROM ，用于存放程序、原始数据和表格。 定时/计数器：2个16位的定时/计数器，实现定时或计数功能。 并行I/O 口：4个8位的I/O 口P0、P1、P2、P3。 串行口：一个全双工串行口。 中断控制系统：5个中断源 时钟电路：可产生时钟脉冲序列
二、MCS-51单片机的外部引脚：控制引脚ALE 、RST 、PSEN 、EA 、RD 、WR 的功能 P.19
ALE: 地址锁存有效信号输出端 RST: 复位引脚
PSEN :外部ROM 读选通信号
EA :片外程序存储器选择信号
RD :外部RAM 读选通信号输出端，低电平有效 WR :外部RAM 写选通信号输出端，低电平有效
三、单片机的存储器组织结构：存储器空间、寻址范围、功能
P.19-22
计算机的存储器结构有两种：
时钟电路 CPU
ROM RAM
T0 T1
中断系统
串行接口
并行接口
P0 P1 P2 P3
TXD
RXD
INT0
INT1
定时计数器
哈佛结构：程序存储器和数据存储器分开，相互独立；
普林斯顿结构：程序存储器和数据存储器是统一的，地址空间统一编址。
MCS-51单片机属于哈佛结构：程序存储器和数据存储器分开。
MCS-51单片机存储空间分布图
MCS-51单片机存储器地址空间分为3类：
1、片内、外统一编址的64KB程序存储器地址空间0000H～FFFFH（16位）
2、64KB片外数据存储器地址空间，地址0000H～FFFFH（16位）
3、128B片内数据存储器地址空间（8位）,地址00H～FFH。
内部RAM数据存储器
工作寄存器区（00H-1FH）：用于暂存系统运行时的中间结果。共4组，每组8个寄存器：R0~R7，CPU当前使用的工作寄存器区由程序状态字PSW的3、4位决定。
位寻址区（20H-2FH）：16个单元的每一位都有一个位地址(16*8)。存放各种标志位信息和为数据.
通用RAM区（30H-7FH）：用于存放各种数据（原始数据、中间结果、最终结果）和堆栈。
堆栈：用于保护CPU的现场，后进先出（LIFO）的RAM缓冲器。堆栈的栈顶位置由堆栈指针SP确定。
四、特殊功能寄存器SFR中各个寄存器的地址和功能P.22-24
特殊功能寄存器/专用寄存器SFR（80H-FFH）
专用于控制、管理单片机内部并行I/O接口、串行口、算术逻辑部件、定时器/计数器、中断系统等功能模块的工作。
21个SFR, 分别用于以下各个功能单元：
CPU：ACC、B、PSW、SP、
DPTR（两个8位寄存器DPL、DPH组成）
并行口：P0、P1、P2、P3
中断系统：IE、IP
定时/计数器：TMOD、TCON、TH1、TL1、TH0、TL0
串行口：SCON，SBUF，PCON
五、单片机并行I/O接口：P0、P1、P2、P3的功能P.24-28
P0口有三个功能：
1、外部扩展存储器时,当做数据总线（如图1中的D0~D7为数据总线接口）
2、外部扩展存储器时,当作地址总线（如图1中的A0~A7为地址总线接口）
3、不扩展时,可做一般的I/O使用,但内部无上拉电阻,作为输入或输出时应在外部接上拉电阻。P1口只做I/O口使用：其内部有上拉电阻。
P2口有两个功能：
1、扩展外部存储器时,当作地址总线使用
2、做一般I/O口使用,其内部有上拉电阻;
P3口有两个功能：
除了作为I/O使用外（其内部有上拉电阻）,还有一些特殊功能,由特殊寄存器来设置
六、单片机的时钟周期、机器周期P.29
时钟周期：时钟电路产生的振荡脉冲的周期，也叫节拍，
一般用P表示。
状态：2个节拍组成一个状态，一般用S表示。
机器周期：计算机工作的最小时间单位(最短指令执行时间)一个机器周期包含6个状态，即12个时钟周期（S1P1、S1P2、S2P1、S2P2、 、S6P1、S6P2）
指令周期：CPU执行一条指令所需要的时间。一般是1、2、4个机器周期。
指令周期=(1~4)*机器周期=6*时钟周期=2*1/振荡周期=1/振荡频率(μs)
七、单片机的复位电路方式、复位后各SFR的初始状态P.31-32
89系列单片机的复位信号是从RST引脚输入到芯片内的施密特触发器中的。当系统处于正常工作状态时，且振荡器稳定后，如果RST引脚上有一个高电平并维持2个机器周期(24个振荡周期)以上，则CPU 就可以响应并将系统复位。
单片机系统的复位方式有：手动按钮复位和上电复位。
第4 章MCS-51 系列单片机C 语言程序设计
一、C51特有的数据类型P.89-91
特殊功能寄存器型(sfr和sfr16)和位类型(bit和sbit)
二、C51变量的存储（器）类型及对应的存储器区域P.94
第5 章MCS-51 型单片机的内部硬件资源及应用
一、MCS-51单片机的中断源、中断请求标志、中断入口地址P.132-133 中断源：引起中断的原因，或能发出中断申请的来源。
中断源：51系列有5个，52系列有6个
5个中断源：
2个外部中断源、2个定时中断源、1个串行口中断源
外部中断输入信号INT0、INT1：外部0（1）中断请求信号。
由P3.2（P3.3）输入。
由IT0（IT1）决定中断请求信号是低电平还是下降沿有效。
输入信号有效时，IE0（IE1）=1，请求中断。
定时中断TF0、TF1：T0（T1）溢出中断请求。
定时器产生溢出时，TF0（TF1）=1，请求中断。
串口中断RI、TI：串行中断请求。
接收（发送）完一帧数据，RI（TI）=1，请求中断。
中断入口地址（中断矢量）
中断源入口地址
INT0 0003H
T0 000BH
INT 10013H
T1 001BH
RI（TI）0023H
中断请求标志：锁存在TCON、SCON的相应标志位中。
定时/计数器控制寄存器TCON（88H）
IE1（IE0）: 外部1（0）中断请求标志。
=1 存在中断请求；=0 无中断请求
IT1（IT0）: 外部中断触发方式选择。
=0 低电平触发；=1 下降沿触发
串口控制寄存器SCON（98H）
TI: 发送中断标志位。硬件置位，软件复位。
TI=1时，可申请中断或软件查询。
RI: 接收中断标志位。硬件置位，软件复位。
RI=1时，可申请中断或软件查询。
三、MCS-51单片机的串行通信接口的4种工作方式及特点P.150-153
二、MCS-51单片机的定时/计数器的应用：中断方式产生方波
第6 章MCS-51 型单片机系统功能的扩展.
一、数据存储器及程序存储器的扩展：地址计算及程序编写
二、74LS377、74LS244扩展并行I/O口：地址计算
第7章MCS-51 型单片机接口技术
一、LED数码管显示器的动态显示接口电路：74LS377的地址计算及程序编写
二、键盘的接口电路：独立式键盘扩展及编程；矩阵式键盘接口扩展及编程
三、ADC0809与单片机的接口电路：8个通道地址计算、中断方式编程
四、DAC0832的3种工作方式；DAC0832与单片机的接口电路地址计算、输入数字量与输出模拟量的对应关系式
注意：考试为开卷。
电子科技大学 期末解题报告 课程：《ACM算法与程序设计》学院： 学号： 姓名： 报告成绩：教师签名：
讨厌的青蛙 1、链接地址 https://www.doczj.com/doc/ae4598075.html,/problem?id=2812 2、问题描述 在韩国，有一种小的青蛙。每到晚上，这种青蛙会跳越稻田，从而踩踏稻子。农民在早上看到被踩踏的稻子，希望找到造成最大损害的那只青蛙经过的路径。每只青蛙总是沿着一条直线跳越稻田，而且每次跳跃的距离都相同，如图1所示。稻田里的稻子组成一个栅格，每棵稻子位于一个格点上，如图2所示。而青蛙总是从稻田的一侧跳进稻田，然后沿着某条直线穿越稻田，从另一侧跳出去，如图3所示。 问题描述
青蛙的每一跳都恰好踩在一棵水稻上，将这棵水稻拍倒。可能会有多只青蛙从稻田穿越，有些水稻被多只青蛙踩踏，如图4所示。当然，农民所见到的是图5中的情形，看不到图4中的直线。 根据图5，农民能够构造出青蛙穿越稻田时的行走路径，并且只关心那些在穿越稻田时至少踩踏了3 棵水稻的青蛙。因此，每条青蛙行走路径上至少包括3 棵被踩踏的水稻。而在一条青蛙行走路径的直线上，也可能会有些被踩踏的水稻不属于该行走路径。在图5中，格点(2, 1)、(6, 1)上的水稻可能是同一只青蛙踩踏的，但这条线上只有两棵被踩踏的水稻，因此不能作为一条青蛙行走路径；格点(2, 3)、(3, 4)、(6, 6)在同一条直线上，但它们的间距不等，因此不能作为一条青蛙行走路径；格点(2, 1)、(2, 3)、(2, 5)、(2, 7)是一条青蛙行走路径，该路径不包括格点(2, 6)。请你写一个程序，确定在所有的青蛙行路径中，踩踏水稻棵数最多的路径上有多少棵水稻被踩踏。例如，图5的答案是7，因为第6 行上全部水稻恰好构成一条青蛙行走路径。
题目来源：福州大学acm网站 代码：fpcdq 一、入门 熟悉ACM竞赛规则以及程序提交注意事项 例题： Problem 1000 A+B Problem Time Limit: 1000 mSec Memory Limit : 32768 KB Problem Description Calculate a + b. Input The input will consist of a series of pairs of integers a and b,separated by a space, one pair of integers per line. Output For each pair of input integers a and b you should output the sum of a and b in one line,and with one line of output for each line in input. Sample Input 1 5 2 3 Sample Output 6 5
My answer： #include
The Mailboxes Manufacturers Problem Time Limit:1000MS Memory Limit:65536K Total Submit:299 Accepted:227 Description In the good old days when Swedish children were still allowed to blowup their fingers with fire-crackers, gangs of excited kids would plague certain smaller cities during Easter time, with only one thing in mind: To blow things up. Small boxes were easy to blow up, and thus mailboxes became a popular target. Now, a small mailbox manufacturer is interested in how many fire-crackers his new mailbox prototype can withstand without exploding and has hired you to help him. He will provide you with k(1 ≤ k≤ 10) identical mailbox prototypes each fitting up to m(1 ≤ m≤ 100) crackers. However, he is not sure of how many firecrackers he needs to provide you with in order for you to be able to solve his problem, so he asks you. You think for a while and then say, “Well,if I blow up a mailbox I can’t use it again, so if you would provide me with only k = 1 mailboxes, I would have to start testing with 1 cracker, then 2 crackers, and so on until it finally exploded. In the worst case, that is if it does not blow up ev en when filled with m crackers, I would need 1 + 2 + 3 + … + m = m ×(m+ 1) ? 2 crackers. If m = 100 that would mean more than 5000 fire-crackers!” “That’s too many,” he replies. “What if I give you more than k = 1 mailboxes? Can you find a strategy that requires less crackers?” Can you? And what is the minimum number of crackers that you should ask him to provide you with? You may assume the following: 1.If a mailbox can withstand x fire-crackers, it can also withstand x? 1 fire-crackers. 2.Upon an explosion, a mailbox is either totally destroyed (blown up) or unharmed, which means that it can be reused in another test explosion.
Acm试题及答案 1001 Sum Problem (2) 1089 A+B for Input-Output Practice (I) (4) 1090 A+B for Input-Output Practice (II) (6) 1091 A+B for Input-Output Practice (III) (8) 1092 A+B for Input-Output Practice (IV) (9) 1093 A+B for Input-Output Practice (V) (11) 1094 A+B for Input-Output Practice (VI) (12) 1095 A+B for Input-Output Practice (VII) (13) 1096 A+B for Input-Output Practice (VIII) (14) 2000 ASCII码排序 (16) 2001计算两点间的距离 (17) 2002计算球体积 (19) 2003求绝对值 (20) 2004成绩转换 (21) 2005第几天 (22) 2006求奇数的乘积 (24) 2007平方和与立方和 (26) 2008数值统计 (27) 2009求数列的和 (28) 2010水仙花数 (29) 2011多项式求和 (31) 2012素数判定 (33) 2014青年歌手大奖赛_评委会打分 (34) 2015偶数求和 (36) 2016数据的交换输出 (38) 2017字符串统计 (40) 2019数列有序! (41) 2020绝对值排序 (43) 2021发工资咯：） (45) 2033人见人爱A+B (46) 2039三角形 (48) 2040亲和数 (49)
海南软件职业技术学院第四届计算机文化节 程序设计大赛决赛题 提醒：请各队在各自电脑D盘根目录下创建一个命名为“2010程序设计大赛-队名”的文件夹，将所有题目的答案都放到此目录底下。 做题过程中请注意保存。每做完一题就通过电子教室系统提交一次，电脑上没装电子教室软件的每题做完后举手示意工作人员用U盘提交。 各题源文件都分别保存在一个单独的文件夹中，文件夹命名为：题号_队名。 第一部分（简单题型）： 1、（10分）马克思手稿中有一道趣味数学问题：有30个人，其中有男人、女人和小孩， 在一家饭馆吃饭花了50先令；每个男人花3先令，每个女人花2先令，每个小孩花1先令；问男人、女人和小孩各有几人？输出所有可能的组合。 样例输出： Men Women Children 1: 0 20 10 2: 1 18 11 3: 2 16 12 4: 3 14 13 5: 4 12 14 6: 5 10 15 7: 6 8 16 8: 7 6 17 9: 8 4 18 10: 9 2 19 11: 10 0 20 Java参考答案： void main() { int men,women,children; int count=0; printf(" %10s%10s%10s\n”,”men”,”women”,”children"); for(men=0;men<=16;men++) for(women=0;women<=25;women++) for(children=0;children<=30;children++) if(men+women+children==30&&men*3+women*2+children==50) { count++; printf(“%2d%10d%10d%10d\n”,count,men,women,children); } }
备战ACM资料 一：知识点 数据结构： 1，单，双链表及循环链表 2，树的表示与存储，二叉树（概念，遍历）二叉树的应用（二叉排序树，判定树，博弈树，解答树等） 3，文件操作（从文本文件中读入数据并输出到文本文件中） 4，图（基本概念，存储结构，图的运算） 数学知识 1，离散数学知识的应用（如排列组合、简单的图论，数理逻辑） 2，数论知识 3，线性代数 4，组合代数 5，计算几何 二算法 1，排序算法（冒抛法，插入排序，合并排序，快速排序，堆排序） 2，查找（顺序查找，二分发） 3，回溯算法 4，递归算法 5，分治算法 6，模拟法 7，贪心法 8，简单搜索算法（深度优先，广度优先），搜索中的剪枝，A*算法 9，动态规划的思想及基本算法 10，高精度运算 三、ACM竞赛的题型分析 竞赛的程序设计一般只有16种类型，它们分别是： Dynamic Programming （动态规划） Greedy （贪心算法） Complete Search （穷举搜索） Flood Fill （不知该如何翻译） Shortest Path （最短路径） Recursive Search Techniques （回溯搜索技术） Minimum Spanning Tree （最小生成树） Knapsack （背包问题） Computational Geometry (计算几何学) Network Flow （网络流） Eulerian Path （欧拉回路） Two-Dimensional Convex Hull （不知如何翻译） BigNums （大数问题）
Heuristic Search （启发式搜索） Approximate Search （近似搜索） Ad Hoc Problems （杂题） 四ACM竞赛参考书 《实用算法的分析与程序设计》（吴文虎，王建德著，电子工业出版社，竞赛类的黑宝书）《青少年国际和全国信息学（计算机）奥林匹克竞赛指导）――组合数学的算法 和程序设计》（吴文虎，王建德著，清华大学出版社，参加竞赛组合数学必学） 《计算机算法设计与分析》（王晓东编著，最好的数据结构教材） 《数据结构与算法》（傅清祥，王晓东编著，我所见过的最好的算法教材） 《信息学奥林匹克竞赛指导――1997-1998竞赛试题解析》（吴文虎，王建德著，清华大学出版社） 《计算机程序设计技巧》 D.E.Kruth著，算法书中最著名的《葵花宝典》，大师的作品，难度大） 《计算几何》周陪德著 《ACM国际大学生程序设计竞赛试题与解析（一）》（吴文虎著，清华大学出版社） 《数学建模竞赛培训教材》共三本叶其孝主编 《数学模型》第二版姜启源 《随机规划》 《模糊数学》 《数学建模入门》徐全智 《计算机算法设计与分析》国防科大 五常见的几个网上题库 常用网站： 1）信息学初学者之家：https://www.doczj.com/doc/ae4598075.html,/ （2）大榕树编程世界：https://www.doczj.com/doc/ae4598075.html,/~drs/program/default.asp （3）中国教育曙光网：https://www.doczj.com/doc/ae4598075.html,/aosai/ （4）福建信息学奥林匹克：https://www.doczj.com/doc/ae4598075.html,/fjas/index.htm （5）第20届全国青少年信息学奥林匹克竞赛：https://www.doczj.com/doc/ae4598075.html,/ （6）第15届国际青少年信息学奥林匹克竞赛：https://www.doczj.com/doc/ae4598075.html,/ （7）全美计算机奥林匹克竞赛：https://www.doczj.com/doc/ae4598075.html,/usacogate （8）美国信息学奥林匹克竞赛官方网站：https://www.doczj.com/doc/ae4598075.html,/ （9）俄罗斯Ural州立大学：http://acm.timus.ru/ （10）西班牙Valladolid大学：http://acm.uva.es/problemset （11）ACM-ICPC：https://www.doczj.com/doc/ae4598075.html,/icpc/ （12）北京大学：https://www.doczj.com/doc/ae4598075.html,/JudgeOnline/index.acm （13）浙江大学：https://www.doczj.com/doc/ae4598075.html,/ （14）IOI：http://olympiads.win.tue.nl/ioi/ （15）2003年江苏省信息学奥林匹克竞赛夏令营：https://www.doczj.com/doc/ae4598075.html, （16）https://www.doczj.com/doc/ae4598075.html, （17）https://www.doczj.com/doc/ae4598075.html, （18）https://www.doczj.com/doc/ae4598075.html, （19）https://www.doczj.com/doc/ae4598075.html,/downldmanag/index.asp （20）https://www.doczj.com/doc/ae4598075.html, colin_fox/colin_fox 五如何备战ACM/ICPC
搜集的南开大学的ACM试题与你共享 [A]南开大学Onlinejudge 在线判题系统https://www.doczj.com/doc/ae4598075.html, A.Lucy的新难题 时间限制：2秒内存限制：32000KB 不知不觉，南开大学第三届“我为程序狂”又要拉开帷幕了。这天，Lucy也来到南开大学ACM协会，与大家共同欢庆NKPC的三周岁的日子。 谈笑间，ACM协会的主席拿了圆形的生日蛋糕。大伙开心地唱完了生日歌，一起吹灭了蜡烛。 要分蛋糕了，大家都很兴奋。本着公平的原则，每位到场的人员都要在蛋糕上切一刀。ACM协会的主席事先知道有n位朋友会参与这个欢庆宴会。为了方便大家切蛋糕，主席在订蛋糕的时候就嘱咐在蛋糕的边缘布置上2n朵小花。 每个人切蛋糕都会从蛋糕的边缘的一朵小花笔直地切到蛋糕的另一端的小花，来表达自己对NKPC的祝福。为了尊重其他同学，每个人在切蛋糕一定不会和蛋糕上已有的切痕相交，也不会从别人已切过的小花作为切蛋糕的起点或终点。同时，每位同学在切蛋糕的时候，都要保证后面所有的同学都能够按照上述的规则切蛋糕。这样，蛋糕上就留下n条切痕。 Lucy眨巴眨巴眼睛，问，要是不考虑切蛋糕的先后顺序和谁切的哪一刀，这蛋糕切完了共有多少种切法呢？ 大家听了呵呵一笑，说，那就把这个问题留给NKPC3，作为《Lucy的新难题》吧。 相信聪明的你，一定能够帮Lucy解答她的难题的，对吗？ 输入包括多组测试数据，你应当处理到输入结束为止。 每组输入数据中，都只有一行，仅包含一个正整数n，且0 计算机科学系第二届大学生程序设计竞赛试题题目一 大数乘法 问题描述（Problem Description）： 编程实现位数不超过300位的任意大的两个整数相乘。 输入（Input）： 提示用户输入第一个大数乘数和第二个大数乘数。 输出（Output）： 输出两个大数的乘积。 输入示例（Sample Input）： 请输入第一个乘数：123456789123456 请输入第二个乘数：123456789123456 输出示例（Sample Output）： 两数的乘积是：15230578580673373689799383936 四三二五六一题目二 排球队员站位问题 问题描述（Problem Description）： 左图为排球场的平面图，其中一、二、三、 四、五、六为位置编号，二、三、四号位置为前排，一、六、五号位为后排。某队比赛时，一、四号位放主攻手，二、五号位放二 传手，三、六号位放副攻手。队员所穿球衣分别为１，２，３，４，５，６号，但每个队员的球衣都与他们的站位号不同。已知１号、６号队员不在后排，２号、３号队员不是二传手，３号、４号队员不在同一排，５号、６号队员不是副攻手。 编程求每个队员的站位情况。 输入（Input）： 输出（Output）： 输出每个队员球衣号码和所站的位置编号。 输入示例（Sample Input）： 输出示例（Sample Output）： 球衣号码：1 2 3 4 5 6 位置编号：一 二 三 四 五 六 题目三文件读写 问题描述（Problem Description）： INI文件为一种广泛应用的储存程序配置的文件格式。要求不使用操作系统自带INI文件处理功能，用c++编写一个INI文件读取程序，并把结果输出到显示器及文件result.txt中。 说明： INI文件的结构： [区名字] # 区名注释 键名=键值 # 键值注释 一个区里可以有几个不同键名的键值，例如： 测试用INI文件test.ini： [section] #this is a section comment key=value #this is a key comment [section2] key2=value2 要求程序能读取section2区中键名为key2的值，以及section区中的键名为key的注释。 输入（Input）： 在Windows命令窗口里输入程序名称来运行程序，注意程序所带参数。 输出（Output）： 第一行输出section2区中键名为key2的值。 第二行输出section区中的键名为key的注释。 同时要把此结果输出到显示器和文件result.txt中。 输入示例（Sample Input）： CppFileRW Test.ini 输出示例（Sample Output）： section2区中键名为key2的值是：value2 section区中的键名为key的注释是：this is a key comment 2005年百度之星程序设计大赛试题初赛题目 第一题（共四题 100 分）：连续正整数（ 10 分） 题目描述：一个正整数有可能可以被表示为 n(n>=2) 个连续正整数之和，如： 15=1+2+3+4+5 15=4+5+6 15=7+8 请编写程序，根据输入的任何一个正整数，找出符合这种要求的所有连续正整数序列。 输入数据：一个正整数，以命令行参数的形式提供给程序。 输出数据：在标准输出上打印出符合题目描述的全部正整数序列，每行一个序列，每个序列都从该序列的最小正整数开始、以从小到大的顺序打印。如果结果有多个序列，按各序列的最小正整数的大小从小到大打印各序列。此外，序列不允许重复，序列内的整数用一个空格分隔。如果没有符合要求的序列，输出“NONE” 。 例如，对于 15 ，其输出结果是： 1 2 3 4 5 4 5 6 7 8 对于 16 ，其输出结果是： NONE 评分标准：程序输出结果是否正确。 百度之星程序设计大赛试题 -2 第二题（共四题 100 分）：重叠区间大小（ 20 分） 题目描述：请编写程序，找出下面“ 输入数据及格式” 中所描述的输入数据文件中最大重叠区间的大小。 对一个正整数 n ，如果 n 在数据文件中某行的两个正整数（假设为A 和 B ）之间，即 A<=n<=B 或 A>=n>=B ，则 n 属于该行；如果 n 同时属于行 i 和 j ，则 i 和 j 有重叠区间；重叠区间的大小是同时属于行 i 和 j 的整数个数。 例如，行（ 10 20 ）和（ 12 25 ）的重叠区间为 [12 20] ，其大小为 9 ；行（ 20 10 ）和（ 12 18 ）的重叠区间为 [10 12] ，其大小为 3 ；行 (20 10) 和（ 20 30 ）的重叠区间大小为 1 。 输入数据：程序读入已被命名为 input.txt 的输入数据文本文件，该文件的行数在 1 到 1,000,000 之间，每行有用一个空格分隔的 2 个正整数，这 2 个正整数的大小次序随机，每个数都在 1 和 2^32-1 之间。（为便于调试，您可下载测试 input.txt 文件，实际运行时我们会使用不同内容的输入文件。） 桂林电子科技大学ACM程序设计校内竞赛试题 ▲此套试题共8道，请根据自己实际情况尽最大努力去完成。 ▲每位参赛的同学需在考试用机的工作盘上创建一个名为Exam2004的临时文件夹用以保存所有的工作文件。上机编程调试出正确结果。按照试题顺序把每题的运行结果、源程序和算法说明（即解题思路说明）合并到一个Word 文档。该Word文档的文件名按如下格式命名：学号+姓名最后将该文件拷至制定的服务器上。 1、请看如下图4*4的一个网格。你能告诉我网格中隐含了多少正方形？也许你能手工数出 来，但是你能数100*100或者1000*1000的网格吗？请编写一个程序： 输入：输入一个整数N(0<=N<=100),代表网格的边长 输出：输出2维网格N*N中不同大小的正方形的数目S. 如以上4*4网格共有正方形30 2、对于一个8位二进制码，它的镜像就是将它的第n位于倒数第n位交换，使它的每一位 都这样交换。例如，代表十进制数46的二进制数是00101110。它的镜像是二进制码01110100，即十进制数116。编写一个程序，输入一个整数N(如46)，输出其镜像M(如116)。 3、给你9个整数，这9个整数分别是x的8次方至0次方的系数，请你按照多项式的一般 形式合理地构造（去除不必要的）。例如9个系数分别为0，0，0，1，22，-333，0，1，-1，你要构造并输出一行多项式: x^5+22x^4-333x^3+x-1。要求：可以输入多行系数，再显示结果。 如输入： 0 0 0 1 22 -333 0 1 -1 0 0 0 0 0 0 6 88 0 E(输入结束标志) 输出： x^5+22x^4-333x^3+x-1 6x^2+88x 4、美国人的家族 农夫John对他的奶牛继承关系非常认真。但是他不是一个很好的记录员，他以一种二叉树的方法来记录他奶牛的继承关系。他用字符串来记录一棵树的前序、中序遍历，而不是用图形方式来表示这棵树。你的任务是对于给出的奶牛继承关系的前序树和中序树表示，找出它的后序树表示。每个奶牛的名字用一个字母来代表。 输入规范 第一行输入中序序列 第二行输入前序序列 输出规范 显示后序序列 实例输入 In order: AEDFCHG // 中序序列输入 Problem A ISBN号码 Description 每一本正式出版的图书都有一个ISBN号码之对应，ISBN码包括9位数字、1位识别码和3位分隔符，其规定格式如“x-xxx-xxxxx-x”，其中符号“-”是分隔符（键盘上的减号），最后一位是识别码，例如0-670-82162-4就是一个标准的ISBN码。ISBN码的首位数字表示书籍的出版语言，例如0代表英语；第一个分隔符“-”之后的三位数字代表出版社，例如670代表维京出版社；第二个分隔之后的五位数字代表该书在该出版社的编号；最后一位为识别码。 识别码计算方法如下： 首位数字乘以1加上次位数字乘以2……以此类推，所得的结果mod 11，所得的余数即为识别码，如果余数为10，则识别码为大写字母X。例如ISBN号码0-670-82162-4中的识别码4是这样得到的：对067082162这9个数字，从左至右，分别乘以1，2.，……，9，再求和，即0×1+6×2+……+2×9=158，然后取158 mod 11 的结果4作为识别码。 你的任务是编写程序判断输入的ISBN号码中识别码是否正确，如果正确，则仅输出“Right”；如果错误，则输出你认为是正确的ISBN号码。 Input 输入只有一行，是一个字符序列，表示一本书的ISBN号码（保证输入符合ISBN号码的格式要求）。 Output 输出共一行，假如输入的ISBN号码的识别码正确，那么输出“Right”，否则，按照规定格式，输出正确的ISBN号码（包括分隔符“-”）。 Sample1 Input 0-670-82162-4 Sample2 Input 0-670-82162-0 Sample1 Output Right Sample2 Output 0-670-82162-4 2012年四川理工学院“达内杯”大学生程序设计竞赛试题 Problem 1：Sorting There are 16 random sorting numbers from 0 to 15, and they could be converted to different binary numbers, which have 4 digits. Please code algorithm to sort them by the order that the first there digits of the former number is same to the last there digits of the following. The first number of the sorted is always the first given number. Sample Input： 1 3 5 7 9 11 13 15 0 2 4 6 8 10 12 14 Sample Output： 1 2 4 9 3 7 15 14 13 10 5 11 6 12 8 0 Problem 2：Solution of Equation In the interval [0,1], please programming to give the real root, of which error is less than 10-3, of equation ax3+bx2+cx+d=0, where a, b ,c and d are real number. And print the real root or the character “no solution”. Sample Input： 1：a =1 b =－1 c =－2 d =1 2：a =1 b =1 c =1 d =1 Sample Output： 1：x =0.444335937 2：no solution ACM入门之新手入门 1.ACM国际大学生程序设计竞赛简介 1)背景与历史 1970年在美国T exasA&M大学举办了首次区域竞赛，从而拉开了国际大学生程序设计竞赛的序幕。1977年，该项竞赛被分为两个级别：区域赛和总决赛，这便是现代ACM竞赛的开始。在亚洲、美国、欧洲、太平洋地区均设有区域赛点。1995至1996年，来自世界各地的一千多支s代表队参加了ACM区域竞赛。ACM大学生程序设计竞赛由美国计算机协会（ACM）举办，旨在向全世界的大学生提供一个展示和锻炼其解决问题和运用计算机能力的机会，现已成为全世界范围内历史最悠久、规模最大的大学生程序设计竞赛。 2)竞赛组织 竞赛在由各高等院校派出的3人一组的队伍间进行，分两个级别。参赛队应首先参加每年9月至11月在世界各地举行的“区域竞赛(Regional Contest)”。各区域竞赛得分最高的队伍自动进入第二年3月在美国举行的“总决赛(Final Contest)”，其它的高分队伍也有可能被邀请参加决赛。每个学校有一名教师主管队伍，称为“领队”(faculty advisor)，他负责选手的资格认定并指定或自己担任该队的教练(coach)。每支队伍最多由三名选手(contestant)组成，每个选手必须是正在主管学校攻读学位的学生。每支队伍最多允许有一名选手具有学士学位，已经参加两次决赛的选手不得再参加区域竞赛。 3)竞赛形式与评分办法 竞赛进行5个小时，一般有6~8道试题，由同队的三名选手使用同一台计算机协作完成。当解决了一道试题之后，将其提交给评委，由评委判断其是否正确。若提交的程序运行不正确，则该程序将被退回给参赛队，参赛队可以进行修改后再一次提交该问题。 程序运行不正确是指出现以下4种情况之一： (1)运行出错(run-time error)； (2)运行超时〔time-limit exceeded〕； (3)运行结果错误(wrong answer)； (4)运行结果输出格式错误(presentation error)。 竞赛结束后，参赛各队以解出问题的多少进行排名，若解出问题数相同，按照总用时的长短排名。总用时为每个解决了的问题所用时间之和。一个解决了的问题所用的时间是竞赛开始到提交被接受的时间加上该问题的罚时(每次提交通不过，罚时20分钟)。没有解决的问题不记时。美国英语为竞赛的工作语言。竞赛的所有书面材料(包括试题)将用美国英语写出，区域竞赛中可以使用其它语言。总决赛可以使用的程序设计语言包括PASCAL，C，C++及Java，也可以使用其它语言。具体的操作系统及语言版本各年有所不同。 4)竞赛奖励情况 总决赛前十名的队伍将得到高额奖学金：第一名奖金为12000美元，第二名奖金为 6000美元，第三名奖金为3000美元，第四名至第十名将各得到l500美元。除此之外还将承认北美冠军、欧洲冠军、南太平洋冠军及亚洲冠军。 2.ACM竞赛需要的知识 语言是最重要的基本功 无论侧重于什么方面，只要是通过计算机程序去最终实现的竞赛，语言都是大家要过的第一道关。亚洲赛区的比赛支持的语言包括C/C++与JAVA。首先说说JAVA，众所周知，作为面向对象的王牌语言，JAVA在大型工程的组织与安全性方面有着自己独特的优势，但是对于信息学比赛的具体场合，JAVA则显得不那么合适，它对于输入输出流的操作相比于C++要繁杂很多，更为重要的是JAVA程序的运行速度要比C++慢10倍以上，而竞赛中对于JAVA程序的运行时限却往往得不到同等比例的放宽，这无疑对算法设计提出了更高的要求，是相当 历届自考C++__程序设计试题及答案全国2008年10月自学考试C++程序设计试题 课程代码:04737 一、单项选择题(本大题共20小题，每小题1分，共20分) 1(对C++语言和C语言的兼容性，描述正确的是( A ) A(C++兼容C B(C++部分兼容C D(C兼容C++ 2(在C++中使用流进行输入输出，其中用于屏幕输出的对象是( C ) A(cerr B(cin C(coutD(cfile (cerr:标准错误输出(非缓冲方式);cin:标准输入; clog 标准错误输出(缓冲方式)) 3(对使用关键字new所开辟的动态存储空间，释放时必须使用( C ) A(free B(create C(delete D(realse (如没有使用private关键字定义类的数据成员，则默认为( A ) 4 A(private B(public C(protected D(friend 5(使用值传递方式将实参传给形参，下列说法正确的是( A ) A(形参是实参的备份 B(实参是形参的备份C(形参和实参是同一对象D(形参和实参无联系 6(在函数调用时，如某一默认参数要指明一个特定值，则有( A ) A(其之前所有参数都必须赋值B(其之后所有参数都必须赋值C(其前、后所有参数都必须赋值D(其前、后所有参数都不必赋值 7(设存在函数int max(int，int)返回两参数中较大值，若求22，59，70三者中最大值，下列表达式不正确的是( C ) A(int m = max(22，max(59，70)); B(int m = max(max(22，59)，70);C(int m = max(22，59，70); D(int m = max(59，max(22，70)); 比赛试题 主办方：迅翔计算机协会 【问题描述】 这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数，一般而言有多种方式。例如：给定了6种钱币面值为2、5、10、20、50、100，用来凑15元，可以用5个2元、1个5元，或者3个5元，或者1个5元、1个10元，等等。显然，最少需要2个钱币才能凑成15元。 你的任务就是，给定若干个互不相同的钱币面值，编程计算，最少需要多少个钱币才能凑成某个给出的钱数。 【要求】 【数据输入】输入可以有多个测试用例。每个测试用例的第一行是待凑的钱数值M（1 <= M <= 2000，整数），接着的一行中，第一个整数K（1 <= K <= 10）表示币种个数，随后是K 个互不相同的钱币面值Ki(1 <= Ki <= 1000)。输入M=0时结束。 【数据输出】每个测试用例输出一行，即凑成钱数值M最少需要的钱币个数。如果凑钱失败，输出“Impossible”。你可以假设，每种待凑钱币的数量是无限多的。 【样例输入】 15 6 2 5 10 20 50 100 1 1 2 【样例输出】 2 Impossible 【问题描述】 Felicia 的生日是11月1日（和Kitty是同一天生的哦）。于是Feli请来Kitty一起过生日。Kitty带来了最新款的“Kitty猫”玩具准备送给Feli，不过她说，这份礼物可不是白送的。Feli要帮她一个忙，才能够得到心仪已久的玩具。Kitty说，“Kitty猫”玩具已经卖出了n!个，n<=10^100 *_*，Kitty想知道确切的数字，而不是无聊的“一个数加个感叹号”。Feli 听了大吃一惊。要知道，算出n!是一个无比艰巨的任务。Feli告诉Kitty，就算Feli算出n!，Kitty也看不下去，因为当n=20 时，计算机的长整型已经存不下了（Kitty只能接受1-9之间的数字）。于是Kitty说，你只要告诉我n!最后一位非0的数就可以了。Feli想了想，立刻动手写了个程序算出了正确的答案。现在，请你也试试看！注意哦，AC的男生将会得到一个“Hello Kitty”计算器（可编程，CPU 1THz，Mem 1TMB），AC的女生将会得到一个仿真“Hello Kitty”宠物（善解人意，无须喂养，智商1101，附带写情书功能）。 【要求】 【数据输入】每行一个n，直到输入数据结束 【数据输出】对应输入的n，每行输出一个答案 【样例输入】 1101 【样例输出】 8 备战ACM资料 习题 1． 0-1背包问题 在0 / 1背包问题中，需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。 程序如下： #include <> void readdata(); void search(int); void checkmax(); void printresult(); int c=35, n=10; "); printf("\n"); } printf("\n"); } 6．素数环问题 把从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。 分析：用回溯算法，考察所有可能的排列。 程序如下： #include <> #include <> void search(int); void init(); 表示空格；’X’表示墙。 程序如下： #include <> #include <> void search(int,int); int canplace(int,int); void readdata(); Floodfill 给一个20×20的迷宫和一个起点坐标，用广度优先搜索填充所有的可到达的格子。 提示：参考第2题。 2. 电子老鼠闯迷宫 如下图12×12方格图，找出一条自入口（2，9）到出口（11，8）的最短路 本题给出完整的程序和一组测试数据。状态：老鼠所在的行、列。程序如下： #include<> void readdata(); a[i][j]=0; .... 注：测试数据可在运行时粘贴上去（点击窗口最左上角按钮，在菜单中选则“编辑”/“粘贴”即可）。 想一想：此程序都存在哪些问题，如果openlen太小程序会不会出错，加入代码使程序能自动报出此类错误。 3.跳马 给一个200×200的棋盘，问国际象棋的马从给定的起点到给定的终点最少需要几步。 Sample Input 0 0 1 1 Sample output 4 状态：马所在的行、列。 程序如下： #include<> void readdata(); 独轮车 The 35th ACM-ICPC Asia Regional Contest (Hangzhou) Contest Section October 24, 2010 Sponsored by IBM & Alibaba Zhejiang Sci-Tech University This problem set should contain 10 problems on numbered 24 pages. Please inform a runner immediately if something is missing from your problem set. Problem A. Naughty fairies Description Once upon a time, there lived a kind of fairy in the world. Those fairies could hear the voice of fruit trees, and helped people with a harvest. But people did n’t know that fruits are also those fairies’ favorite food. After the fairies ate people’s fruits, they always did something to cover it up. One day a little fairy named Lily flew into an orchard and found a large peach tree. Hungry as Lily was, she started eating without thinking until her stomach was full. In the fairy world, when a fairy ate the fruits in a fruit tree, sometimes the fruit tree would feel honored and bore more fruits immediately. That’s why sometimes the number of fruits in a tree got increased after a fairy ate fruits of that tree. But the fairies didn’t want people to find out weird things such as fruits become more or less suddenly. Lily decided to use a magic spell so that the orchard owner couldn’t find the change of the number of p eaches. Suppose there were N peaches on a tree originally and there were M peaches left after Lily was full. M may be greater than, less than or equal to N. All M peaches were visible at first, and Lily wanted to make an illusion so that exactly N peaches are visible. Lily can do 3 kinds of spell to change the total visible number of peaches: 1) “PAPADOLA”：This spell would increase the number of visible peaches by one. 2) “EXPETO POTRONUM”：This spell would double the number of visible peaches. 3) “SAVIDA LOHA”:This spell would decrease the number of visible peaches by one. Each spell would take one minute and Lily wanted to finish as fast as possible. Now please tell Lily the least time she needs to change the number of visible peaches to N. Input There are several test cases, ended by “0 0”. For each test case, there are only one line containing two numbers separated by a blank, N and M, the original numbers of peaches and the numbers of peaches left(02008年ACM大学生程序设计竞赛题
历届百度之星程序设计大赛题目
桂林电子科技大学ACM程序设计校内竞赛试题
ACM程序设计大赛(校级)
四川理工学院2012年ACM程序设计赛试题
ACM入门之新手入门
历届自考C++__程序设计试题及答案
acm编程比赛题
ACM程序设计竞赛例题[1]
ACM比赛试题
相关主题
文本预览