2017常州市程序设计小能手比赛试题
需积分: 5 22 浏览量
2023-05-06
15:41:30
上传
评论
收藏 241KB PDF 举报
2017 年常州市“程序设计小能手”比赛说明
在 D 盘根目录下建一个以自己的中文名字命名的文件夹如“丁宁”，活动结
束前将你编的所有程序(扩展名为 pas)放到该文件夹中等待工作人员上传到
教师机。如果你同时会用两种或两种以上语言编程，每个程序你都可以任选
一种语言完成，你提交的全部源程序不必都是同一种语言。
一般说来前面的题要比后面的容易，后面的题目虽然得到满分很难，然而拿
一部分分数并不难。请合理分配你的时间，先保证程序的正确性，超时等问
题都是次要的，计算机的运行速度往往比你想象的要快得多。如果某题不太
会做你可以针对小数据编程争取拿部分分数，哪怕手算一个结果输出也行，
比赛总是有难度的，不能像平时学校里的小测验那样老想着拿满分，从往年
的经验来看你能得到总分的 1/4 就相当不错了。
所有测试点时限都是 1 秒，所有程序运行时内存都不能超过 256MB，大约可
以存储六千万个长整型数。每题一般有 10 个或 20 个测试点，除非特别说明，
每题的满分均为 100 分。
输出时行首和行尾都不要有多余的空格，也不要有多余的空行，相邻两项输
出之间严格用一个空格隔开，最后一项输出之后没有空格，一行输出结束时
一定要换行。
程序名即为题目的英文名，所有题目均使用标准输入输出，即从键盘输入数
据，结果输出到屏幕，请认真阅读试机文件夹中的 word 文档“说明.doc”，
你的程序请严格按范例程序的格式编写。
【范例】
最大公约数和最小公倍数(gcdlcm)
问题描述
最大公约数(Greatest Common Divisor，简写为 GCD)：如果有一个自然数 a 能被自然
数 b 整除(也称 b 能整除 a，记作 b|a)，则称 a 为 b 的倍数，b 为 a 的约数。两个自然数公
共的约数，叫做这两个自然数的公约数。公约数中最大的一个公约数，称为这两个自然数的
最大公约数。最小公倍数(Least Common Multiple，缩写 LCM)：对于两个整数来说，最小
公倍数是指这两个数公共的倍数中最小的一个。例如： 在 12 和 16 中，4 就是 12 和 16 的
最大公约数。12 和 16 的最小公倍数是 48。
早在公元前 300 年左右，欧几里得就在他的著作《几何原本》中给出了求最小公倍数的
高效方法——辗转相除法。辗转相除法使用到的原理很聪明也很简单，假设用 GCD(x, y)表
示 x，y 的最大公约数，取 k = x div y，b = x mod y，则 x = ky + b，如果一个数能够同
时整除 x 和 y，则必能同时整除 b 和 y；而能够同时整除 b 和 y 的数也必能同时整除 x 和 y，
即 x 和 y 的公约数与 b 和 y 的公约数是相同的，其最大公约数当然也相同，则当 y<>0 时有
剩余12页未读，继续阅读
资源评论
