北京航空航天大学2014第五次上机解题报告
2014第五次上机解题报告
--------by14211065于济凡
写在前面：
上机题目有时需要投入大量时间进行练习，在某些情况下也可能带来突发的创新想法；因此无需过分关注结果如何；毕竟我们最终的目标都是为了提升自身的技能水平以及实现个人的成长与进步。
第一题：jhljx学gcd
ProblemDescription
众所周知, gcd代表的是最大公约数的概念。jhljx为了进一步掌握知识的深度,决定从今天起开始系统地学习这一知识点。他计划计算n个数值的最大公约数值和最小公倍数值,希望通过自己的努力能够完全掌握这一知识点并取得理想的学习效果,如果您能给予帮助与支持,将不胜感激
Input
读取多组数据。每组数据由两部分组成：第一部分为一行包含一个介于2到20之间的正整数n（其中n表示该数据集中的元素数量），第二部分为一行包含n个正整数（这些数字之间由空格分隔开）。
Output
输出这n个数共同的最大公约数和最小公倍数（保证结果在int范围内）。
SampleInput
2
9 15
3
24 60 18
SampleOutput
345
6 360
如果说仅就比较与计算两个数字的最大公约数与最小公倍数而言，这对于那些掌握了函数与递归知识的同学们来说倒算易事；但对于要处理多个数字的情况而言，这确实是一个挑战。因此，在深入探讨相关算法之前，请让我们先系统地复习一下三个或更多数字的最大公约数与最小公倍数的求解方法。
比如：24,60,18
为了计算最大公约数（GCD），可采用先计算24与60的最大公约数（GCD），接着计算该结果12与18之间的最大公约数（GCD），最终得出结果为6。
求最小公倍数可以采取先求24与60的最小公倍数120，再求120与18的最小公倍数，得到180.
可以看出，在计算一组多个数字的最大公约数目和最小公倍数目时
于是，代码如下：
#include
using namespace std;
int gcd(int m,int n)
{
int r;
r=m%n;
if(r==0)
return n;
else
return gcd(n,r);
}
int lcm(int p,int q)
{
return p*q/gcd(p,q);
}
int main()
{
int counter;
int x,y,z,x1,y1,z1;
int gcdx,lcmx;
while(cin>>counter)
{
cin>>x>>y;
x1=x;
y1=y;
gcdx=gcd(x,y);
lcmx=lcm(x1,y1);
for;counter>=3;counter--)
{
cin>>y;
y1=y;
x=gcdx;
gcdx=gcd(x,y);
x1=lcmx;
lcmx=lcm(x1,y1);
}
cout<<gcdx<<" "<<lcmx<<endl;
}
}
第二题：jhljx学素数
ProblemDescription
函数是一个重要的知识点概念。JHLJX玩得非常嗨而不按常理出牌,来点清新脱俗的小花式操作。
他让你编写程序完成对某个数字是否为质数的分析。
Input
输入多组数据。
输入一个非负整数n。(保证n在long long范围内,但不会很大)
Output
当该数值为质数时返回'jhljx isgood!'；否则返回'jhljxis sangxinbingkuang!'
SampleInput
1
2
SampleOutput
jhljxis sangxinbingkuang!
jhljx is good!
Hint
本题会检查代码，不用函数实现的一律 0分。
本题是课本原题，见课本214页6.29
首先，这道题目与书后练习题高度一致；至于第二个问题，请不要过于苛责；考虑到我们曾参加过2014级第一次练习E中的类似素数判断问题。
不过这个题目还有一点，那就是要求用函数实现
那么具体如何实现呢？
判定一个整数n是否为素数时，只需确保检查所有小于等于√n的正整数值即可（那为什么不直接检查到n呢？因为它可能导致计算超时）
所以规避了超时的陷阱之后，这道题可能就基本做出来了。
#include
#include
#include
using namespace std;
int sushu(long long x)
{
if(x==1)
{
printf("jhljx is sangxinbingkuang!\n");
}
else
{
int sum=0;
for(long long i=1;i<=sqrt(x);i++)
{
if(x%i==0)
{
sum=sum+1;
}
}
if(sum==1)
{
printf("jhljx is good!\n");
}
else
{
printf("jhljx is sangxinbingkuang!\n");
}
}
}
int main()
{
long long x;
while(cin>>x)
{
sushu(x);
}
}
通过这道题我们可以获得一个至关重要的启示，在后续的问题中这一重要启示仍然具有实用性。具体来说，在设计算法时需要特别注意将复杂的计算过程进行简化处理。如果未能做到这一点的话——这会导致系统运行效率低下甚至无法及时响应。
第三题：jhljx学下棋
ProblemDescription
jhljx热衷于下棋，并计划与Last_Day进行下一盘对弈。Last_Day提供了一个n×n大小的棋盘。为了策略性地布局，在此棋盘上，jhljx决定布设若干个小兵。当一个小兵被放置在坐标为（x,y）的位置时，在其周围四个相邻的位置（即（x-1,y）、（x+1,y）、（x,y-1）、（x,y+1）），如果存在其他棋子，则会被视为被攻击的目标。为了最大化布局的有效性，在不导致任何两个小兵互相攻击的前提下，请问最多能布设多少个小兵？
Input
输入多组数据。
每组数据一行，为一个数n。(保证n在int范围内)
Output
输出最多可放置的小兵的个数。
SampleInput
1
2
3
SampleOutput
1
2
5
这道题不算很难 但仔细琢磨确实大有裨益 例如 它主要考察的是基本的奇偶性分析
就难度而言 这道题不算很高 但它确实值得一思 例如 它的主要解法就是基于经典的奇偶判断
虽然说 这道题不算很难 但它确实值一读 例如 其解法的核心就是基本的奇偶性分析
虽然说 这道题不算很难 它确实值一看 例如 其主要解法就是基于经典的奇偶判断方法
采用了奇偶性的判断方法，并在此基础上完成了后续的基本运算。通过观察和分析可以看出这些数字的变化规律：当n为奇数时，结果等于(n² + 1)/2；当n为偶数时，则结果等于n² / 2。
但是这样就结束了吗？万万没那么简单，这回如果只用int，则会出现WA。
那么问题出在哪里呢？在对两个int类型数值进行相乘运算时，其乘积可能会超出int类型的存储范围。因此为了正确解答这个问题，请确保在计算中使用long long类型变量以避免溢出情况的发生。
代码如下：
#include
using namespace std;
int main()
{
long long n;
long long k;
while(cin>>n)
{
if(n%2==1)
{
k=(n*n+1)/2;
cout<<k<<endl;
}
else
{
k=n*n/2;
cout<<k<<endl;
}
}
}
这道题又一次为我们提供了深刻的启示：经过算法的深入思考后必须考虑数值是否会超出定义数据范围而导致错误。
第四题：jhljx的强迫症
ProblemDescription
Input
Output
SampleInput
SampleOutput
Hint
**3** **1** **4** **2** **0** **3**这道题再次是一道考察数学想法的题目；如何在两个数的倍数与模运算中获得从1到m-1的所有整数值呢？
可能有人会想到数组，保存一个又一个数据，然后判断。。。
但是，这么做会惊讶地发现，这一定会超时间很久。
所以一定有什么简单算法的。
我们来观察一下，如果是3和8，会出现所有的数吗？
3%8==3,
3*2%8=6
3*3%8=1
3*4%8=4
。。。
貌似可以，这是为什么呢？
那我们再来看看，如果是6和8呢?
那么貌似是：
6%8=6
6*2%8=2
6*3%8=2
。。。
为什么一个奇数都没有呢？
哦！原来是因为6和8有最大公约数2，所以每次得出的结果都至少是加2！
所以，只要判断两个数是否互质就好啦！（互质不就是最大公约数为1嘛！）
于是，代码如下：
#include
using namespace std;
int gcd(int x,int y)
{
if(y==0)
{
return x;
}
else
{
return gcd(y,x%y);
}
}
int main()
{
int n,m,k;
while(cin>>n>>m)
{
k=gcd(n,m);
if(k==1)
{
cout<<"jhljxshidadoubi"<<endl;
}
else
{
cout<<"shuishuowoshidadoubi"<<endl;
}
}
}
从解答这道题中能获得哪些启发？无需过分焦虑，请仔细思考这个问题。仅此一例的提示作用足以说明问题。后续还有更多题目需要解答。
第五题：汉诺塔再度来袭
ProblemDescription
Hanoi Tower problem, also known as the Tower of Hanoi, is a classic益智玩具 originating from an ancient Indian legend. The Great梵天 created the world by setting up three diamond pillars, each with 64 golden discs stacked from bottom to top in ascending order on one pillar. Great梵天 commanded Brahmagupta to move the discs from the original column to another column, maintaining their size order. The rules specify that no disc may be placed upon a smaller disc and that only one disc can be moved at a time between any two pillars.
假定三根柱分别为A、B、C。共有n个大小不一的圆盘..., 按从最小到最大依次叠放于A柱上。最大的圆盘位于底部, 最小的圆盘位于顶端.
Input
输入多组数据。
每组数据一个n,表示黄金圆盘的个数。(1<=n<=20)
Ouput
输出需要移动的步骤及其详细方案。例如1\ A\rightarrow C表示将第1个盘从A柱移至C柱。
SampleInput
1
2
SampleOutput
1
1 A->C
3
1 A->B
2 A->C
1 B->C
Hint
Sample 1：输出结果1中A到C的字符间存在一个空格
汉诺塔问题作为演示为递归算法的核心问题而闻名，在本次上机考试题目中再次出现
如果读者是之前参加过练习赛或者是去年第四次上机的同学，则他们对于汉诺塔应该已经比较熟悉了。为了帮助大家更好地理解该问题，在这里将详细讲解解决汉诺塔问题的基本原理：
首先有三个柱子：A，B，C
将n个盘子从初始柱子移到最终柱子，一共分三步：
1. 将前n-1个盘子从初始柱子A移到中间柱子B
2. 将第n个盘子从初始柱子A移到最终柱子C
3. 将前n-1个柱子从中间柱子移到最终柱子C
注意：全过程中使用递归方法。为了表示前n-1个盘子的移动过程,需要先解决n-2的情况,直至只剩下单个盘子时,就可以直接从A移到C即可。
这是最为经典的递归问题！一定要搞懂呀！
然后计算次数：
既然每一次都包括n-1个盘子的移动的两倍加一。。。那么。。。数学规律就来了。。。
移动n个盘子需要2的n次方减一次！！
于是，代码如下：
#include
#include
#include
#include
using namespacestd;
int f(int n,charstart,char over,char middle)
{
if(n==1)
{
printf("%d%c->%c\n",n,start,over);
}
else
{
f(n-1,start,middle,over);
printf("%d%c->%c\n",n,start,over);
f(n-1,middle,over,start);
}
}
int main()
{
char A='A';
char C='B';
char B='C';
int n;
while(cin>>n)
{
cout<<pow(2,n)-1<<endl;
f(n,A,B,C);
}
}
第六题：斐波那契数列
ProblemDescription
jhljx了解到你们已经学习过斐波那契数列的知识后非常高兴地宣布说"我想测试一下大家对这一知识点的理解程度"随后开始出题询问某一项的具体数值是多少。
有些人在刚开始接触这类数学问题时可能会感到有些困惑甚至完全不知道从何下手。
按照这个规律排列下去的话就是一个完整的斐波那契数列其核心特点是由前两项之和构成后续各项数值遵循着固定的递推关系式F_n=F_{n-1}+F_{n-2}其中F_0=0、F_1=1以此类推形成一个无限延伸的序列。
Input
输入多组数据。
每组数据输入一个n。
Ouput
输出斐波那契数列中的第n个数。
SampleInput
1
2
3
SampleOutput
1
1
2
Hint
这道题用递归和迭代都可以过。纯签到题
思路：参见Hint……
如果这个题不会。。。那就看书吧，书里讲的十分简单明了哦！
第七题：找不到的孩子们
ProblemDescription
这个数列具有独特性。
我们来定义一个递推关系式：对于所有n≥3，有f(n)=|f(n−1)−f(n−2)|。
已知初始值为a和b，请计算序列中的每一项。
面对这个问题时，请保持冷静：它远非表面看上去那么简单。
KamuiKirito告知我们这一序列最终将包含有限数量的不同数值。
请确定该序列中可能出现的所有不同数值的数量。
Input
输入多组数据。
每组数据为两个整数a,b，代表f(1)和f(2)。(0<=a,b<=10^18)
Output
每组数据输出一行，为会出现的数字个数。
SampleInput
21
4 6
SampleOutput
3
4
本次上机最终boss题来临！
这个题开做之前，希望你能看一下本次上机的第A,B,C,D题
得到了什么启示吗？
细细说来：
A题：本题上来就将我们带入了最大公约数问题，这是否是提示呢？
B题：这个题告诉我们小心超时，要优化算法，否则是会超时的哦。
C题：这道题教会我们在处理变量时避免因计算过程中超出数据范围而导致的问题
D题：再次使用了最大公约数的问题。
好，看看这道题怎么做！
可能会有不少学生开始就建立了一个数组 然后逐个进行条件判断 最终才发现时间不够 并想知道为什么会这样
因为要判断那么多数的话。。。4,6这样的数据还可以接受，那么100000000,1呢？
电脑会累死的。。
所以，我们来看看有没有规律可言。
首先，请输入两个数值。接着不断进行减法运算，并计算其差值的绝对值。请问直到不再产生新的数值时为止吗？
答案是，出现了0的时候。
如何使结果为零？通过观察可知，仅当之前的两个数相等时才会出现零。
等等，这像不像是“更相减损之术”呢？
这是啥？
该方法（更相减损之术）是一种不同于辗转相除法的最大公约数计算方式。为何选择该方法来解决最大公约数问题呢？因为最近在实践过程中发现这一概念频繁出现。
好，那么我们编一个直接利用更相减损，然后求循环次数不就好了？
结果发现：再次超时。
这说明我们的算法依旧不够简单。
如何才能使算法更为简洁呢？在之前的高中学习中了解了"更相减损之术"和"辗转相除法"。而最后，在选择这两种算法之一时选择了辗转相除的原因是什么呢？因为相比多次减法而言，一次除法则能显著提升效率。那么这种方法是否可行呢？
以100和40为例，正常应该是以100-40，得到60，再60-40得到20，再40-20，最后20=20，计算结束。
次数是什么呢？是不停地除法，直到等于100%40，再继续，期间经历了100/40次。。。
等等，如果是倍数呢，比如100与5呢？
那么就是100/5-1次计算
好，综上我们可以设计一个代码，大概实现这道题：
代码如下：
#include
usingnamespace std;
longlong f(long long x,long long y)
{
longlong sum=0;
while(x!=y)
{
if(x>y)
{
if(x%y!=0)
{
sum+=x/y;
x=x%y;
}
else
{
sum+=x/y-1;
x=y;
}
}
else
{
if(y%x!=0)
{
sum+=y/x;
y=y%x;
}
else
{
sum+=y/x-1;
y=x;
}
}
}
return sum;
sum=0;
}
intmain()
{
long long n,m;
while(cin>>n>>m)
{
if(m==0)
{
if(n==0)
{
cout<<"1"<<endl;
}
else
{
cout<<"2"<<endl;
}
}
else if(n==0)
{
if(m==0)
{
cout<<"1"<<endl;
}
else
{
cout<<"2"<<endl;
}
}
else
{
cout<<f(n,m)+2<<endl;
}
}
}
通过观察代码，你可以发现我这条代码还有几个补充：
我将数据范围升级为long long类型。这源于题干中给出的数值上限为10^18的需求。这得益于我在C题中积累的经验教训。
2. 我考虑到a和b中一开始就有零元素的情况，这有助于避免在执行除法运算时出现Runtime Error，因此，在初始化a和b时确保它们不包含零元素是一个明智的做法。
3. 利用函数让主函数小一点了。
如果对这个题自己能做出来，那么恭喜，你的思路一定让你有所提高~
（当然，希望大家积极说出自己的想法，大家都是最棒的）