Created
October 23, 2016 12:26
-
-
Save coderodde/d546706f8fecea3b7aa39a72bff556a7 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.ArrayList; | |
import java.util.List; | |
import java.util.Scanner; | |
public class Main { | |
public static void main(String[] args) { | |
System.out.println("Starting program..."); | |
int n = readFromKeyboard(); | |
long start = System.nanoTime(); | |
List<List<Integer>> triples1 = pythagoreanTriple(n); | |
long end = System.nanoTime(); | |
System.out.printf( | |
"pythagoreanTriple(%d) in %.1f milliseconds.\n", | |
n, | |
(end - start) / 1e6); | |
start = System.nanoTime(); | |
List<List<Integer>> triples2 = pythagoreanTriple2(n); | |
end = System.nanoTime(); | |
System.out.printf( | |
"pythagoreanTriple2(%d) in %.1f milliseconds.\n", | |
n, | |
(end - start) / 1e6); | |
System.out.println("Algorithms agree: " + triples1.equals(triples2)); | |
} | |
private static int readFromKeyboard() { | |
Scanner keybInput = new Scanner(System.in); | |
return keybInput.nextInt(); | |
} | |
private static List<List<Integer>> pythagoreanTriple(int n) { | |
//List<List<Integer>> pytTri = new ArrayList<List<Integer>>(); | |
// Use diamond inference istead: | |
List<List<Integer>> pytTri = new ArrayList<>(); | |
int i, j, k; | |
for (i = 3; i < n; i++) { | |
for (j = n; j > i; j--) { | |
for (k = n; k > j; k--) { | |
if (i * i + j * j == k * k) { | |
ArrayList<Integer> tempArray = new ArrayList<Integer>(); //we create a list of integers | |
tempArray.add(i); | |
tempArray.add(j); | |
tempArray.add(k); | |
pytTri.add(tempArray); | |
} | |
} | |
} | |
} | |
return pytTri; | |
} | |
private static List<List<Integer>> pythagoreanTriple2(int n) { | |
List<List<Integer>> pytTri = new ArrayList<>(); | |
for (int i = 3; i < n; i++) { | |
int iSquared = i * i; | |
for (int j = n; j > i; j--) { | |
int iSquaredPlusJSquared = iSquared + j * j; | |
for (int k = n; k > j; k--) { | |
if (iSquaredPlusJSquared == k * k) { | |
List<Integer> result = new ArrayList<>(3); | |
result.add(i); | |
result.add(j); | |
result.add(k); | |
pytTri.add(result); | |
} | |
} | |
} | |
} | |
return pytTri; | |
} | |
private static void printResult(List<List<Integer>> resultList) { | |
for (List<Integer> ls : resultList) { | |
for (Integer i : ls) { | |
System.out.print(i); | |
System.out.print(" "); | |
} | |
System.out.println(";"); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment