问题求解普及组.doc

1 问题求解二（历届全国初赛题）问题求解二（历届全国初赛题） 【第一届普及第一届普及】 1请将以下程序段表示的计算公式写出来（假设 X 的值已给出） E：=1 ； A：=1 ； FOR N：=1 TO 10 DO A：=A*X/N ； E：=E+A ； ENDFOR ； 写出所表示的公式。写出所表示的公式。 2 列举一个算法，使算法的解能对应相应的问题。 例如，设问题为：学生答题，答对一题可得 10 分，答错一题则要扣去 5 分，输入 答对的题数（M）与答错的题数（N） ，求最后得分（S）是多少？ 列举出相应算法为： X：=10； Y：=5； READ（M，N） ； S：=X*M-Y*N； 现有以下问题：用五角钱换成 5 分、2 分与 1 分的硬币，可有多少种换法？ 请列出该问题的算法。请列出该问题的算法。 3 已知如下 N*(N+1)/2 个数据，按行的顺序存入数组 A1，A2，中： a11 a21 a22 a31 a32 a33 an1 an2 an3 ann 其中：第一个下标表示行 第二个下标表示列。 若：aij(ij,j,i=1,2,n)存贮在 Ak中，试问： （1）k 和和 i，j 之间的关系如何表示？之间的关系如何表示？ （2）给定给定 k 值（值（kn*(n+1)/2)后，写出能决定相应的后，写出能决定相应的 i，j 值的算法。值的算法。 2 4 有红、黄、黑、白四色球各一个，放置在一个内存编号为 1、2、3、4 四个格子的 盒中，每个格子放置一只球，它们的顺序不知。甲、乙、丙三人猜测放置顺序如下： 甲：黑编号 1，黄编号 2； 乙：黑编号 2，白编号 3； 丙：红编号 2，白编号 4 。 结果证明甲乙丙三人各猜中了一半。 写出四色球在盒子中放置情况及推理过程。写出四色球在盒子中放置情况及推理过程。 【第四届普及第四届普及】 二、问题求解：（20%） 1已知一个数列 U1，U2，U3，UN， 往往可以找到一个最小的 K 值和 K 个数 a1，a2， ，ak使得数列从某项开始都满足： UN+K=a1UN+K-1+a2UN+K-2+akUN (A) 例如对斐波拉契数列 1，1，2，3，5，可以发现：当 K=2，a1 =1，a2 =1 时， 从第 3 项起（即 N=1）都满足 U n+2 =Un+1+Un 。试对数列 12，22，32，n2,求 K 和 a1,a2, ,aK使得（A）式成立。 7% 2某班有 50 名学生，每位学生发一张调查卡，上写 a，b，c 三本书的书名，将读 过的书打，结果统计数字如下： 只读 a 者 8 人；只读 b 者 4 人；只读 c 者 3 人；全部读过的有 2 人；读过 a，b 两本书的有 4 人；读过 a，c 两本书的有 2 人；读过 b，c 两本书的有 3 人；6% （1）读过 a 的人数是 （2）一本书也没有读过的人数是 3任给自然数 n，k， 1K9 ，按如下计算步骤求序列 XJXJ-1X0的步骤： 8% （1） j=0 （2） 如果 N=K 则转第 3 步，否则转第 7 步 （3） Xj = N MOD K div 表示整数除法，结果取整数； （4） N =N DIV K mod 表示整除取余数 （5） j=j+1 （6） 回第 2 步 （7） Xj = N （8） 结束 试求当： N=1998， K=3 时，XJXJ-1X0 之值。 3 【第五届普及第五届普及】 三公式推导（10 分） 根据 Nocomachns 定理，任何一个正整数 n 的立方一定可以表示成 n 个连续的奇数 的和。 例如： 13 1 23 3 5 33 7 9 11 43=13+15+17+19 在这里，若将每一个式中的最小奇数称为 X，那么当给出 n 之后，请写出 X 与 n 之 间的关系表达式：_ 【第六届普及第六届普及】 二、问题解答：（每题 7 分，共 14 分） 1.已知，按中序遍历二叉树的结果为：abc 问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。 2.有 2n 的一个长方形方格，用一个 12 的骨牌铺满方格。例如 n=3 时，为 23 方格。 此时用一个 12 的骨牌铺满方格，共有 3 种铺法： 试对给出的任意一个 n(n0)，求出铺法总数的递推公式。 【第七届普及第七届普及】 二、问题求解(5+7=12 分) 1.在 a,b,c,d,e,f 六件物品中，按下面的条件能选出的物品是： (1)a,b 两样至少有一样 (2)a,d 不能同时取 (3)a,e,f 中必须有 2 样 (4)b,c 要么都选，要么都不选 (5)c,d 两样中选一样 (6)若 d 不选，则 e 也不选 2.平面上有三条平行直线，每条直线上分别有 7，5，6 个点，且不同直线上三个点都不 在同一条直线上。问用这些点为顶点，能组成多少个不同三角形？ 【第八届普及第八届普及】 二.问题求解: 4 1. 如下图,有一个无穷大的的栈 S,在栈的右边排列着 1,2,3,4,5 共五个车厢。其中每 个车厢可以向左行走,也可以进入栈 S 让后面的车厢通过。现已知第一个到达出口的是 3 号车厢，请写出所有可能的到达出口的车厢排列总数(不必给出每种排列)。 出口 1 2 3 4 5 S 2.将 N 个红球和 M 个黄球排成一行。例如:N=2,M=3 可得到以下 6 种排法: 红红黄黄黄 红黄红黄黄 红黄黄红黄 黄红红黄黄 黄红黄红黄 黄黄黄红红 问题:当 N=4,M=3 时有多少种不同排法?(不用列出每种排法) 【第九届普及第九届普及】 二问题求解(每题 5 分，共 10 分) 1现在市场上有一款汽车 A 很热销，售价是 2 万美元。汽车 A 每加仑汽油可以 行驶 20 英里。普通汽车每年大约行驶 12000 英里。油价是每加仑 1 美元。不久我公司 就要推出新款节油汽车 B，汽车 B 每加仑汽油可以行驶 30 英里。现在我们要为 B 制定 价格(它的价格略高于 A)：我们预计如果用户能够在两年内通过节省油钱把 B 高出 A 的价钱弥补回来，则他们就会购买 B，否则就不会购买 B。那么 B 的最高价格应为 万美元。 2无向图 G 有 16 条边，有 3 个 4 度顶点、4 个 3 度顶点，其余顶点的度均小于 3，则 G 至少有 个顶点。 【第十届普及第十届普及】 二问题求解 （每题 5 分，共 10 分） 1. 一个家具公司生产桌子和椅子。现在有 113 个单位的木材。每张桌子要使用 20 个单位的木材，售价是 30 元；每张椅子要使用 16 个单位的木材，售价是 20 元。使用 已有的木材生产桌椅（不一定要把木材用光） ，最多可以卖 元钱。 2. 75 名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已 知其中 20 人这三种东西都玩过，55 人至少玩过其中的两种。若每样乘坐一次的费用是 5 元，游乐场总共收入 700，可知有 名儿童没有玩过其中任何一种。 【第十一届普及第十一届普及】 二.问题求解（请在空格处填上答案，每空 5 分，共 10 分） 1.将数组32,74,25,53,28,43,86,47中的元素按从小到大的顺序排列，每次可以交换任意 两个元素，最少需要交换_次。 2.有 3 个课外小组：物理组，化学组和生物组。今有张、王、李、赵、陈、5 名同学， 已知张、王为物理组成员，张、李、赵为化学组成员，李、赵、陈为生物组成员。如 果要在 3 个小组分别选出 3 位组长，一位同学最多只能担任一个小组的组长，共有_ 5 种选择方案。 【第十二届普及第十二届普及】 二问题求解（共 2 题，每题 5 分，共计 10 分） 1 （寻找假币） 现有 80 枚硬币，其中有一枚是假币，其重量稍轻，所有真币的重量 都相同，如果使用不带砝码的天平称重，最少需要称几次，就可以找出假币？你还要 指出第 1 次的称重方法。请写出你的结果： _。 2 （取石子游戏） 现有 5 堆石子,石子数依次为 3，5，7，19，50，甲乙两人轮流从任 一堆中任取（每次只能取自一堆，不能不取）, 取最后一颗石子的一方获胜。甲先取， 问甲有没有获胜策略（即无论乙怎样取，甲只要不失误，都能获胜）？如果有，甲第 一步应该在哪一堆里取多少？请写出你的结果： _。 【第十三届普及第十三届普及】 二、问题求解（共 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，最短的走法共有多少种？ _ 【第十四届普及第十四届普及】 二、问题求解（共 2 题，每题 5 分，共计 10 分） 1书架上有 4 本不同的书 A、B、C、D。其中 A 和 B 是红皮的，C 和 D 是黑皮的。 把这 4 本书摆在书架上，满足所有黑皮的书都排在一起的摆法有_种。满足 A 必须比 C 靠左，所有红皮的书要摆在一起，所有黑皮的书要摆放在一起，共有 _种摆法。 2有 6 个城市，任何两个城市之间都有一条道路连接，6 个城市两两之间的距离如下 表所示，则城市 1 到城市 6 的最短距离为_。 6 城市 1 城市 2 城市 3 城市 4 城市 5 城市 6 城市 1 0 2 3 1 12 15 城市 2 2 0 2 5 3 12 城市 3 3 2 0 3 6 5 城市 4 1 5 3 0 7 9 城市 5 12 3 6 7 0 2 城市 6 15 12 5 9 2 0 【第十五届普及第十五届普及】 二. 问题求解（共 2 题，每空 5 分，共 10 分） 1. 小陈现有 2 个任务 A，B 要完成，每个任务分别有若干步骤如下：A=a1-a2- a3，B=b1-b2-b3-b4-b5。在任何时候，小陈只能专心做某个任务的一个步骤。但 是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任 务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如a2-b2-a3- b3是合法的，而 a2-b3-a3-b2是不合法的。小陈从 B 任务的 b1 步骤 开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得 自己已经完成了整个任务 A，其他的都忘了。使计算小陈饭前已做的可能的任务步骤 序列共有 _ 种。 【分析】70 解法一： 相当于以前的 A 到 B 路程的问题，呵呵 a3 0 1 4 10 20 35 a2 0 1 3 6 10 15 a1 0 1 2 3 4 5 0 1 1 1 1 1 b1 b2 b3 b4 b5 能明白吧。然后把 a3 那一行加起来 1+4+10+20+35=70。 解法二： 排列组合+加法原理 B 任务中的 b1 一定做，而且肯定是第一个做的。除了 b1 外， 第一类：完成 A 任务 只有 1 种。 第二类：完成 A 任务和 b2 有 C(4,1)=4 种。 第三类：完成 A 任务和 b2、b3 有 C(5,2)=10 种。 第四类：完成 A 任务和 b2、b3、b4 有 C(6,3)=20 种。 第五类：完成 A 任务和 b2、b3、b4、b5 有 C(7,4)=35 种。 加起来 1+4+10+20+35=70。 2. 有如下的一段程序： 1. a:=1; 2. b:=a; 7 3. d:=-a; 4. e:=a+d; 5. c:=2*d; 6. f:=b+e-d; 7. g:=a*f+c; 现在要把这段程序分配到若干台（数量充足）用电缆连接的 PC 上做并行执行。每台 PC 执行其中的某几个