棋盘覆盖问题
问题描述:在一个2k×2k 个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。
代码:#include<stdio.h>
int tile=0//整型变量,记录L型骨牌的数量 int Matrix[100][100]//定义数据结构
void ChessBoard(int tr,int tc,int dr,int dc,int size)
{//tr和tc分别是棋盘左上角方格的行号、列号;dr和dc分别是特殊方格的行号、列号 if(size==1) return int t=tile++//L型骨牌号,初值为0 int s=size/2//分割棋盘
if(dr<tr+s&&dc<tc+s)//用L型骨牌号覆盖左上角子棋盘 ChessBoard(tr,tc,dr,dc,s)// 特殊方格在此棋盘中 else
{//特殊方格不在此棋盘中用 ,t号L型骨牌覆盖右下角 Matrix[tr+s-1][tc+s-1]=t// 覆盖本子棋盘中的其余方格 ChessBoard(tr,tc,tr+s-1,tc+s-1,s) }
if(dr<tr+s&&dc>=tc+s)//用L型骨牌号覆盖右上角子棋盘 ChessBoard(tr,tc,dr,dc,s)// 特殊方格在此棋盘中 else
{//特殊方格不在此棋盘中用 ,t号L型骨牌覆盖左下角 Matrix[tr+s-1][tc+s]=t// 覆盖本子棋盘中的其余方格 ChessBoard(tr,tc+s,tr+s-1,tc+s,s) }
if(dr>=tr+s&&dc<tc+s)//用L型骨牌号覆盖左下角子棋盘 ChessBoard(tr+s,tc,dr,dc,s)// 特殊方格在此棋盘中 else
{//特殊方格不在此棋盘中用 ,t号L型骨牌覆盖右上角 Matrix[tr+s][tc+s-1]=t// 覆盖本子棋盘中的其余方格 ChessBoard(tr+s,tc,tr+s,tc+s-1,s) }
if(dr>=tr+s&&dc>=tc+s)//用L型骨牌号覆盖右上角子棋盘 ChessBoard(tr+s,tc+s,dr,dc,s)// 特殊方格在此棋盘中 else
{//特殊方格不在此棋盘中用 ,t号L型骨牌覆盖左上角 Matrix[tr+s][tc+s]=t// 覆盖本子棋盘中的其余方格 ChessBoard(tr+s,tc+s,tr+s,tc+s,s) }
}
int main() { int size,r,c,row,col //memset(Matrix,0,sizeof(Matrix)) for(int i=0i<=100i++)//初始化 为零 { for(int j=0j<=100j++) { Matrix[i][j]=0 } } scanf("%d",&size)//输入棋盘大小 scanf("%d%d",&row,&col)//输入特殊方格位置 ChessBoard(0,0,row,col,size) for (r = 0r <sizer++)//输出棋盘覆盖结果 { for (c = 0c <sizec++) { printf("%2d ",Matrix[r][c]) } printf("\n") } return 0 }
输出结果:
通过字符控制是很难做出来的,而且毫不值得,你基本需要控制光标到特定位置进行重绘,这需要操作系统支持,而这种支持似乎越来越少了,已经没有啥API可以让你直接做了。
这种东西建议学习windows编程,然后用图形界面做。
第十三届全国青少年信息学奥林匹克联赛初赛试题( 普及组 Pascal 语言 二小时完成)
●● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 ●●
一、单项选择题(共20题,每题1.5分,共计30分。每题有且仅有一个正确答案。)
1.在以下各项中,( )不是CPU的组成部分。
A.控制器 B.运算器C.寄存器 D.主板
2.在关系数据库中,存放在数据库中的数据的逻辑结构以( )为主。
A.二叉树 B.多叉树C.哈希表 D.二维表
3.在下列各项中,只有( )不是计算机存储容量的常用单位。
A.ByteB.KBC.UBD.TB
4.ASCII码的含义是( )。
A.二→十进制转换码B.美国信息交换标准代码
C.数字的二进制编码D.计算机可处理字符的唯一编码
5.一个完整的计算机系统应包括( )。
A.系统硬件和系统软件 B.硬件系统和软件系统
C.主机和外部设备 D.主机、键盘、显示器和辅助存储器
6.IT的含义是( )。
A.通信技术B.信息技术C.网络技术D.信息学
7.LAN的含义是( )。
A.因特网 B.局域网 C.广域网 D.城域网
8.冗余数据是指可以由其它数据导出的数据。例如,数据库中已存放了学生的数学、语文和英语的三科成绩,如果还存放三科成绩的总分,则总分就可以看作冗余数据。冗余数据往往会造成数据的不一致。例如,上面4个数据如果都是输入的,由于操作错误使总分不等于三科成绩之和,就会产生矛盾。下面关于冗余数据的说法中,正确的是( )。
A.应该在数据库中消除一切冗余数据
B.用高级语言编写的数据处理系统,通常比用关系数据库编写的系统更容易消除冗余数据
C.为了提高查询效率,在数据库中可以保留一些冗余数据,但更新时要做相容性检验
D.做相容性检验会降低效率,可以不理睬数据库中的冗余数据
9.在下列各软件,不属于NOIP竞赛(复赛)推荐使用的语言环境有( )。
A.gccB.g++C.Turbo C D.Free Pascal
10.以下断电后仍能保存数据的有( )。
A.硬盘 B.高速缓存 C.显存D.RAM
11.在下列关于计算机语言的说法中,正确的有( )。
A.高级语言比汇编语言更高级,是因为它的程序的运行效率更高
B.随着Pascal、C等高级语言的出现,机器语言和汇编语言已经退出了历史舞台
C.高级语言比汇编语言程序更容易从一种计算机上移植到另一种计算机上
D.C是一种面向对象的高级计算机语言
12.近20年来,许多计算机专家都大力推崇递归算法,认为它是解决较复杂问题的强有力的工具。在下列关于递归算法的说法中,正确的是( )。
A.在1977年前后形成标准的计算机高级语言“FORTRAN77”禁止在程序使用递归,原因之一是该方法可能会占用更多的内存空间
B.和非递归算法相比,解决同一个问题,递归算法一般运行得更快一些
C.对于较复杂的问题,用递归方式编程一般比非递归方式更难一些
D.对于已经定义好的标准数学函数 sin(x),应用程序中的语句“y=sin(sin(x))”就是一种递归调用
13.一个无法靠自身的控制终止的循环成为“死循环”,例如,在C语言程序中,语句“while(1) printf(“*”)”就是一个死循环,运行时它将无休止地打印*号。下面关于死循环的说法中,只有( )是正确的。
A.不存在一种算法,对任何一个程序及相应的输入数据,都可以判断是否会出现死循环,因而,任何编译系统都不做死循环检查
B.有些编译系统可以检测出死循环
C.死循环属于语法错误,既然编译系统能检查各种语法错误,当然也应该能检查出死循环
D.死循环与多进程中出现的“死锁”差不多,而死锁是可以检测的,因而,死循环也可以检测的
14.在Pascal语言中,表达式 (23 or 2 xor 5)的值是( )。
A.18B.1C.23 D.32
15.在Pascal语言中,判断整数a等于0或b等于0或c等于0的正确的条件表达式是( )。
A.not ((a<>0) or (b<>0) or (c<>0))
B.not ((a<>0) and (b<>0) and (c<>0))
C.not ((a=0) and (b=0)) or (c<>0)
D.(a=0) and (b=0) and (c=0)
16.地面上有标号为A、B、C的三根柱,在A柱上放有10个直径相同中间有孔的圆盘,从上到下依次编号为1,2,3……,将A柱上的部分盘子经过B柱移入C柱,也可以在B柱上暂存。如果B柱上的操作记录为“进、进、出、进、进、出、出、进、进、出、进、出、出”。那么,在C柱上,从下到上的编号为( )。
A.2 4 3 6 5 7B.2 4 1 2 5 7 C.2 4 3 1 7 6 D.2 4 3 6 7 5
17.与十进制数1770对应的八进制数是( )。
A.3350B.3351 C.3352 D.3540
18.设A=B=True,C=D=False,一下逻辑运算表达式值为假的有( )。
A.(「A∧B)∨(C∧D∨A) B.「(((A∧B)∨C)∧D)
C.A∧(B∨C∨D)∨D D.(A∧(D∨C))∧B
19.(2070)16 + (34)8 的结果是( )。
A.(8332)10 B.(208A)16 C.(100000000110)2D.(20212)8
20.已知7个节点的二叉树的先根遍历是1 2 4 5 6 3 7(数字为节点的编号,以下同),中根遍历是4 2 6 5 1 7 3,则该二叉树的后根遍历是( )。
A.4 6 5 2 7 3 1 B.4 6 5 2 1 3 7C.4 2 3 1 5 4 7D.4 6 5 3 1 7 2
二、问题求解(共2题,每题5分,共计10分)。
1、(子集划分)将n个数(1,2,…,n)划分成r个子集。每个数都恰好属于一个子集,任何两个不同的子集没有共同的数,也没有空集。将不同划分方法的总数记为S(n,r)。例如,S(4,2)=7,这7种不同的划分方法依次为{(1),(234)},{(2),(134)},{(3),(124)},{(4),(123)},{(12),(34)},{(13),(24)},{(14),(23)}。当n=6,r=3时,S(6,3)=______________。
(提示:先固定一个数,对于其余的5个数考虑S(5,3)与S(5,2),再分这两种情况对原固定的数进行分析。)
2、(最短路线)某城市的街道是一个很规整的矩形网络(见下图),有7条南北向的纵街,5条东西向的横街。现要从西南角的A走到东北角的B,最短的走法共有多少种?___________
(图画不了)
三、阅读程序写结果(共4题,每题8分,共计32分。)
1、program j301
vari,a,b,c,x,y:integer
p:array[0..4] of integer
begin
y:=20
for i:=0 to 4 do read(p)
readln
a:=(p[0]+p[1])+(p[2]+p[3]+p[4]) div 7
b:=p[0]+p[1] div ((p[2]+p[3]) div p[4])
c:=p[0]*p[1] div p[2]
x:=a+b-p[(p[3]+3) mod 4]
if (x>10)
then y:=y+(b*100-a) div (p[p[4] mod 3]*5)
else
y:=y+20+(b*100-c) div (p[p[4] mod 3]*5)
writeln(x,',',y)
end.
{注:本例中,给定的输入数据可以避免分母为0或数组元素下表越界。}
输入:6 6 5 5 3 输出:______________________
2、program j302
vara,b:integer
varx,y:^integer
procedure fun(a,b:integer)
vark:integer
begin k:=aa:=bb:=kend
begin
a:=3b:=6
x:=@ay:=@b
fun(x^,y^)
writeln(a,',',b)
end.
输出:_______________________________
3、program j303
vara1:array[1..50] of integer
vari,j,t,t2,n,n2:integer
begin
n:=50
for i:=1 to n do a1:=0
n2:=round(sqrt(n))
for i:=2 to n2 do
if (a1=0) then
begin
t2:=n div i
for j:=2 to t2 do a1[i*j]:=1
end
t:=0
for i:=2 to n do
if (a1=0) then
begin
write(i:4)inc(t)
if (t mod 10=0) then writeln
end
writeln
end.
输出:_____________________________________________
_____________________________________________
4、Program j304
Type str1=string[100]
Str2=string[200]
Var
S1:str1s2:str2
Function isalpha(c:char):Boolean
Var i:integer
Begin
i:=ord(c)
if ((i>=65) and (i<=90)) or ((i>=97) and (i<=122)) then
isalpha:=true
else isalpha:=false
end
function isdigit(c:char):Boolean
var i:integer
begin
i:=ord(c) if (i>=48) and (i<=57) then isdigit:=true
else isdigit:=false
end
procedure expand(s1:str1var s2:str2)
var i,j:integera,b,c:char
begin
j:=1c:=char(1)i:=0
while (i<=ord(s1[0])) do
begin inc(i)c:=s1
if c='-' then begin {1}
a:=s1[i-1]b:=s1[i+1]
if (isalpha(a) and isalpha(b)) or (isdigit(a) and isdigit(b)) then begin
dec(j)
while (ord(upcase(a))<ord(upcase(s1[i+1]))) do
begin
s2[j]:=ainc(j)inc(a)end
end
else
begin s2[j]:=cinc(j)end
end{1}
else begin s2[j]:=cinc(j)endends2[0]:=char(j-2)end
begin readln(s1)expand(s1,s2)writeln(s2)
end.
输入:wer2345d-h454-82qqq 输出:__________________________
四、完善程序(前4空,每空2.5分,后6空,每空3分,共28分)。
1、(求字符的逆序)下面的程序的功能是输入若干行字符串,每输入一行,就按逆序输出该行,最后键入-1终止程序。
请将程序补充完整。
Program j401
type str1=string[100]
var line:str1kz:integer
procedure reverse(var s:str1)
var I,j:integert:char
begin
i:=1j:=length(s)
while (i<j) do begin
t:=ss:=s[j]s[j]:=t
end
end
begin
writeln(‘continue? -1 for end.’)
readln(kz)
while ( )do
begin
readln(line)
writeln(line)
writeln(‘continue? -1 for end.’)
readln(kz)
end
end.
2233
2-113
4115
4455
2、(棋盘覆盖问题)在一个2k×2 k个方格组成的棋盘中恰有一个方格与其它方格不同(图中标记为-1的方格),称之为特殊方格。现用L型(占3个小方格)纸片覆盖棋盘上除特殊方格的所有部分,各纸片不得重叠,于是,用到的纸片数恰好是(4 k-1)/3。在下表给出的一个覆盖方案中,k=2,相同的3各数字构成一个纸片。
下面给出的程序使用分治法设计的,将棋盘一分为四,依次处理左上角、右上角、左下角、右下角,递归进行。请将程序补充完整。
(图画不了...郁闷)
Program j402
type arr1=array[1..65] of integer
arr2=array[1..65] of arr1
var board:arr2tile:integersize,dr,dc:integer
procedure chessboard(tr,tc:integerdr,dc:integervar size:integer)
var t,s:integer
begin
if (size=1) then
t:=tileinc(tile)
s:=size div 2
if then chessboard(tr,tc,dr,dc,s) else begin
board[tr+s-1]:=t
end
if (dr<tr+s) and (dc>=tc+s) then chessboard(tr,tc+s,dr,dc,s)
else begin board[tr+s-1][tc+s]:=t
end
if (dr>=tr+s) and (dc<tc+s) then chessboard(tr+s,tc+s,dr,dc,s) else begin
board[tr+s][tc+s]:=t
end
if (dr>=tr+s) and (dc>=tc+s) then chessboard(tr+s,tc+s,dr,dc,s)
else begin board[tr+s][tc+s]:=t
end
end
procedure prt1(n:integer)
var I,j:integer
begin
for I:=1 to n do begin
for j:=1 to n do write(board[j]:3)
writeln
end
end
begin
writeln(‘input size(4/8/16/64):’)
readln(size)writeln(‘input the position of special block(x,y):’)
readln(dr,dc) board[dr][dc]:=-1
tile:=1 chessboard(1,1,dr,dc,size)prt1(size)
end.
NOIP2007年普及组(Pascal语言)参考答案与评分标准
一、单项选择题:(每题1.5分)
题号12345678910
答案DDCBBBBCCA
题号11121314151617181920
答案C A A A B D C D A A
二、问题求解:(每题 5分)
1.90 2.210
三、阅读程序写结果
1. 15, 46(对1个数给4分,无逗号扣1分)
2. 3, 6
3. 2 3 5 7 11 13 17 19 23 29
31 37 41 43 47
4. wer2345defgh45456782qqq
四、完善程序(前4空(①--④),每空2.5分,后6空(⑤--⑩),每空3分)
1.
① inc(i) 或i:=i+1
② dec(j) 或 j:=j-1
③ kz<>-1
④ reverse(line)
2.
⑤ exit
⑥ (dr<tr+s)and(dc<tc+s)
⑦ chessboard(tr,tc,tr+s-1,tc+s-1,s)
⑧ chessboard(tr,tc+s,tr+s-1,tc+s,s)
⑨ chessboard(tr+s,tc,tr+s,tc+s-1,s)
⑩ chessboard(tr+s,tc+s,tr+s,tc+s,s)
貌似我考过了 不难
希望对你能有所帮助。