NOIP2011普及组思维训练题实例

NOIP普及组思维训练题实例

例1:传球游戏

上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，老师带着同学们一起做传球游戏。 游戏规则是这样的：n个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老师再次吹哨子时，传球停止，此时，拿着球没传出去的那个同学就是败者，要给大家表演一个节目。

聪明的小蛮提出一个有趣的问题：有多少种不同的传球方法可以使得从小蛮手里开始传的球，传了m次以后，又回到小蛮手里。两种传球的方法被视作不同的方法，当且仅当这两种方法中，接到球的同学按接球顺序组成的序列是不同的。比如有3个同学1号、2号、3号，并假设小蛮为1号，球传了3次回到小蛮手里的方式有1->2->3->1和1->3->2->1，共2种。

【输入】 输入文件ball.in共一行，有两个用空格隔开的整数n，m（3<=n<=30，1<=m<=30）。 【输出】 输出文件ball.out共一行，有一个整数，表示符合题意的方法数。 【输入输出样例】 ball.in ball.out 3 3 2 题解一 搜索法 根据题意可知，每个同学可以把球传给自己左右的两个同学中的一个，我们可以模仿传球的方法尝试用搜索法，每个搜索点都分左右两条分支去搜，当传球m次并且传到1号同学，方案数sum加1，以下是分三种情况进行搜索：

1、当球在1号同学时，传球方案如图所示：

N 1 2

2、当球在n号同学时，传球方案如图所示：

n-1 n 1

3、当球在第k号同学时(1k-1 k K+1

源程序： var

n,m,sum:longint;

procedure pp(k,step:integer); begin

if step=m then begin if k=1 then sum:=sum+1; exit; end; ｛方案数加1｝ if k=n then begin pp(1,step+1); pp(k-1,step+1);end; ｛传球方案2｝ if k=1 then begin pp(n,step+1); pp(k+1,step+1);end; ｛传球方案1｝

if (k>1)and(kreadln(n,m);

2

pp(1,0);

write(sum); end.

题解二 递推法

我们可以发现要球传到某个人，只能从左边传过来或者右边传过来，设当前球的位置号用i表示，传球次数用j表示，那么他的方案数是左右两边的方案数之和 即：

f[i,j]:=f[i-1,j-1]+f[i+1,j-1]; 这里有两种边界要分别考虑

1、当球在1号同学时可知：f[1,j]:=f[2,j-1]+f[n,j-1]; 2、当球在n号同学时可知：f[n,j]:=f[n-1,j-1]+f[1,j-1];

当然这里还要考虑递推初始值，因为是从一号同学开始传球，我们可以给f[1,0]赋值， f[1,0]:=1;有了递推初始值和递推关系式，我们就可以根据传球次数进行递推。 源程序： var

i,j,k,t,n,m,c,s:longint;

f:array[1..30,1..30]of longint; begin

readln(n,m);

fillchar(f,sizeof(f),0);

f[1,0]:=1; ｛赋初值｝

for j:=1 to m do ｛按传球次数递推｝ begin

for i:=2 to n-1 do

f[i,j]:=f[i-1,j-1]+f[i+1,j-1]; f[1,j]:=f[2,j-1]+f[n,j-1]; f[n,j]:=f[n-1,j-1]+f[1,j-1]; end;

writeln(f[1,m]); end.

题解三 穷举法

因为只有两种传球方法，设向左走的步数为i，向右走的步数为j

那么如果 abs(j－i)mod n=0 也就是说球传到了原来的位置1号同学这里。方案数为：

左左….左, 右右….右全部的组合数。即有i＋j=m个位置，可放i个左，则方法为C（m，i）组合数 我们可以穷举i,穷举范围0<=i<=m 把满足条件abs(j－i)mod n=0的求C（m，i）组合数,并加入到方案数sum中。 源程序： var

i,j,m,n:integer; sum:real;

function c(m,n:integer):real;｛求组合数｝ var

i:integer; s:real; begin

if n=0 then begin c:=1;exit; end;

3

s:=1.0;

for i:=m downto m-n+1 do s:=s*i; for i:=n downto 2 do s:=s/i; c:=s; end; begin

readln(n,m);

for i:=0 to m do ｛穷举i｝ begin j:=m-i;

if abs(j-i) mod n=0 then ｛判断是否能回到1号同学｝ sum:=sum+c(m,i);{组合数加入到sum中} end;

writeln(sum:0:0); end.

例2：装箱问题

[问题描述]有一个箱子容量为V（正整数，0≤V≤20000），同时有n个物品（0要求从n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。 [样例]

输入: 24 一个整数，表示箱子容量

6 一个整数，表示有n个物品

8 接下来n行，分别表示这n个物品的各自体积。 3 12 7 9 7

输出： 0 一个整数，表示箱子剩余空间。 穷举法分析：

为了穷举每一种状态，用数组a来存储n件物品的选取状态，a[i]=1表示第i个物品被选取，a[i]=0表示第i个物品末被选取，a[0]是循环开关，初始时a[0]=0，当a[0]=1时穷举结束；另外，用min 记录最小剩余量，针对穷举产生的每一种状态先计算出箱子所用的容量s，如果v-s< min，则更新min的值。 穷举法程序1： var

v,n:integer;

w: array[1 .. 30] of integer; {存储n件物品的体积}

a: array[0 .. 30] of integer; {存储n件物品的选取状态}

i,j,min,s:integer; { min 记录最小剩余量；s为累加器，统计已选物品的体积和} begin

read(v);

min:=v; {初始时设定最小剩余量为箱子总容量} read(n);

for i:=1 to n do read (w[i]); for i:=0 to n do a[i]:=0; while a[0]=0 do

4

begin

j:=n;

while a[j]=1 do j:=j-1;

a[j]:=1; {设定新的状态} for i:=j+1 to n do a[i]:=0;

s:=0; {计算被选取物品的体积和} for i:=1 to n do

if a[i]:=1 then s:=s+w[i];

if (v-s>=0) and (v-swriteln(min); end.

回溯法例程2： var

v,n,i,best:integer;

box,s:array[0..30]of longint;

procedure search(k,v:integer);{从状态k,v出发，递归计算最小剩余空间} begin

if v=best

then exit; {若箱子即便能装下全部物品，其剩余空间仍不小于best，则回溯} if k<=n then{在未装入全部物品的前堤下搜索两种可能情况} begin

if v>=box[k]

then search(k+1,v-box[k]);{把物品K装入箱子，递归计算子状态}

search(k+1,v); {物品K不装入箱子，递归计算子状态} end; end; begin

readln(v);{读入箱子体积} readln(n);{读入物品数} s[0]:=0;

for i:=1 to n do begin

readln(box[i]);{读入第i个物品的体积}

s[i]:=s[i-1]+box[i];{计算前i个物品的体积和} end;

best:=v;{初始时最小剩余空间为箱子体积}

if s[n]<=v then best:=v-s[n] {若所有物品能全部装入箱子，则剩余空间为问题的解} else search(1,v);{否则从物品1出发，递归计算最小剩余空间} writeln(best);{输出最小剩余空间} end.

动态规划例程3： var

i , j , n , v : integer;

box:array[1..30] of integer; {存储每个物品各自的体积}

5

f0,f1:array[0..20000] of boolean; { f1[j]为真,表示箱子能装下体积为J的物品} begin read(v,n);

for i:=1 to n do read(box[i]);

fillchar(f0,sizeof(f0),false); {装箱前，状态转移方程初始化} f0[0]:=true;

for i:=1 to n do {阶段I：按物品数递增的顺序考虑装箱情况} begin

f1:=f0; { I阶段的状态转移方程初始化}

for j:=box[i] to v do {状态J：枚举所有可能的装箱体积}

if f0 [ j-box[i] ] then f1[j]:=true; {若物品I装入箱子后的体积正好为J，则物品装入箱子} f0:=f1; {记下当前装箱情况}

for i:=v downto 0 do {按递减顺序枚举所有可能的体积} end;

if f1[i] then begin {若箱子能装入体积为I的物品，则输出剩余空间为V-I，并退出程序} writeln(v-i); halt; end;

writeln(v); {在末装入一个物品的情况下输出箱子体积} end.