Skip to content

Instantly share code, notes, and snippets.

@danielfariati

danielfariati/Algoritmos Las Vegas - Monte Carlo

Created December 29, 2011 18:43
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save danielfariati/1535513 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save danielfariati/1535513 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. danielfariati revised this gist Jan 5, 2012. No changes.
  2. danielfariati revised this gist Jan 5, 2012. No changes.
  3. danielfariati revised this gist Jan 5, 2012. 1 changed file with 24 additions and 13 deletions.
    37 changes: 24 additions & 13 deletions Algoritmos Las Vegas - Monte Carlo
    View file
    Original file line number Diff line number Diff line change
    @@ -1,13 +1,14 @@
    import java.util.ArrayList;
    import java.util.Collection;
    import java.util.HashSet;

    public class AlgoritmosDiversos {

    public static final long MAX_SECRET = 100000;
    public static final long MAX_SECRET = 1000000;
    public static final long SECRET = (long) ((Math.random() * MAX_SECRET) + 1);

    public static void main(String[] args) {
    new LasVegas(SECRET).start();
    new MonteCarlo(SECRET, 10000).start();;
    new MonteCarlo(SECRET, 10).start();
    }
    }

    @@ -20,10 +21,12 @@ class LasVegas extends Thread {
    }

    public void run() {
    System.out.println("LAS VEGAS: Programa iniciado.");

    long guess;
    int iteracoes = 0;
    long runningTime = System.currentTimeMillis();
    ArrayList<Long> remainingList = new ArrayList<Long>();
    Collection<Long> remainingList = new HashSet<Long>();

    for (long i = 1; i <= secret; i++) {
    remainingList.add(i);
    @@ -45,7 +48,7 @@ class LasVegas extends Thread {

    }

    class MonteCarlo extends Thread {
    class MonteCarlo extends Thread {
    long runningTime = System.currentTimeMillis();
    long secret;
    long maximoIteracoes;
    @@ -57,31 +60,39 @@ class MonteCarlo extends Thread {
    }

    public void run() {
    System.out.println("MONTE CARLO: Programa iniciado.");

    int iteracoes = 0;
    ArrayList<Long> remainingList = new ArrayList<Long>();
    Collection<Long> remainingList = new HashSet<Long>();

    for (long i = 1; i <= secret; i++) {
    remainingList.add(i);
    }

    do {
    guess = (long) (Math.random() * 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);

    long prediction = 0;

    for (Long value : remainingList) {
    prediction += value;
    }

    prediction /= remainingList.size();

    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 + " - Número real: " + secret);
    }

    runningTime = System.currentTimeMillis() - runningTime;
    System.out.println("MONTE CARLO: O algoritmo ficou " + runningTime + "ms em execução.");
    }
  4. danielfariati revised this gist Dec 29, 2011. 1 changed file with 88 additions and 0 deletions.
    88 changes: 88 additions & 0 deletions Algoritmos Las Vegas - Monte Carlo
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,88 @@
    import java.util.ArrayList;

    public class AlgoritmosDiversos {

    public static final long MAX_SECRET = 100000;
    public static final long SECRET = (long) ((Math.random() * MAX_SECRET) + 1);

    public static void main(String[] args) {
    new LasVegas(SECRET).start();
    new MonteCarlo(SECRET, 10000).start();;
    }
    }

    class LasVegas extends Thread {

    long secret;

    public LasVegas (long secret) {
    this.secret = secret;
    }

    public void run() {
    long guess;
    int iteracoes = 0;
    long runningTime = System.currentTimeMillis();
    ArrayList<Long> remainingList = new ArrayList<Long>();

    for (long i = 1; i <= secret; i++) {
    remainingList.add(i);
    }

    do {
    guess = (long) (Math.random() * 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.");
    }

    }

    class MonteCarlo extends Thread {
    long runningTime = System.currentTimeMillis();
    long secret;
    long maximoIteracoes;
    long guess;

    public MonteCarlo(long secret, long maximoIteracoes) {
    this.secret = secret;
    this.maximoIteracoes = maximoIteracoes;
    }

    public void run() {
    int iteracoes = 0;
    ArrayList<Long> remainingList = new ArrayList<Long>();

    for (long i = 1; i <= secret; i++) {
    remainingList.add(i);
    }

    do {
    guess = (long) (Math.random() * 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 + " - Número real: " + secret);
    }

    runningTime = System.currentTimeMillis() - runningTime;
    System.out.println("MONTE CARLO: O algoritmo ficou " + runningTime + "ms em execução.");
    }
    }
  5. danielfariati created this gist Dec 29, 2011.
    74 changes: 74 additions & 0 deletions Algoritmos: Las Vegas - Monte Carlo
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,74 @@
    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.");
    }

    }