蓄水池算法等機率問題

蓄水池算法

假設有一個源源吐出不同球的機器，隻有裝下10個球的袋子，每一個吐出的球，要麼放入袋子，要麼永遠扔掉，如何做到機器吐出每一個球之後，所有吐出的球都等機率被放進袋子裡？

思路：第k個球到來的時候，以10/k的機率放入袋子，扔的時候10個裡面随機選一個

public class RandomBox {

	private int[] bag;
	private int N;
	private int count;

	public RandomBox(int capacity) {
		bag = new int[capacity];
		N = capacity;
		count = 0;
	}

	private int rand(int max) {
		return (int) (Math.random() * max) + 1;
	}

	public void add(int num) {
		count++;
		if (count <= N) {
			bag[count - 1] = num;
		} else {
			if (rand(count) <= N) {
				bag[rand(N) - 1] = num;
			}
		}
	}
}
           

470. 用 Rand7() 實作 Rand10()

已有方法

rand7

可生成 1 到 7 範圍内的均勻随機整數，試寫一個方法

rand10

生成 1 到 10 範圍内的均勻随機整數。

不要使用系統的

Math.random()

方法。

方法：

用4個二進制位表示，最多可以表示0-15，
隻取1-10

使用rand7等機率的傳回0或1
1-3 -> 0
4-6 -> 1
7   -> 重來
           

public int rand10() {
    	int r;
    	while(true) {
    		r = (rand_01()<<3)+(rand_01()<<2)+(rand_01()<<1)+rand_01();
    		if(r>=1 && r<=10) {
    			break;
    		}
    	}
    	return r;
    }
    
    public int rand_01(){
    	int r7;
    	int t;
    	while(true) {
    		r7 = rand7();
    		if(r7 == 7) {
    			continue;
    		}else {
    			if(r7 >= 1&& r7 <= 3) {
    				t = 0;
    			}else {
    				t = 1;
    			}
    			break;
    		}
    	}
    	return t;
    }
           

每個人都有潛在的能量，隻是很容易被習慣所掩蓋，被時間所迷離，被惰性所消磨~