没有合适的资源?快使用搜索试试~ 我知道了~
2018常州市程序设计小能手比赛试题.pdf
需积分: 12 10 下载量 20 浏览量
2020-12-02
09:47:55
上传
评论 1
收藏 221KB PDF 举报
温馨提示
试读
10页
2018常州市程序设计小能手比赛试题 常州市中小学C++比赛试题 涉及 if else,单循环,嵌套循环,一维数组和二维数组
资源推荐
资源详情
资源评论
2018 年常州市“程序设计小能手”比赛说明
在 D 盘根目录下建一个以自己的中文名字命名的文件夹如“丁宁”,活动结束前将你编的
所有程序(扩展名为 cpp 或 pas)放到该文件夹中等待工作人员上传到教师机。如果你同
时会用两种或两种以上语言编程,每个程序你都可以任选一种语言完成,你提交的全部
源程序不必都是同一种语言。明年将不再允许使用 Pascal 语言!
一般说来前面的题要比后面的容易,后面的题目虽然得到满分很难,然而拿一部分分数
并不难。请合理分配你的时间,先保证程序的正确性,超时等问题都是次要的,计算机
的运行速度往往比你想象的要快得多。如果某题不太会做你可以针对小数据编程争取拿
部分分数,哪怕手算一个结果输出也行,比赛总是有难度的,不能像平时学校里的小测
验那样老想着拿满分,从往年的经验来看你能得到总分的 1/4 就相当不错了。
所有测试点时限都是 1 秒,所有程序运行时内存都不能超过 256MB,大约可以存储六千万
个长整型数。每题一般有 10 个或 20 个测试点,除非特别说明,每题的满分均为 100 分。
输出时行首和行尾都不要有多余的空格,也不要有多余的空行,相邻两项输出之间严格
用一个空格隔开,最后一项输出之后没有空格,一行输出结束时一定要换行。
程序名在题目后面的括号中,千万不能起错名字。所有题目均使用标准输入输出,即从
键盘输入数据,结果输出到屏幕,请认真阅读范例,你的程序请严格按范例程序的格式
编写。
题目中用到的“∧”符号表示乘方运算,如 2^3=2*2*2=8,10^6=1000000
【范例】最大公约数和最小公倍数(gcdlcm.cpp 或 gcdlcm.pas)
问题描述
最大公约数(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 时有 GCD(x, y)= GCD(y, x mod y),如此便可把原问题转化为求两个更小
数的最大公约数,直到其中一个数为 0,剩下的另外一个数就是两者的最大公约数。以求 288 和 123 的最
大公约数为例,操作如下: 288 mod 123=42 123 mod 42=39 42 mod 39=3 39 mod 3=0
所以 3 就是 288 和 123 的最大公约数。
计算最小公倍数时,通常会借助最大公约数来辅助计算。可以证明两个自然数的乘积等于它们的最大
公约数和最小公倍数的乘积,即 a*b=GCD(a,b)*LCM(a,b)。如 12*16=192= GCD(12,16)*LCM(12,16)=4*48。
编一个程序对于输入的两个自然数 a,b,求它们的最大公约数和最小公倍数。
资源评论
chenxiaohua
- 粉丝: 81
- 资源: 25
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功