À pedidos de usuário do GUJ.

Algoritmos Las Vegas - Monte Carlo

import java.util.Collection;
import java.util.HashSet;

public class AlgoritmosDiversos {

	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, 10).start();
	}
}

class LasVegas extends Thread {

	long secret;

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

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

		long guess;
		int iteracoes = 0;
		long runningTime = System.currentTimeMillis();
		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 (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() {
		System.out.println("MONTE CARLO: Programa iniciado.");

		int iteracoes = 0;
		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 = 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.");
	}
}

Algoritmos: Las Vegas - Monte Carlo

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.");
	}

}