《信息学竞赛中问题求解题常见考查题型分析》由会员分享，可在线阅读，更多相关《信息学竞赛中问题求解题常见考查题型分析（32页珍藏版）》请在金锄头文库上搜索。
1、信息学竞赛中问题求解题常见考查题型分析信息学竞赛中问题求解题常见考查题型分析问题求解是信息技术竞赛初赛中常见题型，它共两题，每题 5 分，共 10分。诸如寻找假币、博弈原理、抽屉原理、容斥问题、排列组合问题、逻辑推理、递推关系等问题出现在问题求解中，但是在实际的竞赛中，问题求解得分率往往是不高的，下面我对问题求解的题型进行了一下探索。一、寻找假币问题一、寻找假币问题有 n（n3）个硬币，其中一个是假币，已知假币的重量比其他的要重一些，你有一架天平。现在要称出哪个假币来。解析：解析：首先我们先来考虑最简单的问题 1。为了方便叙述，把 n 个硬币按 1,2,n顺次编号。若 n=3，把一号硬币放在天
2、平左边、二号硬币放在天平右边。如果天平：1、左偏，一号重，是假币。2、右偏，二号重，是假币。3、保持平衡，那么一、二都是正常的硬币，因此就只有可能三号硬币是假币了。因此 n=3，至多一次就能称出哪个是假币。记作 f(3)=1。下面考虑 n=9。把所有的硬币分成三组：A1,2,3,B4,5,6,C7,8,9。A 组的硬币放在左边、B 组放在右边。如果天平：1、左偏，则假币在 A 组里面。2、右偏，则假币在 B 组里面。3、保持平衡，假币在 C 组里面。无论在哪个组里面，我们已经把假币的范围从“9”缩小到了“3”，也就是减少到原来的 1/3。之前我们已经研究过，3 个硬币 1 次就能称出来，故而f
3、(9)=2。不难推广到一般的情况：定理定理 1.1 f(3n)=n。证明：n=1,2 时，已证。设 n=k 成立，则 f(3k)=k；下面考虑 n=k+1 的情况。将 3k+1 个硬币分成三堆 A, B, C，使得|A|=|B|=|C|=3k。把 A 放在天平左边、B 放在右边，天平：1、左偏，假币在 A2、右偏，假币在 B3、平衡，假币在 C无论哪种结果，我们都把假币的范围缩小到了 3k 个硬币里面。而 f(3k)=k，故而 f(3k+1)=k+1。综上，定理 1.1 成立。稍经分析不难得到：定理定理 1.2 f(n)= n3log这个的证明和定理 1.1 完全类似，分 n mod 3 =
4、0, 1, 2 适当讨论即可。我们必须注意到是可行的，因为我们能够构造出这样一个方案。问题n3log是它是否最优？我们采取的方案是每次将硬币尽量均匀的三分，这样做的根据就是天平只有三种结果：左偏、右偏、平衡。于是就能保证无论假币在哪一份都能将结果的范围缩小到原来的 1/3。从感性上认识，应该就是最优解了。n3log为了更加严格的证明的最优性，我们引进判定树的概念。n3log下图就是 n=9 时的一种判定树：比较(1,2,3)与(4,5,6)=13=79=46=0 thenbegininc(len3);num3i+1:=carry;end;end;procedure Work;求从出发点到目标点
5、的路径总数vari:longint;beginnum11:=1; num21:=1;for i:=start+2 to finish dobeginAdd;高精度加法运算：num3=num1+num2num4:=num1;num1:=num2;num2:=num3;num3:=num4;len4:=len1;move(len2,len1,6);end;end;procedure Out;输出结果vari:integer;beginfor i:=len2 downto 1 dowrite(num2i);writeln;end;beginDataInit; 数据初始化write(Input: );
6、readln(start,finish);Work; 求从出发点到目标点的路径总数Out; 输出结果end. 练习：练习：第 1 题(5 分)，有 5 本不同的数学书分给 5 个男同学，有 4 本不同的 英语书分给 4 个女同学，将全部书收回来后再从新发给他们，与原方案都不相 同的方案有_种。答案： 5!*4!+D(5)*D(4)=1140480其中：D(n)=(n-1)*(D(n-1)+D(n-2) (n 2)D(1)=0 D(2)=1第 2 题(5 分)，在 m*n 的棋盘上，每个方格(单位正方形，即边长为 1 的正方形)的顶点称为格点。以格点为顶点的多边形称为格点多边形。若设格 点凸 N
7、 边形面积的最小值为 gn，格点凸 N 边形内部(非顶点的)格点的个数的最 小值为 fn，则 gn 和 fn 的关系式为 gn=_。答案：Gn= fn+N/2-1 ( N = 3 )第 3 题(8 分)，有位小同学喜欢在方阵中填数字，规则是按下图示例 从右上角开始，按斜线填数字，碰到边界就重新。显然，数字 1 在坐标(1，5) 位置，数字 25 在坐标(5，1)位置。后来这位小朋友想知道，对于 N 阶的方阵， 随机取一个位置(x，y)，并规定 xy，问这个位置上应该填的数字是多少?5 阶 方阵的示例图如下：11 7 4 2 116 12 8 5 320 17 13 9 623 21 18 14
8、 1025 24 22 19 15答案：(N-y+x)*(N-y+x-1)/2+x第 4 题(5 分)，把三角形各边分成 n 等分，过每一分点分别做各边的 平行线，得到一些由三角形的边和这些平行线所组成的平行四边形。n 为已知 整数，能组成_个平行四边形。答案：3*C(n+2,4)第 5 题(5 分)，由 a，b，c3 个不同的数字组成一个 N 位数，要求不 出现两个 a 相邻，也不出现两个 b 相邻，这样的 N 位数的个数为 AN，用 AN-1 和 AN-2 表示 AN 的关系式为：AN_。答案：AN= 2*AN-1+AN-2作者单位：江苏省洪泽县第二中学姓 名：吴斌通讯地址：江苏省洪泽县第二中学电教中心组邮编： 223100电 话：13912054539QQ:372836808邮件地址：HZEZDJZX126.COM
