Created
December 29, 2011 18:43
-
-
Save danielfariati/1535513 to your computer and use it in GitHub Desktop.
À pedidos de usuário do GUJ.
This file contains hidden or 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; | |
| public class AlgoritmosDiversos { | |
| public static final long MAX_SECRET = 20; | |
| public static final long SECRET = (long) ((Math.random() * MAX_SECRET) + 1); | |
| public static void main(String[] args) { | |
| monteCarlo(10); | |
| lasVegas(); | |
| } | |
| public static void lasVegas() { | |
| long runningTime = System.currentTimeMillis(); | |
| long guess; | |
| int iteracoes = 0; | |
| ArrayList<Long> remainingList = new ArrayList<Long>(); | |
| for (long i = 1; i <= MAX_SECRET; i++) { | |
| remainingList.add(i); | |
| } | |
| do { | |
| guess = (long) (Math.random() * MAX_SECRET) + 1; | |
| if (remainingList.contains(guess)) { | |
| remainingList.remove(guess); | |
| iteracoes++; | |
| } | |
| } while (guess != SECRET); | |
| runningTime = System.currentTimeMillis() - runningTime; | |
| System.out.println("LAS VEGAS: Foram necessarias " + iteracoes + " iterações para descobrir o número."); | |
| System.out.println("LAS VEGAS: O algoritmo ficou " + runningTime + "ms em execução."); | |
| } | |
| public static void monteCarlo(long maximoIteracoes) { | |
| long runningTime = System.currentTimeMillis(); | |
| long guess; | |
| int iteracoes = 0; | |
| ArrayList<Long> remainingList = new ArrayList<Long>(); | |
| for (long i = 1; i <= MAX_SECRET; i++) { | |
| remainingList.add(i); | |
| } | |
| do { | |
| guess = (long) (Math.random() * MAX_SECRET) + 1; | |
| if (remainingList.contains(guess)) { | |
| remainingList.remove(guess); | |
| iteracoes++; | |
| } | |
| } while (SECRET != guess && iteracoes < maximoIteracoes); | |
| if (SECRET == guess) { | |
| System.out.println("MONTE CARLO: Foram necessarias " + iteracoes + " iterações para descobrir o número."); | |
| } else { | |
| long prediction = remainingList.get(remainingList.size() / 2); | |
| System.out.println("MONTE CARLO: O número não foi descoberto nas " + maximoIteracoes + " iterações realizadas!"); | |
| System.out.println("MONTE CARLO: Previsão: " + prediction); | |
| System.out.println("MONTE CARLO: Número real: " + SECRET); | |
| } | |
| runningTime = System.currentTimeMillis() - runningTime; | |
| System.out.println("MONTE CARLO: O algoritmo ficou " + runningTime + "ms em execução."); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment