陕西省西安高级中学导高中信息技术奥赛强化练习卷六.docVIP

信息学奥赛强化练习卷六信息学奥赛强化练习卷六 以下各题请分析问题 完善程序以下各题请分析问题 完善程序 1 题题 目目 找出小于 33 的 6 个正整数 用这些整数进行加法运算 使得包括原来的整数在内能组 成尽可能多的不同整数 例如 用 2 3 5 这三个数能可组成下面的数 2 3 5 2 3 5 但 5 已经存在 2 5 7 3 5 8 2 3 5 10 所以用 2 3 5 能组成 6 个不同的数 程序要求程序要求 输出所选的这 6 个数 以及能组成不同整数的个数 算法提要算法提要 选择的这 6 个数 用来组成数时应该尽可能不重复 引入数组 A 保存找 出的这 6 个整数 程序 begin A 1 1 t 0 For i 2 to 6 do begin for j 1 to i 1 do s a i END FOR i 1 TO 6 DO begin T WRITE a i END Writeln 能组成不同整数的个数 t End 答 s 0 s s a j a i s 1 t t a i 或 t t 2 1 分析 掌握程序中变量 S 的意义是求解本题的关键 根据算法说明中提到的 选择 的这 6 个数 用来组成数时应尽可能不重复 这一策略 同时 这 6 个数要小于 33 的限制 条件 我们不妨假设前 I 1 个数 a1 a2 a3 a4 ai 1 已找到 对第 I 个数 ai 确定其值的原则 为 1 ai 要尽可能小且满足 a1 a2 a3 a4 ai 1 ai 2 由 ai 参与加法的结果应大 于 a1 a2 a i 1 这样保证与前 I 1 个数所组成的整数不重复 显然 ai a1 a2 ai 1 1 因 此 S 的意义为前 I 1 个数之和 填空 为 S a j 填空 置 S 初值为 0 填空 为 S 1 我们还可以换一种方法来思考 所选 6 个数 1 a1 a2 a3 a4 a5 a6 33 这 6 个数在 组成数时 每一个数都有参与加法或不参与加法两种可能 很自然想到 这 6 个数在组成 数时 可用一个 6 位二进制数表示 b6b5b4b3b2b1 其中 bi 0 表示 ai 不参与加法运算 bi 1 表示 ai 参与加法运算 6 位二进制数的每一种情况就表示组成的一个数 且各不相同 000001 表示只有 a 1 1 时的值 当有 a 1 1 和 a 2 时 能组成的数为 000001 000010 000011 这 3 个不同的数 所以 a 2 取 2 即二进制 000010 依次 可得 a 3 4 即二进制 000100 a 4 8 a 5 16 a 6 32 能组成不同整数的个数 t a 1 a 2 a 3 a 4 a 5 a 6 所以 处应填 t a I 得到累 加和 2 题题 目目 求出所有满足下列条件的二位数 将此二位数的个位数字与十位数字进行交换 可得 到一个新的数 要求新数与原数之和小于 100 程序要求程序要求 每行输出 6 个满足条件的数 算法提要算法提要 分解每一个二位数 然后重新组成一个新数 当满足条件时 用计数器来 统计个数 程序 K 0 FOR i TO 99 DO X Y J x 10 y IF THEN K k 1 Write I 4 THEN WRITELN ENDIF ENDFOR 答 10 x i mod 10 y i div 10 If i j A J THEN WRITELN S S END 答 N 1 I 1 S S 1 4 题题 目目 装球 设有 n 个盒子 n 足够大 可装入任何数量的球 分别编号 1 2 同时 有 k 个小球 k 0 今将 k 个小球装入到盒子中去 装入规则如下 1 第一个盒子不能为空 2 装入必须严格按递增顺序进行 例如 当 k 8 n 6 时 装入方法有 1 2 5 或 1 3 4 3 在满足上面的两个条件下 要求有球的盒子尽可能多 4 装完后 相邻盒子中球个数差的绝对值之和最小 未装的盒子不计 如上例中 装入法 1 2 5 则差的绝对值之和为 2 1 5 2 4 装入法 1 3 4 则差的绝对值之和为 3 1 4 3 3 程序要求程序要求 给出 k k 表示小球的个数 之后 求出满足上述四个条件的装入方法 算法描述算法描述 设计一个数组 A 用数组元素代表盒子 然后依次装入小球 程序清单程序清单 CONST N 20 VAR I J K L INTEGER A ARRAY 1 N OF INTEGER BEGIN READLN K J 1 WHILE DO BEGIN A J J J J 1 END L J 1 WHILE K 0 DO BEGIN K K 1 L L 1 END FOR I 1 TO DO WRITE A I 4 END 答 for I 1 to n do A I 0 K A J I K K J A L A L 1 J 1 分析分析 由本题条件 1 第一个盒子至少放一个小球 即 A I 1 根据条件 2 盒 子中放到小球数必须严格按递增的顺序 因此 A 1 A 2 A n 1 J 上述这种放球的思路可以仔细阅读程序得到启发 语句 a j j 告诉我们程序先利用第 j 号盒子放 j 个球的方法 满足题目给出的前三个条件 用上述方法放球后 如果余下的球数为 0 放球过程结束 如果还有球多出来 把这 些余下的球再分配到各个装球的盒中 考虑到条件 4 装完后 相邻的盒中球的个数差 的绝对值之和为最小 如何分配 这是程序要处理的第二个问题 由于 a1 a2 an 相 邻盒中球个数差的绝对值之和 s a2 a1 a3 a2 an 2 an 1 a2 a1 a3 a2 an 2 an 1 an an 1 an a1 显然 s 与第 1 个盒子 第 n 个盒子的球数有关 增加第 1 个盒子的球数 可以使 s 更 小 但第 1 个盒子加 1 个 后面的盒子至少都要加 1 个 而多出来的球数 n 所以只能从 编号大的加起 逐个往编号小的盒子中加 1 个球 直到加完为止 最多 n 个盒子 程序中 处应填 a 1 a 1 1 变量 j 的最后值为装球盒子数加 1 所以输出部分 I 的终值应为 装球的盒子数 j 1 2 题题 目目 4 色问题 设有下列形状的图形 N 8 其编号为 1 2 N 图形之间的相邻关系用下面的邻接矩阵表示 12345678 101000011 210100110 301010100 400101100 500010100 601111010 711000101 810000010 其中 1 相邻 0 不相邻 程序要求程序要求 将上面图形的每一个部分涂上红 1 黄 2 蓝 3 绿 4 四种颜 色之一 要求相邻的部分有不同颜色 输入方式 邻接矩阵 输出方式 区域 颜色 算法描述算法描述 用数组 R ARRAY 1 N 1 N OF 0 1 表示相邻关系 S ARRAY 1 N OF INTEGER 表示颜色 采用回溯的方法 首先给第一个图形涂上红色 1 然后在下面的图形中依次涂上其 他颜色 当有矛盾时回溯解决 程 程 序 序 PROGRAM EXP2 INPUT OUTPUT CONST N 8 VAR I J K INTEGER R ARRAY 1 N 1 N OF 0 1 S ARRAY 1 N OF INTEGER BEGIN FOR I 1 TO N DO BEGIN FOR J 1 TO N DO READ R I J READLN END I 2 J 1 WHILE I N DO BEGIN WHILE J 4 AND I N DO BEGIN K 1 WHILE DO K K 1 IF K4 THEN BEGIN I I 1 END END FOR I 1 TO N DO WRITELN I S I END 答 S 1 1 K I AND S K R I J J J J 1 S I J J S I 1 分析分析 涂色算法 深度优先搜索 读入邻接矩阵 对第一号区域涂色 while I n do 还有区域尚未涂色 while J 4 and I n do 选择颜色 begin if k I and 检查相邻区域 如不是当前要涂色区域 then 试探下一区 k 1 K if 当前色不能涂 then 试探下一种颜色 y 1 y else 本区域涂色 准备试探下一区域 if 试探不成功 then 回溯 I 1 I 返回上一个点区域 修正 y 颜色值 end 3 题题 目目 多项式加法运算 一个仅含有 x 的多项式可以用下列的方式表示 系数 指数 系数 指数 0 0 其中 0 0 作为结束标志 例如 P x 4x6 3x3 2x2 1 可表示为 4 6 3 3 2 2 1 0 0 0 Q x x4 x 1 可表示为 1 4 1 1 1 0 0 0 当用上面的方式给出 2 个多项式之后 编制程序对这两个多项式进行加法运算 结果 也用上面的方式给出 例如 上面的 P x 和 Q x 相加的结果为 4x6 x4 3x3 2x2 x 表示结果为 4 6 1 4 3 3 2 2 1 1 0 0 算法描述算法描述 多项式可用数组 P 表示 分别以 p1 表示 P p2 表示 Q p3 表示结果 处理的过程为将 P 复制到 p3 然后逐项检查 Q 当发现有相同的方次时 进行系数相 加 当发现没有相同方次时 插入到 p3 中去 程程 序序 PROGRAM EXP3 INPUT OUTPUT VAR X Y I I1 J J1 J2 INTEGER P1 P2 P3 ARRAY 1 20 1 2 OF INTEGER BEGIN J1 0 WRITE INPUT P X READ X Y WHILE X0 DO BEGIN J1 J1 1 P1 J1 1 X P1 J1 2 Y READ X Y END J1 J1 1 P1 J1 1 0 P1 J1 2 0 WRITE INPUT Q X READ X Y J2 0 WHILE X0 DO BEGIN J2 J2 1 P2 J2 1 X P2 J2 2 Y READ X Y END J2 J2 1 P2 J2 1 0 P2 J2 2 0 FOR I 1 TO J1 DO BEGIN P3 I 1 P1 I 1 P3 I 2 P1 I 2 END I 1 WHILE DO BEGIN IF THEN BEGIN FOR J J1 DOWN TO 1 DO BEGIN P3 J 1 1 P3 J 1 P3 J 1 2 P3 J 2 END P3 I 1 P2 I 1 P3 I 2 P2 I 2 J1 J1 1 END ELSE BEGIN I1 1 WHILE P2 I 2 P3 I1 2 DO IF P2 I 2 P3 I1 2 THEN P3 I1 1 ELSE BEGIN FOR J J1 DOWNTO I1 DO BEGIN P3 J 1 1 P3 J 1 P3 J 1 2 P3 J 2 END P3 I1 1 P2 I 1 P3 I1 2 P2 I 2 END END I I 1 END FOR J 1 TO J1 2 DO WRITE P3 J 1 P3 J 2 WRITELN P3 J 1 1 P3 J 1 2 END 答 P2 I 1 0 P2 I 1 P3 1 2 I1 I1 1 P3 I1 1 P2 I 1 J1 J1 1 分析 程序实现的是线性表的归并算法 多项式相加的规则是指数相同 系数相加 多项式 p 和 q 利用了将系数不为 0 的项用一对数字表示某一项的方式 分别存在一个二维数组中 p 和 q 相加的结果用另一个二维数组存放 根据算法说明 归并运算实际上在表示多项式 q 的数组 p2 和表示相加结果的数组 p3 之间进行 p3 的初始值为表示多项式 p 的数组 p1 其初始长度为 p1 的长度 以后在归并过程中 p3 的长度将会变大 因此 仔细阅读程序 可发现 表示 p3 长度的变量 j1 是一个关键的量 程序的主要部分是如何实现将 p2 的每一 分量加入到数组 p3 中去 程序利用循环扫描数组 p2 的方法 其扫描指针为变量 I 因此 1 处为循环控制条 件 由题意可知 应为 p2 I 1 0 下面的循环体用嵌套的 if then else 结构分别处理 p2 数组的当前分量 p2 I 是插入到 p3 还是与 p3 中某一分量合并 指数相同时 从 if 条件 2 成立时处理的程序段 for j j1 downto 1 do 可知 是将 p3 各项依次向后移一位置 p2 I 插入 p3 的第 1 个位置 可知 2 应为 p2 I 2 p3 I 2 即 p2 i 的指数大于 p3 的最 大指数 注 数组表示多项式均利用降幂