ACM基础训练题

《ACM基础训练题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、【题目1】N皇后问题（八皇后问题的扩展）【题目2】排球队员站位问题【题目3】把自然数N分解为若干个自然数之和。【题口4】把自然数N分解为若干个自然数之积。【题戸5】马的遍历问题。【题目6】加法分式分解【题目7］地图着色问题【题目8］在n和的正方形中放置长为2,宽为1的长条块，【题口9］找迷宫的垠短路径。（广度优先搜索算法）【题廿10］火车调度问题【题目11】农夫过河【题目12】七段数码管问题。【题目13］把1-8这8个数放入下图8个格中，要求相邻的格（横，竖，对角线）上填的数不连续.【题口14】在4X

2、4的棋盘上放置8个棋，要求每一行，每一列上只能放置2个.【题廿15］迷宫问题.求迷宫的路径.（深度优先搜索法）【题目16］一笔画问题【题目17］城市遍历问题.【题目18］棋子移动问题【题口19】求集合元素问题（l,2x+l,3X+l类）【题目】N皇后问题(含八皇后问题的扩展，规则同八皇后)：在N鏡的棋盘上,放置N个皇后，要求每一横行每一列，每一对角线上均只能放置一个皇后，问可能的方案及方案数。constmax=8;vari,j:integer;a:array[1..max]of0..max;｛放皇后数

3、组｝b:array[2..2*max]ofboolean;｛/对角线标志数组｝c:array[-(max~l)..max-1]ofboolean;｛对角线标志数组｝col:array[1..max]ofboolean;｛列标志数组｝total:integer;｛统计总数｝procedureoutput;｛输岀｝vari:integer;beginwrite(*No.':4,',total+1:2,';fori:=1tomaxdowritc(a[i]:3);writc(，，)；if(total+1)m

4、od2=0thenwritein;inc(total);end;functionok(i,dcp:integer):boolean;｛判断第dcp行第i列可放否｝beginok:二false;if(b[i+dep]二true)and(c[dep-i]二true)｛and(a[dep]=0)｝and(col[i]=true)thenok:=trueend;proceduretry(dep:integer);vari,j:integer;be百infori:=1tomaxdo｛每一行均有max种放法｝if

5、ok(i,dep)thenbegina[dep]:=i;b[i+dep]:二false;｛/对角线已放标志｝c[dep-i]:二false;｛对角线已放标志｝col[i]:二false;｛列已放标志｝ifdep=maxthenoutputelsetry(dep+1);｛递归下一层｝a[dep]:二0;｛取走皇后，冋溯｝b[i+dep]:二true;｛恢复标志数组｝c[dcp-i]:二true;col[i]rue;end;end;beginfori:=1tomaxdobegina[i]:=0;col[

6、i]:=true;end;fori:=2to2*maxdob[i]:=true;fori(max-1)tomax~ldoc[i]:二true;total:二0;try(1);writelnCtotal,total);end.【测试数据】n=8八皇后问题No.LllJNo.[13]No.[15]l5863724l746825324683l752574l8632683l4752758l4633l758246JuuTJu135797468253uuuu-IJ-IJuu24680246・A1A_亠1£ILoN

7、XOXONo8358711736612871No.[17]35841726No.[18]36258174No.[19]36271485No.[20]36275184No.[21]36418572No.[22]36428571No.[23]36814752No.[24]36815724No.[25]36824175No.[26]37285146No.[27]37286415No.[28]38471625No.[29]41582736No.[30]41586372No.[31]42586137No.[32

8、]42736815No.[33]42736851No.[34]42751863No.[35]42857136No.[36]42861357No.[37]46152837No.[38]46827135No.[39]46831752No.[40]47185263No.[41]47382516No.[42]47526138No.[43]47531682No.[44]48136275No.[45]48157263No.[46]48531726No.[47]514