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时有
GCD(x,y)=GCD(y,x mod y)，如此便可把原问题转化为求两个更小数的最大公约数，直到其中一个数为0，剩下的另外一个数就是两者的最大公约数。以求288和123的最大公约数为例，操作如下：288mod123=42123mod42=3942mod39=339mod 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，求它们的最大公约数和最小公倍数。
输入格式
输入数据仅有一行包含两个用空格隔开的正整数a,b，范围不超过长整型longint。
样例输入
1216
输出格式
输出数据仅有一行包含两个整数，表示要求的最大公约数和最小公倍数。两数之间严格用一个空格隔开，行末没有多余的空格。
样例输出
448
以下是源程序，存盘文件名为gcdlcm.pas
var m,n,a,b,r:longint;
begin
read(m,n);
a:=m;
b:=n;
while b<>0do
begin
r:=a mod b;
a:=b;
b:=r;
常州程序员培训机构
end;
writeln(a,'',m*n div a);
end.
以下是源程序，存盘文件名为gcdlcm.cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
int m,n,a,b,r;
cin>>m>>n;
a=m;
b=n;
while(b!=0){
r=a%b;
a=b;
b=r;
}
cout<<a<<""<<m*n/a<<endl;
return0;
}
小X与机器人(robot)
问题描述
小X的老师很喜欢围棋。众所周知，围棋的棋盘有19行19列，共有361个交叉点。为方便起见，我们把这些行列按顺序编号为1～19，并用(x,y)表示第x列第y行的位置。例如下图中，A用(16,4)表示，B用(14,3)表示。
小X在做一个机器人的项目，他正思考这样一个问题：如果一个小机器人从(x1,y1)这个位置出发，沿
直线移动到(x2,y2)这个位置，它一共经过了多少个交叉点？
注意起点和终点也算作经过，因此至少经过了2个交叉点。
输入格式
输入数据仅有一行包含4个用空格隔开的正整数，分别表示x1,y1,x2,y2
输出格式
输出一行包含一个小于20的正整数，表示从(x1,y1)沿直线移动到(x2,y2)经过的交叉点的个数。
样例输入1
44416
样例输出1
13
样例输入2
111919
样例输出2
19
样例输入3
1175
样例输出3
3
样例解释3
经过了(1,1),(4,3),(7,5)共3个交叉点，你在图上画条直线就能一目了然看出来。
数据范围
对于20%的数据，x1=x2
对于另外20%的数据，y1=y2
对于另外30%的数据，满足abs(x1-x2)=abs(y1-y2)，它们是某个正方形的两个对角顶点对于100%的数据，1<=x1,y1,x2,y2<=19

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。