tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

NOI1992试题


NOI92 试题
第一题:文章排版
把一段文章按要求排版文章的输入方式为: 由键盘输入一个以回车符结束的文章 (最大长度 2000 个字符)。 排版时以单词为基本单位。单词由不含空格的任意字符组成,是长度小于 20 个字符的串。 空格符是分隔单词的唯一字符,在输入时连续的空格符在处理时应 首先化简为单个空格。 在排版前应先输入排版后每行的字符数 N,排版后将整

理好的文章按行输出。 输出时应保证不将一个完整的单词截断,并且要求输出的总行数最小。 将每个不足 N 个字符的行用空格符补足,填充空格符的方式有以下 3 种: 1.将填充的空格符置于每行的末尾,并要求每行的起始为单词。 2.将填充的空格符置于每行的起始,并要求每行的末尾为单词。 3.将填充的空格符尽可能平均分配在每行中,并保证每行的起始和末尾均为单 词。 试编程对输入的一段文阐分别完成上述三个要求。

第二题:逻辑表达式
由英文字符和符号和符号~、*、+、()组成逻辑表达式,英文字母表示变 量,变量有两种可能的取值,False 或 True;~、*、+。括号()可改变表达 式的运算次序,且可以嵌套。 逻辑“非”运算的公式如下表: A TRUE FALSE ~A FALSE TRUE

逻辑“与”和逻辑“或”的运算公式如下表: A FALSE B FALSE A*B FLASE A+B FLASE

FALSE TRUE FLASE TRUE TRUE FALSE FALSE TRUE TRUE TRUE TRUE TRUE 两个逻辑表达式等价,当且仅当两个公式中相同名字的变量取任何一种值时两 个公式的值都相同。如: A*(B+C) 与 A*B+A*C 等价 A*(~A+B) 与 A*B 等价 (~A+A)*BC 与 B+C 等价 A*B+A*~B 与 A 等价 而: A+B 与 A*B 不等价 A*B+~C 与 A*E+~F 不等价 现要求你编程解决下列问题: 任务 1 用键盘输入一个逻辑表达式,判断这个表达式的合法性; 任务 2 将键盘输入的表达式化简,化简的表达式为 a1*a2*…*aN+b1**b2*…*bM+…+x1*x2*…*xL 其中 ai、bj、…xk(i=1,2,…n; j=1,2,…m; k=1,2,…1)表示一个变量或一个变量 的逻辑非; 任务 3 将任务 2 中的化简的表达式化为最简形式。所谓最简有如下两个条件: (1)表达式中的"+"号最少; (2)满足的条件下"+"号最少。

第三题:无根树
无根树与通常所说的树(有根树)很相似,它包括有节点和枝,但不含有根。 无根树节点间只有相邻关系,而不存在父子节点的关系。如图 3.3-1 所示,是 一棵有 7 个节点的无根树; 以图 3.3-1 的 A 为根节点得到图 3.3-2 所示的有根 树,以图 3.3-1 的 B 为根节得到图 3.3-3 所示的有根树,但从无根树的角度看, 图 3.3-1、图 3.3-2、图 3.3-3 是结构相同的无根树,同时无根树的结构与节点 的名称无关。

有根树可以以字符串的形式表示,其递归表示方法为: 根节点(子树 1 子树 2 子树 3……) 如图 3.3-2,图 3.3-3 的有根树可分别表示为 A(B(CF(EGD)))和 B(ACF(EGD)), 需要注意的是, 由于子树的表示顺序可以不同,所以一棵有根树可以有多种表示 方法,如图 3.3-3 由可表示为 B(F(EGD)CA)和 B(ACF(DEG))等。 表示无根树时,可以以它的任一节点为根节点,将其看作有根树从而可以利用 有根树的字符串表示形式来表示无根树。 任务 1 由键盘读入一个字符串表示的无根树,无根树的各节点的名称用互不 相同的大写英文字母表示。 则用户输入一个节点的名称,程序应能够输出一种以 该节点为根节点的字符串形式。 程序输出无根树的子符串形式时,各个节点的名称无关紧要,所有节点都以 P 表示,以后的各种输出了也采用这种方式。 例如: 用户输入无根树的字符串形式:A(B(CD(EF))) 指定的根节点为:D 输出 P(P(PP)PP)P(PP(PP)P)P(PPP(PP)) 任务 2 输入两个串表示的无根树,判断其结构是否一样。注意与节点名称无关, 只考虑结构。 任务 3 输入无根树的总枝 N(1≤N≤11),输出所有枝数为 N 的互不相同的无根 树,并记录总数。以字符串形式输出:例如,N=5 时,共有 6 种不同结构的无 根树。

第四题:电子锁

某机要部门安装了电子锁。 M 工作人员每人发一张磁卡, 卡上有开锁的密码特征。 为了确保安全,规定至少要有 N 个人同时使用各自的磁卡才能将锁打开。 现在需要你计算一下, 电子锁上至少要有多少种特征,每个人的磁卡上至少有几 个特征。 如果特征的编号以小写字符表示, 将每个人的磁卡的特征编号打印出来。 要求输出的电子锁的总特征数量最少。 为了使问题简单,M 与 N 的上下限为 3≤M≤7,1≤N≤4 M 与 N 由键盘输入,工作人员的编号用 1#,2#,…等。 例如 M=3,N=2,则电子锁上要有三种特征。个人的磁卡上要有两种特征。
C(m,n-1)=m!/(m-n+1)!/(n-1)! C(m-1,n-1)=(m-1)!/(m-n)!/(n-1)!=C(m,n-1)/m*(m-n+1)


推荐相关:

NOI1992试题

NOI1992试题_学科竞赛_高中教育_教育专区。NOI92 试题第一题:文章排版把一段文章按要求排版文章的输入方式为: 由键盘输入一个以回车符结束的文章 (最大长度 2000...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com