写在正文前的几句话
????????来由: 鄙人在寒假中闲来无事, 又因自己对计算机编程颇有兴趣, 于是特地向我学习计算机的同学要了几个题做, 借此来打发时间, 不成想这几道题颇有意思, 于是在此编辑此文与诸君分享. 然我才疏学浅, 恐于文章中有些许差错, 望诸君海涵.
????????声明:由于朋友给了我一系列题目, 所以此博客应为一个专辑, 然奈何我菜鸡一枚, 又有俗事缠身, 很大概率不能按时更新. 不过, 这并不影响, 因为这些题目可问问度娘, 而且我对它们并没有多高的期待, 所以......
????????格式:?这一系列除本文外, 其他文章应该均由三部分组成, 即, 问题描述( 包含输入输出样例及其他内容 ), 思路分析, 样例代码.
正文
题目描述
给定两个正整数, 计算这两个数的最小公倍数.
输入
输入包含多组测试数据, 每组只有一行, 包括两个不大于1000的正整数.
输出
对于每个测试用例, 给出这两个数的最小公倍数, 每个实例输出一行.
?思路分析
? ? ? ? 这道题的思路比较明显了, 为方便下文叙述,不妨设每次输入的正整数分别是 a, b. 首先, 利用欧几里得算法计算出 a, b 的最大公约数( 设最大公约数为c ), 之后再计算 a*b/c 即可.
????????不过, 这里有一处小bug, 即, a*b 可能超出int的数据范围, 当然, 可以使用 long long int 来解决这个问题. 其实, 此小bug还可用一个小技巧解决, 即将表达式 "a*b/c" 改为 "a/c*b" 或 "b/c*a" , 此处利用的乘法的交换律, 这样就不会存在超出数据范围的问题了.
? ? ? ? 当然, 解决上述几个问题之后, 我们再来看一下下一个坑, 即: 如何实现多组输入. 这个问题对于许多新手可能比较困难, 因为题目一开始并未告诉我们要输入多少数据. 但是,问问度娘也是可以解决的, 然后就有了如下的解决方案.
while(cin>>a>>b)
{
...
}
? ? ? ? ?在解决完上述所有问题之后, 我们就可以打一个比较完整的程序了.
样例代码
#include<iostream>
using namespace std;
int main()
{
int a,b; //输入的两个数.
while(cin>>a>>b)
{
int a1=a,b1=b; //保存a, b的值.
int r=a1%b1;
while(r>0) //欧几里得算法.
{
a1=b1;
b1=r;
r=a1%b1;
}
cout<<a/b1*b<<endl; //计算到最后, 最大公约数一定就是b1的值.
}
return 0;
}
|