搜尋此網誌

2011年7月28日 星期四

ACM-light, more light problem

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:

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;
}

}