没有合适的资源?快使用搜索试试~ 我知道了~
acm基础训练题(动态规划等。。。。。。)
需积分: 0 4 下载量 12 浏览量
2009-05-10
22:00:09
上传
评论
收藏 166KB DOC 举报
温馨提示
试读
29页
N皇后问题;排球队员站位问题;把自然数N分解为若干个自然数之和;把自然数N分解为若干个自然数之积;马的遍历问题;加法分式分解 等。。。。。。
资源详情
资源评论
资源推荐
【题目 1】N
皇后问题 (八皇后问题的扩展)
【题目 2】排球队员站位问题
【题目 3】把自然数N分解为若干个自然数之和。
【题目 4】把自然数N分解为若干个自然数之积。
【题目 5】马的遍历问题。
【题目 6】加法分式分解
【题目 7】地图着色问题
【题目 8】在
n*n
的正方形中放置长为
2, 宽为
1
的长条块 ,
【题目 9】找迷宫的最短路径。(广度优先搜索算法)
【题目 10】火车调度问题
【题目 11】农夫过河
【题目 12】七段数码管问题。
【题目 13】把
1-8
这
8
个数放入下图
8
个格中 , 要求相邻的格 ( 横 , 竖 , 对角线 ) 上填的数不连续 .
【题目 14】在
4×4
的棋盘上放置
8
个棋 , 要求每一行 , 每一列上只能放置
2
个 .
【题目 15】迷宫问题 . 求迷宫的路径 .(深度优先搜索法)
【题目 16】一笔画问题
【题目 17】城市遍历问题.
【题目 18】棋子移动问题
【题目 19】求集合元素问题(1,2x+1,3X+1 类)
=====================================================
===========================
=====================================================
===========================
【题目】N 皇后问题(含八皇后问题的扩展,规则同八皇后):在 N*N 的棋盘上,放置 N 个皇后,要求
每一横行
每一列,每一对角线上均只能放置一个皇后,问可能的方案及方案数。
const max=8;
var i,j:integer;
a:array[1..max] of 0..max; {放皇后数组}
b:array[2..2*max] of boolean; {/对角线标志数组}
c:array[-(max-1)..max-1] of boolean; {\对角线标志数组}
col:array[1..max] of boolean; {列标志数组}
total:integer; {统计总数}
procedure output; {输出}
var i:integer;
begin
write('No.':4,'[',total+1:2,']');
for i:=1 to max do write(a[i]:3);write(' ');
if (total+1) mod 2 =0 then writeln; inc(total);
end;
function ok(i,dep:integer):boolean; {判断第 dep 行第 i 列可放否}
begin
ok:=false;
if ( b[i+dep]=true) and ( c[dep-i]=true) {and (a[dep]=0)} and
(col[i]=true) then ok:=true
end;
procedure try(dep:integer);
var i,j:integer;
begin
for i:=1 to max do {每一行均有 max 种放法}
if ok(i,dep) then begin
a[dep]:=i;
b[i+dep]:=false; {/对角线已放标志}
c[dep-i]:=false; {\对角线已放标志}
col[i]:=false; {列已放标志}
if dep=max then output
else try(dep+1); {递归下一层}
a[dep]:=0; {取走皇后,回溯}
b[i+dep]:=true; {恢复标志数组}
c[dep-i]:=true;
col[i]:=true;
end;
end;
begin
for i:=1 to max do begin a[i]:=0;col[i]:=true;end;
for i:=2 to 2*max do b[i]:=true;
for i:=-(max-1) to max-1 do c[i]:=true;
total:=0;
try(1);
writeln('total:',total);
end.
【测试数据】
n=8 八皇后问题
No.[ 1] 1 5 8 6 3 7 2 4 No.[ 2] 1 6 8 3 7 4 2 5
No.[ 3] 1 7 4 6 8 2 5 3 No.[ 4] 1 7 5 8 2 4 6 3
No.[ 5] 2 4 6 8 3 1 7 5 No.[ 6] 2 5 7 1 3 8 6 4
No.[ 7] 2 5 7 4 1 8 6 3 No.[ 8] 2 6 1 7 4 8 3 5
No.[ 9] 2 6 8 3 1 4 7 5 No.[10] 2 7 3 6 8 5 1 4
No.[11] 2 7 5 8 1 4 6 3 No.[12] 2 8 6 1 3 5 7 4
No.[13] 3 1 7 5 8 2 4 6 No.[14] 3 5 2 8 1 7 4 6
No.[15] 3 5 2 8 6 4 7 1 No.[16] 3 5 7 1 4 2 8 6
No.[17] 3 5 8 4 1 7 2 6 No.[18] 3 6 2 5 8 1 7 4
No.[19] 3 6 2 7 1 4 8 5 No.[20] 3 6 2 7 5 1 8 4
No.[21] 3 6 4 1 8 5 7 2 No.[22] 3 6 4 2 8 5 7 1
No.[23] 3 6 8 1 4 7 5 2 No.[24] 3 6 8 1 5 7 2 4
No.[25] 3 6 8 2 4 1 7 5 No.[26] 3 7 2 8 5 1 4 6
No.[27] 3 7 2 8 6 4 1 5 No.[28] 3 8 4 7 1 6 2 5
No.[29] 4 1 5 8 2 7 3 6 No.[30] 4 1 5 8 6 3 7 2
No.[31] 4 2 5 8 6 1 3 7 No.[32] 4 2 7 3 6 8 1 5
No.[33] 4 2 7 3 6 8 5 1 No.[34] 4 2 7 5 1 8 6 3
No.[35] 4 2 8 5 7 1 3 6 No.[36] 4 2 8 6 1 3 5 7
No.[37] 4 6 1 5 2 8 3 7 No.[38] 4 6 8 2 7 1 3 5
No.[39] 4 6 8 3 1 7 5 2 No.[40] 4 7 1 8 5 2 6 3
No.[41] 4 7 3 8 2 5 1 6 No.[42] 4 7 5 2 6 1 3 8
No.[43] 4 7 5 3 1 6 8 2 No.[44] 4 8 1 3 6 2 7 5
No.[45] 4 8 1 5 7 2 6 3 No.[46] 4 8 5 3 1 7 2 6
No.[47] 5 1 4 6 8 2 7 3 No.[48] 5 1 8 4 2 7 3 6
No.[49] 5 1 8 6 3 7 2 4 No.[50] 5 2 4 6 8 3 1 7
No.[51] 5 2 4 7 3 8 6 1 No.[52] 5 2 6 1 7 4 8 3
No.[53] 5 2 8 1 4 7 3 6 No.[54] 5 3 1 6 8 2 4 7
No.[55] 5 3 1 7 2 8 6 4 No.[56] 5 3 8 4 7 1 6 2
No.[57] 5 7 1 3 8 6 4 2 No.[58] 5 7 1 4 2 8 6 3
No.[59] 5 7 2 4 8 1 3 6 No.[60] 5 7 2 6 3 1 4 8
No.[61] 5 7 2 6 3 1 8 4 No.[62] 5 7 4 1 3 8 6 2
No.[63] 5 8 4 1 3 6 2 7 No.[64] 5 8 4 1 7 2 6 3
No.[65] 6 1 5 2 8 3 7 4 No.[66] 6 2 7 1 3 5 8 4
No.[67] 6 2 7 1 4 8 5 3 No.[68] 6 3 1 7 5 8 2 4
No.[69] 6 3 1 8 4 2 7 5 No.[70] 6 3 1 8 5 2 4 7
No.[71] 6 3 5 7 1 4 2 8 No.[72] 6 3 5 8 1 4 2 7
No.[73] 6 3 7 2 4 8 1 5 No.[74] 6 3 7 2 8 5 1 4
No.[75] 6 3 7 4 1 8 2 5 No.[76] 6 4 1 5 8 2 7 3
No.[77] 6 4 2 8 5 7 1 3 No.[78] 6 4 7 1 3 5 2 8
No.[79] 6 4 7 1 8 2 5 3 No.[80] 6 8 2 4 1 7 5 3
No.[81] 7 1 3 8 6 4 2 5 No.[82] 7 2 4 1 8 5 3 6
No.[83] 7 2 6 3 1 4 8 5 No.[84] 7 3 1 6 8 5 2 4
No.[85] 7 3 8 2 5 1 6 4 No.[86] 7 4 2 5 8 1 3 6
No.[87] 7 4 2 8 6 1 3 5 No.[88] 7 5 3 1 6 8 2 4
No.[89] 8 2 4 1 7 5 3 6 No.[90] 8 2 5 3 1 7 4 6
No.[91] 8 3 1 6 2 5 7 4 No.[92] 8 4 1 3 6 2 7 5
total:92
对于 N 皇后:
┏━━━┯━━┯━━┯━━┯━━┯━━┯━━┯━━┓
┃皇后 N│ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ 10 ┃
┠───┼──┼──┼──┼──┼──┼──┼──┨
┃方案数│ 2 │ 10 │ 4 │ 40 │ 92 │352 │724 ┃
┗━━━┷━━┷━━┷━━┷━━┷━━┷━━┷━━┛
【题目】排球队员站位问题
┏━━━━━━━━┓图为排球场的平面图,其中一、二、三、四、五、六为位置编号,
┃ ┃二、三、四号位置为前排,一、六、五号位为后排。某队比赛时,
┃ ┃一、四号位放主攻手,二、五号位放二传手,三、六号位放副攻
┠──┬──┬──┨手。队员所穿球衣分别为1,2,3,4,5,6号,但每个队
┃ 四 │ 三 │ 二 ┃员的球衣都与他们的站位号不同。已知1号、6号队员不在后排,
┠──┼──┼──┨2号、3号队员不是二传手,3号、4号队员不在同一排,5号、
┃ 五 │ 六 │ 一 ┃6号队员不是副攻手。
┗━━┷━━┷━━┛ 编程求每个队员的站位情况。
【算法分析】本题可用一般的穷举法得出答案。也可用回溯法。以下为回溯解法。
【参考程序】
type sset=set of 1..6;
var a:array[1..6]of 1..6;
d:array[1..6]of sset;
i:integer;
procedure output; {输出}
begin
if not( (a[3]in [2,3,4])= (a[4] in[2,3,4])) then
begin { 3,4 号队员不在同一排 }
write('number:');for i:=1 to 6 do write(i:8);writeln;
write('weizhi:');for i:=1 to 6 do write(a[i]:8);writeln;
end;
end;
procedure try(i:integer;s:sset); {递归过程 i:第 i 个人,s:哪些位置已安排人了}
var
j,k:integer;
begin
for j:=1 to 6 do begin {每个人都有可能站 1-6 这 6 个位置}
if (j in d[i]) and not(j in s) then begin
{j 不在 d[i]中,则表明第 i 号人不能站 j 位. j 如在 s 集合中,表明 j 位已排人了}
a[i]:=j; {第 i 人可以站 j 位}
if i<6 then try(i+1,s+[j]) {未安排妥,则继续排下去}
else output; {6 个人都安排完,则输出}
end;
end;
end;
begin
for i:=1 to 6 do d[i]:=[1..6]-[i]; {每个人的站位都与球衣的号码不同}
d[1]:=d[1]-[1,5,6];
d[6]:=d[6]-[1,5,6]; {1,6 号队员不在后排}
d[2]:=d[2]-[2,5];
d[3]:=d[3]-[2,5]; {2,3 号队员不是二传手}
d[5]:=d[5]-[3,6];
d[6]:=d[6]-[3,6]; {5,6 号队员不是副攻手}
try(1,[]);
end.
【题目】把自然数N分解为若干个自然数之和。
【参考答案】
n │ total
5 │ 7
6 │ 11
7 │ 15
10 │ 42
100 │ 190569291
【参考程序】
var n:byte; num:array[0..255] of byte; total:word;
procedure output(dep:byte);
var j:byte;
begin
for j:=1 to dep do write(num[j]:3);writeln; inc(total);
end;
procedure Hnd(n,dep:byte); {N:待分解的数,DEP:深度}
var i,j,rest:byte;
begin
for i:=1 to n do {每一位从 N 到 1 去试}
if num[dep-1]<=i then {保证选用的数大于前一位}
begin
num[dep]:=i;
rest:=n - i; {剩余的数进行下一次递归调用}
if (rest>0) then begin Hnd(rest,dep+1);end
else if rest=0 then output(dep);{刚好相等则输出}
num[dep]:=0;
end;
end;
begin {主程序}
writeln('input n:');readln(n);
Hllchar(num,sizeof(num),0);
total:=0; num[0]:=0;
Hnd(n,1);
writeln('sum=',total);
end.
【题目】把自然数N分解为若干个自然数之积。
【参考程序】
var path :array[1..1000] of integer;
total,n:integer;
procedure Hnd(k,sum,dep:integer); {K:}
var b,d:Integer;
begin
if sum=n then {积等于 N}
begin
write(n,'=',path[1]);
for d:=2 to dep-1 do write('*',path[d]);
writeln;inc(total);
exit;
end;
if sum>n then exit; {累积大于 N}
for b:= trunc(n/sum)+1 downto k do {每一种可能都去试}
begin
path[dep]:=b;
Hnd(b,sum*b,dep+1);
end;
end;
begin
readln(n); total:=0;
Hnd(2,1,1);writeln('total:',total);
剩余28页未读,继续阅读
happiers
- 粉丝: 13
- 资源: 10
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0