[整理]全国信息学奥赛1995~2004年分类试题汇编完善程序.doc

1 问题描述 求出所有满足下列条件的二位数 将此二位数的个位数字与十位数字进 行交换 可得到一个新的数 要求新数与原数之和小于 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 2 问题描述 找出小于 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 个整数 程序 a 1 1 t 0 for i 2 to 6 do for j 1 to i 1 do s endfor a i endfor for i 1 to 6 do t write a i endfor writeln 能组成不同整数的个数 t end 3 问题描述 求出 2 1000 之间长度最长的 成等差数列的素数 质数 例如 在 2 50 之间的全部素数有 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 其中 公差为 1 的素数数列为 2 3 其长度为 2 公差为 2 的素数数列为 3 5 7 其长度为 3 程序要求 输出满足条件的素数数列 算法提要 首先用筛选法求出此范围内的全部素数 存放在数组 B 中 然后用 2 个变 量 i j 逐步求出满足条件的素数数列 程序 max 0 num 1000 for i 2 to num do b i i endfor for i 2 to do if then k i i while k num do b k 0 k k i endwhile endif endfor for i 2 to num 1 do if then j 1 d j b i for i1 do if b i1 0 then delta k delta while i kmax then begin max j c d 数组 d 的每个元素值分别送放数组 c 的相应元素中去 endif j 1 endif endfor endif endfor writeln the max length is max write the string is for i 1 to max do write c i writeln endfor 4 问题描述 求出二个整形数组错位相加的最大面积 1 数组面积的定义 限定数组头尾不为 0 设有一个数组 C 4 8 12 0 6 则 C 的面积为 Sc 4 8 2 8 12 2 12 2 6 2 也就是说 Sc 各梯形面积之和 其中梯 形的高约定为 1 三角形作为梯形的特殊情况 处理 又如 D 12 24 6 时 其面积的定义为 Sd 12 24 2 24 6 2 2 数组错位相加的定义 设有 2 个正整数的数组 a b 长度为 n 当 n 5 时 a 34 26 15 44 12 b 23 46 4 0 18 对 a b 进行错位相加 可能有下列情况 34 26 15 44 12 12 24 6 11 4 8 12 1 6 111 23 46 4 0 18 34 26 15 44 12 23 46 4 0 18 或 34 26 15 44 12 23 46 4 0 18 34 26 15 44 35 46 4 0 18 或 34 26 15 44 12 23 46 4 0 18 34 26 15 67 58 4 0 18 或 最后有 34 26 15 44 12 23 46 4 0 18 23 46 4 0 18 34 26 15 44 12 可以看到 由于错位不同 相加的结果也不同 程序要求 找出一个错位相加的方案 使得输出的数组面积为最大 算法提要 设 a b 的长度为 10 用 a b array 1 10 of integer 表示 其结果用数组 C D array 1 30 of integer 表示 错位相加的过程可以从开始不重叠 然后逐步重叠 再到最后的不重叠 梯形面积的计算公式为 上底 下底 高 2 其中由于约定高为 1 故可写为 上底 下底 2 程序 n 10 function sea real 计算数组 c 面积 begin j1 1 while do j1 j1 1 endwhile if j1 3 n then sea 0 else begin j2 3 n while do j2 j2 1 if j1 j2 then sea 0 else begin j3 c j1 c j2 for j4 j1 1 to j2 1 do inc j3 c j4 2 endfor sea j3 2 end endif end 主程序 for i 1 to n do read a i endfor for j 1 to n do read b j endfor for i 1 to 2 n 1 do for j 1 to 3 n do endfor for j 1 to n do c j n a j endfor for j 1 to n do endfor p sea if p s then begin d c s p end endif endfor for i 1 to 3 n do write d i endfor write s end 主程序结束 5 问题描述 设有 N 个不同整数的数列 例如 N 4 时 有 4 个不同整数的数列为 17 4 16 5 数列中的第 1 个数 17 比它后面的三个数都大 则称数 17 的逆数为 3 数列中的第 2 个数 4 比它后面的数都小 则称数 4 的逆数为 0 同时记数列中全部逆数的 和称为数列的逆数 上例中 数列 17 4 16 5 的逆数 为 3 0 1 0 4 程序要求 当给出 N 个不同整数的数列后 求出此数列的逆数 算法描述 为求得上面问题的解 设置数组 A ARRAY 1 N OF INTEGER 和逆数计数 器 5 然后用一个二重循环求出数列的逆数 程序清单 const n 10 var i j s integer a array 1 n of integer begin s 0 for i 1 to n do read a i for i 1 to 1 do for j 2 to n do if a i a j then 3 writeln s s end 6 问题描述 装球 设有 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 1 j 1 while 2 do begin a j j 3 j j 1 end l j 1 while k 0 do begin 4 k k 1 l l 1 end for i 1 to 5 do write a i 4 end 7 问题描述 积木游戏 设有 n 个小木块排成一排 如下图 游戏开始时 每个小木块向下的一面涂有红 黄 蓝三种颜色之中的一种 约定 0 表示红色 1 表示黄色 2 表示兰色 要求通过翻看与交换方式对小木块重新排列 翻 看的规则为每个小木快只能看一次 最终成为下面的形状 红 蓝 黄 即相同颜色的木块排列在一起 设计一个翻看与交换的方案 使得用最少的交换次 数实现上面的要求 算法描述 翻看小木块时 可以从两端进行 例如 设中间状态如下 A B C 红 未翻过 蓝 黄 此时 可以从两个方向看 即从 A 或 B 处开始 1 若看 A 则有三种可能性 为红色 则不用交换 为兰色 交换一次 即 A 与 B 交换 为黄色 交换两次 即 C 与 B 交换一次 然后 A 与 C 再交换一次 此时 平均交换次数为 1 2 若看 B 也有三种可能性 为兰色 则不用交换 为红色 交换一次 即 B 与 A 交换 为黄色 交换一次 即 B 与 C 交换 此时 平均交换次数为 2 3 由此可见 从 B 处翻看直到游戏结束 次数最少符合题目要求 程序清单 const n 20 var i tem r b y integer a array 1 n of 0 2 begin for i 1 to n do read a i r 1 1 y n while 2 do if 3 then begin tem a r a r a b a b tem r r 1 end else if 4 then begin tem a b a b a y a y tem 5 6 end else b b 1 for i 1 to n do write a i 3 end 8 问题描述问题描述 读入 n 个不相同且不为 0 的数 1 n 100 不用排序 求出其中第 r 个 大的数 1 r n 即有 r 1 个数比它大 其余的数都比它小 例如 输入 3 14 22 15 17 6 其中第 3 个大的数为 15 算法说明算法说明 以数组 a 1 100 记录读入的 n 个数 并以 0 结束 0 本身不是 n 个数中的数 然后从第一个数开始 将它与其余的数进行比较并记录出比它大的数的个数 存于变 量 y 中 若 y r 1 时 得到所求结果 否则对下一个数进行同样的处理 程序清单程序清单 program exp2 input output var r i j k x y integer a array 1 100 of integer p boolean begin j 0 readln x while do begin a j x end readln r p true i 1 while p do begin y 0 for k 1 to j do if x y do begin r r y q q 1 end 结果 商在 q 中 余数在 r 中 算法说明 上面的算法有一个缺点 就是当 x 比较大 y 比较小时 则运算的次数非常 多 速度太慢 为提高速度 下面给出改进的算法 先找一个非常接近 x 的数 w 且满 足 w y 2k y 2 k 1 x w 然后通过减法与移位的运算 以较少的运算次数完成除法 程序清单 program exp3 input output var x y w r q integer begin readln x r x while w w then begin r end end writeln q r end 10 问题描述 一个正整数 非素数 可表示成它的因子 1 与其本身除外 的乘积 例如 12 有因子 2 3 4 6 所以可表示为 12 2 2 3 4 3 2 6 给出任一个正整数 N 求出它所有的因子乘积的表达式 交换律得出的不同式子算 同一种 算法说明 读入一个整数 N 首先求出它的所有的因子以及每个因子可能的次数 例如 整数 48 因子 2 3 4 6 8 12 16 24 次数 4 1 2 1 1 1 1 1 将上面的结果存入数组A ARRAY 0 20 1 2 中 其中 A 1 表示因子 A 2 表示次 数 然后用简单回溯的方法求出所有可能的表示 数组 B 0 20 记录取数情况 C ARRAY 0 20 工作单元 程序清单 program exp4 input output var a array 0 20 1 2 of integer c b array 0 20 of integer n m i j s k l integer begin writeln readln n for i 1 to 20 do a i 1 0 a 0 2 1 j 0 for i 2 to n 1 do begin s 0 m n while m0 and m mod i 0 do begin m m div i end if then begin j j 1 a j 2 end end for i 0 to j do b i 0 while b 0 0 do begin k j while do k k 1 b k b k 1 for l do b l 0 s 1 for i 1 to j do if b i 0 then for l 1 to b i do if s n then begin for i 1 to j do c i b i write m 1 for i 1 to j do while c i 0 and mn do begin m m a i 1 if m n then write a i j else begin write a i 1 c i c i 1 end end writeln end end end 11 问题描述 输入一长度不超过 80 个字符的字符串 称为源串 该字符串由小写英 文字母 空格组成 并以 结束 单词是由连续字母组成 两个单词之间至少有一个空格 本程序的功能为 首先找出字符串中所有单词并保留一个空格作为单词分隔 存入数组 ch 中 然后用键盘输入一个待查找的单词 以字符 结束 采用顺序查找的方法在 ch 中 进行查找 若找到 则输出该单词在 ch 中出现的序号 若有多个位置出现该单词 则只 输出第一个序号位置 若不存在 则输出 NOT FOUND 程序清单 program exp1 var a b ch array 1 80 of char i j k n m integer begin n 0 repeat 1 read a n until a n readln k 0 for i 1 to n do if a i a and a i z then begin k k 1 2 end else if k0 then if ch k 表示一个空格 以下同 then begin k k 1 ch k end m 0 3 repeat m m 1 read b m until 4 i 1 j 1 k 1 b m while i n and j m do begin if 5 then begin i i 1 j j 1 end else begin while ch i do 6 i i 1 j 1 k k 1 end end if 7 then writeln k 4 else writeln not found end 12 问题描述 下面程序的功能是从键盘读取 A B 数组的元素 A B 数组均已从小 到大排好序 无相同元素 现将 A B 合并为数组 C 同样要求数组 C 也是从小到大排 好序 有相同元素时只保留一个 程序中 N 表示数组A B 的长度 i j k 分别表示数组A B C 的取数或存数的指 针 程序清单 program excp3 const n 8 m 2 n type arr1 array 1 n of integer arr2 array 1 m of integer var a b arr1 c arr2 i j k integer procedure copy x arr1 var y arr2 var i j integer begin i i 1 y i x j j j 1 end begin for i 1 to n do read a i readln for i 1 to n do read b i readln i 1 j 1 while do if a i b j then copy a c k i else if b j a i then copy b c k j else begin copy a c k i end while do copy a c k i while do copy b c k j for i 1 to k do write c i 4 writeln end 13 问题描述 将 2n个 0 和 2n 个 1 排成一圈 从任一个位置开始 每次按逆时针的 方向以长度为 n 1 的单位进行数二进制数 要求给出一种排法 用上面的方法产生出来的 2 个二进制数都不相同 例如 当 n 2 时 即 个 0 和 个 1 排成如下一圈 比如 从 A 位置开始 逆时针方向取三个数 000 然后再从 B 位置上开始取三个数 001 接着从 C 开始取三个数 010 可以得到 000 001 010 101 011 111 110 100 共 8 个二进制数且都不相同 程序说明 以 n 4 为例 即有 16 个 0 16 个 1 数组 a 用以记录 32 个 0 1 的排法 数组 b 统计二进制数是否已出现过 程序清单 program noi00 var a array 1 36 of 0 1 b array 0 31 of integer i j k s p integer begin for i 1 to 36 do a i 0 for i 28 to 32 do a i 1 p 1 a 6 1 while p 1 do begin j 27 while a j 1 do j j 1 for i j 1 to 27 do for i 0 to 31 do b i 0 for i 1 to 32 do begin for k i to i 4 do s s 2 a k end s 0 for i 0 to 31 do s s b i A 0 0 1 0 1 1 1 0 if then p 0 end for i 1 to 32 do for j i to i 4 do write a j writeln end 14 多项式的乘法 问题描述 例如有如下多项式 P X 2X2 X 1 Q X X 1 则 P X Q X 2X2 X 1 X 1 2X3 X2 1 程序说明 多项式的表示 系数 指数 如上例中 P X 系数 指数 Q X 系数 指数 2 2 1 1 1 1 1 0 1 0 0 0 0 0 PXQ 的结果存入 C 中 其输出格式是 依次用一对括号内的 系数 指数 分别来 表示 如上例的输出结果表示为 2 3 1 2 1 0 程序清单 program noi 007 var i j k l jp jq jc x y x1 y1 integer p q array 1 10 1 2 of integer c array 1 20 1 2 of integer begin jp 0 readln x y while x0 do begin jp jp 1 p jp 1 x p jp 2 y readln x y end jq 0 readln x y while x0 do begin jq jq 1 q jq 1 x q jq 2 y readln x y end jc 1 c jc 1 0 c jc 2 1000 for i 1 to jp do begin y p i 2 for j 1 to jq do begin y1 y q j 2 k 1 while y1 c k 2 do k k 1 if y1 c k 2 then else begin for l jc downto k do begin c l 1 1 c l 1 c l 1 2 c l 2 end c k 1 x1 c k 2 y1 end end end for i 1 to jc do if then write c i 1 c i 2 readln end 15 输入 n 个 0 到 100 之间的整数 由小到大排序输出 每行输出 8 个 程序清单 program chu7 5 var i j k n x integer b array 0 100 of integer begin readln n for i 0 to 100 do b i 0 for i 1 to n do begin readln x b x end for i 0 to 100 do while do begin write k k 1 b i b i 1 if then writeln end readln end 16 问题描述 在 A B 两个城市之间设有 N 个路站 如下图中的 S1 且 N 100 城 市与路站之间 路站和路站之间各有若干条路段 各路段数 20 且每条路段上的距离均 为一个整数 A B 的一条通路是指 从 A 出发 可经过任一路段到达 S1 再从 S1 出发经过任一 路段 最后到达 B 通路上路段距离之和称为通路距离 最大距离 1000 当所有的 路段距离给出之后 求出所有不同距离的通路个数 相同距离仅记一次 例如 下图所示是当 N 1 时的情况 从 A 到 B 的通路条数为 6 但因其中通路 5 5 4 6 所以满足条件的不同距离的通 路条数为 5 算法说明 本题采用穷举算法 数据结构 N 记录 A B 间路站的个数 数组 D I 0 记录第 I 1 到第 I 路站间路段的个数 D I 1 D I 2 记录每个路段距离 数组 G 记录可取到的距离 程序清单 program chu7 6 var i j n s integer b array 0 100 of integer d array 0 100 0 20 of integer g array 0 1000 of 0 1 begin readln n for i 1 to n 1 do begin readln d i 0 for j 1 to d i 0 do readln d i j end d 0 0 1 for i 1 to n 1 do b i 1 b 0 0 for i 0 to 1000 do g i 0 while do begin s 0 for i 1 to n 1 do s g s 1 j n 1 while do j j 1 b j b j 1 for i j 1 to n 1 do b i 1 end s 0 for i 1 to 1000 do writeln s readln end 17 问题描述 将 n 个整数分成 k 组 k n 要求每组不能为空 显然这 k 个部分均可 得到一个各自的和 s1 s2 sk 定义整数 P 为 P S1 S2 2 S1一 S3 2 S1 Sk 2 s2 s3 2 Sk 1 Sk 2 问题求解 求出一种分法 使 P 为最小 若有多种方案仅记一种 程序说明 数组 a 1 a 2 A N 存放原数 s 1 s 2 s K 存放每个部分的和 b 1 b 2 b N 穷举用临时空间 d 1 d 2 d N 存放最佳方案 程序 program exp4 var i j n k integer a array 1 100 of integer b d array 0 100 of integer s array 1 30 of integer begin readln n k for i 1 to n do read a i for i 0 to n do b i 1 cmin 1000000 while b 0 1 do begin for i 1 to k do for i 1 to n sum 0 for i 1 to k 1 do for j do sum sum s i s j s i s j if then begin cmin sum for i 1 to n do d i b i end j n while do j j 1 b j b j 1 for i j 1 to n do end writeln cmin for i 1 to n do write d i 40 writeln end 18 问题描述 工厂在每天的生产中 需要一定数量的零件 同时也可以知道每天生产 一个零件的生产单价 在N 天的生产中 当天生产的零件可以满足当天的需要 若当天用 不完 可以放到下一天去使用 但要收取每个零件的保管费 不同的天收取的费用也不相 同 问题求解 求得一个N 天的生产计划 即N 天中每天应生产零件个数 使总的费用最 少 输入 N 天数 N 29 每天的需求量 N 个整数 每天生产零件的单价 N 个整数 每天保管零件的单价 N 个整数 输出 每天的生产零件个数 N 个整数 例如 当 N 3 时 其需要量与费用如下 第一天第二天第三天 需要量251530 生产单价203032 保管单价5l00 生产计划的安排可以有许多方案 如下面的三种 第一天第二天第三天总的费用 25153025 2O 15 30 30 32 1910 4003040 20 15 5 30 32 1835 700070 20 45 5 30 10 1925 程序说明 b n 存放每天的需求量 c n 每天生产零件的单价 d n 每天保管零件的单价 e n 生产计划 程序 program exp5 var i j n yu j0 j1 s integer b c d e array 0 30 of integer begin readln n for i 1 to n do readln b i c i d i for i 1 to n do e i 0 10000 c n 2 0 b n 1 0 jo 1 while jo n do begin yu c j0 j1 jo s b j0 while do begin j1 j1 1 s s b j1 end j0 j1 1 end for i 1 to n do readln end 19 一元二次方程 题目描述 方程 ax2 bx c 0 要求给出它的实数解 输入 三个实数 a b c 是方程的三个系数 a 0 输出 如果无实数解 则输出 No solution 如果有两个相等的实数解 则输出其中一个 四舍五入到小数点后面 3 位 如果有两个不等的实数解 则解与解之间用逗号隔开 同样要四舍五入到小数 点后 3 位 输入样例 l 2 1 输出样例 1 000 程序 program program41 var a b c m real begin read a b c m b b 4 a c if then begin write 0 3 write write 1 b sqrt m 2 a 0 end else if then write else begin write no solution end end 20 翻硬币 题目描述 一摞硬币共有 m 枚 每一枚都是正面朝上 取下最上面的一枚硬币 将它 翻面后放回原处 然后取下最上面的 2 枚硬币 将他们一起翻面后再放回原处 再取 3 枚 取 4 枚 直至 m 枚 然后再从这摞硬币最上面的一枚开始 重复刚才的做法 这 样一直做下去 直到这摞硬币中的每一枚又都是正面朝上为止 例如 m 为 1 时 翻两 次即可 m 为 2 时 翻 3 次即可 m 为 3 时 翻 9 次即可 m 为 4 时 翻 11 次即可 m 为 5 时 翻 24 次即可 m 为 30 时 翻 899 次即可 输入 仅有的一个数字是这摞硬币的枚数 m 0 m 1000 输出 为了使这摞硬币中的每一枚又都是正面朝上所必需翻的次数 输入样例 30 输出样例 899 程序 program programl var m integer function solve m integer integer var i t d integer flag boolean begin if m 1 then so1ve else begin d 2 m 1 t 2 i 1 flag false repeat if t 1 then begin solve flag true end else if then begin solve i m 1 flag true end else t i i 1 until flag end end begin read m if m 0 and m 1000 then writeln end 21 Joseph 题目描述 原始的Joseph问题的描述如下 有n个人围坐在一个圆桌周围 把这n个人依 次编号为1 n 从编号是1的人开始报数 数到第m个人出列 然后从出列的下一个 人重新开始报数 数到第m个人又出列 如此反复直到所有的人全部出列为止 比 如当n 6 m 5的时候 出列的顺序依次是5 4 6 2 3 1 现在的问题是 假设有k个好人和k个坏人 好人的编号的1到k 坏人的编号是k 1到 2k 我们希望求出m的最小值 使得最先出列的k个人都是坏人 输入 仅有的一个数字是k 0 k c b c a c a b 表示三角形三边的边长 输出 三角形内切圆的面积 结果四舍五入到小数点后面2位 输入样例 3 4 5 输出样例 3 14 程序 program program1 var a b c r s t real begin read a b c s 2 t s s a s b s c r t s writeln 3 1415927 r 0 end 23 上楼梯 问题描述 设有一个 n 级的楼梯 1 n 12 编号从下到上依次为 1 至 n 其中有若 干级为坏的 有一个人上楼梯时一步可走 1 级 或 2 级 或 3 级 坏级只能跨过不能踏 上 但级数照算 问 这个人从楼下走到第 n 级 共有多少种不同的走法 例如 当 n 1 时 无坏级的情况 仅有 1 种走 法 当 n 2 时 无坏级的情况 有 1 级 1 级 或 2 级 共 2 种走法 当 n 3 时 第二级为坏级的情况 有 1 级 2 级 直接 3 级 共 2 种走法 程序说明 用递推方法求解 用集合记录坏级 程序清单 program cup 5 var x i n f1 f2 f3 f4 longint s set of 0 30 begin readln n s readln x x 坏级 以 0 结束 while x0 do begin s readln x end if 1 in s then f1 0 else f1 1 if 2 in s then f2 0 else f2 if 3 in s then f3 0 else f3 1 f1 f2 if n 1 then f4 f1 else i