According to the "Mathematical Induction", we found out that when the serial are 1,4,9,16 ...the final bulb is on ,which means that number has a square root . On the other hand, besides those numbers, the bulb is off. Therefore , following is my Java solution:
網頁
BloggerAds 廣告
標籤
- Java (96)
- Android (27)
- 演算法 (21)
- c++ (19)
- JavaScript (7)
- OpenMp (6)
- Design Pattern (4)
- 日文歌曲 (4)
- 資料結構 (4)
- Foundation Knowledge Of Programming (3)
- QUT (2)
- CodingHomeWork (1)
- Database (1)
- 英文歌詞 (1)
搜尋此網誌
2011年7月28日 星期四
ACM-Greatest Common Denominator
It is a Java based solution. The operation is dividing the two numbers mutually until one of them equals zero. The green part is the main mechanism .
package acm;
import java.io.*;
import java.util.*;
public class GCD {
public static void main(String[] args) throws IOException {
ArrayList<String> userInput = new ArrayList<String>();
while (true) {
int intCases = 0;
System.out.println("How many test cases to run?(from 1 to 1000)?");
BufferedReader bs = new BufferedReader(new InputStreamReader(
System.in));
String cases = bs.readLine();
intCases = Integer.parseInt(cases);
if (intCases < 1 || intCases > 1000) {
System.out.println("Please enter a valid number!!");
} else {
System.out.println("Please enter 2 numbers m and n,separate them by dot.");
System.out.println("ex: 12,60");
while (intCases != userInput.size()) {
userInput.add(bs.readLine());
}
break;
}
}
Iterator it=userInput.iterator();
while(it.hasNext()){
String numbers=(String)(it.next());
int[] ns=getInts(numbers);
System.out.println(gcd(ns[0],ns[1]));
}
}
public static int gcd(int a, int b) {
while (a != 0 && b != 0) {
if (a > b)
a %= b;
else
b %= a;
}
if (a == 0)
return b;
else
return a;
}
public static int[] getInts(String str){
int totalNumbers=str.split(",").length;
int[] ints=new int[totalNumbers];
for(int i=0;i<totalNumbers;i++){
ints[i]=Integer.parseInt(str.split(",")[i]);
}
return ints;
}
}
訂閱:
文章 (Atom)
我的網誌清單
標籤
日文歌曲
(4)
股市
(7)
股票
(9)
英文歌詞
(1)
時事
(1)
硬體(hardware)
(1)
資料結構
(4)
演算法
(21)
數學(Math)
(4)
ACM
(3)
ajax
(7)
algorithms
(1)
Android
(27)
Blog Notes(部落格記事)
(6)
C
(9)
c++
(19)
CodingHomeWork
(1)
Database
(1)
Design Pattern
(4)
Foundation Knowledge Of Programming
(3)
GWT
(1)
How
(2)
J2EE
(1)
Java
(96)
Java語言
(4)
JavaScript
(7)
Leetcode
(4)
LOL
(1)
OpenMp
(6)
QUT
(2)
Uva
(2)
Yahoo知識問答
(11)