问题求解普及组.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 个数据 按行的顺序存入数组 A 1 A 2 中 a11 a21 a22 a31 a32 a33 an1 an2 an3 ann 其中 第一个下标表示行 第二个下标表示列 若 aij i j j i 1 2 n 存贮在 A k 中 试问 1 k 和和 i j 之间的关系如何表示 之间的关系如何表示 2 给定给定 k 值 值 k n 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 1 K 9 按如下计算步骤求序列 XJXJ 1 X0的步骤 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 1 X0 之值 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 有 2 n 的一个长方形方格 用一个 1 2 的骨牌铺满方格 例如 n 3 时 为 2 3 方格 此时用一个 1 2 的骨牌铺满方格 共有 3 种铺法 试对给出的任意一个 n n 0 求出铺法总数的递推公式 第七届普及第七届普及 二 问题求解 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 执行其中的某几个语句 并可随时通