- OJ 2028 Lowest Common Multiple Plus
鏈(http://acm.hdu.edu.cn/showproblem.php?pid=2028)
問(wèn)題描述：求n個(gè)數(shù)的最小公倍數(shù)。
Input：輸入包含多個(gè)測(cè)試實(shí)例，每個(gè)測(cè)試實(shí)例的開(kāi)始是一個(gè)正整數(shù)n，然后是n個(gè)正整數(shù)。
Output：為每組測(cè)試數(shù)據(jù)輸出它們的最小公倍數(shù)，每個(gè)測(cè)試實(shí)例的輸出占一行。你可以假設(shè)最后的輸出是一個(gè)32位的整數(shù)。
2.思路：
一看到題的第一想法就是用一位數(shù)組把要求計(jì)算的數(shù)據(jù)裝進(jìn)去，然后再對(duì)它進(jìn)行遍歷窮舉?？蚣芎苋菀拙蛯?xiě)出來(lái)了，就是算法部分不知道怎么操作怎么進(jìn)行遍歷。因?yàn)檫@題不像普通的只求兩個(gè)數(shù)的最小公倍數(shù)，而是變化的數(shù)據(jù)個(gè)數(shù)，那我們熟悉的兩個(gè)數(shù)的輾轉(zhuǎn)相除法、輾轉(zhuǎn)相減法、窮舉法都沒(méi)有用了。由于算法經(jīng)驗(yàn)不是很足，想了很久一直沒(méi)有想到什么解決的辦法。通過(guò)去討論區(qū)觀摩學(xué)習(xí)了大佬的思路后，成功把問(wèn)題解決了。
3.收獲與總結(jié)：
后來(lái)想到了求最大公倍數(shù)時(shí)，是從i=1開(kāi)始遍歷的，而i可以取到n這個(gè)值（如果簡(jiǎn)單地循環(huán)for(i=0;i<n;i++)會(huì)因?yàn)閕的最初值是0而影響到后面計(jì)算最小公倍數(shù)的結(jié)果）。但是數(shù)組的定義并不能取到num[n],會(huì)導(dǎo)致數(shù)組溢出，所以報(bào)錯(cuò)了。而直接定義實(shí)際范圍給該數(shù)組。
通過(guò)學(xué)習(xí)，知道了另一種更好用的計(jì)算最小公倍數(shù)的算法。
除了去討論區(qū)，后來(lái)再去看了一下別人的筆記，發(fā)現(xiàn)他順利的實(shí)現(xiàn)了我一開(kāi)始想的方法，也明白了靈活運(yùn)用循環(huán)的重要性，他的辦法是在原本兩個(gè)數(shù)的窮舉法基礎(chǔ)上套了
個(gè)循環(huán)每次單獨(dú)求兩個(gè)數(shù)的最小公倍數(shù)，然后再用求到的最小公倍數(shù)跟后面的數(shù)繼續(xù)比較，周而復(fù)始。
4.經(jīng)過(guò)學(xué)習(xí)后的源代碼：
#include<stdio.h>
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int a=0;
int num[100];
for(int i=1;i<=n;i++){
scanf("%d",&num[i]);
if(a<num[i])a=num[i];
}
for(int i=1;i<=n;i++){
if(a%num[i]!=0){
a++;
i=0;
}
}
printf("%d\n",a);
}
return 0;
}
5.運(yùn)行結(jié)果：
