算法导论里关于随机算法的两道题

1：RANDOM(a, b)方法返回一个介于a与b之间的整数，每个整数出现的机会相等。描述RANDOM(a, b)的一种实现，它只调用RANDOM(0, 1)。

设方法random01()以等概率返回0或1

    int RANDOM(int a, int b) {
        int c = b - a;
        int n = 0;

        //算出b-a用二进制表示所需的位数
        while(c > 0) {
            n++;
            c /= 2;
        }
        int d;

        //对每一位分别调用random01()
        do {

            d = 0;
            for(int i = 0; i < n; i++) {
                d = d * 2 + random01();
            }
        } while(d <= c);
        return (a + d);
    }

2. 希望以各1/2的概率输出0和1。使用一个输出0或1的方法BIASED-RANDOM。它以概率p输出1，以概率1-p输出0，其中0

    int RANDOM() {
        int a = BIASED_RANDOM();
        int b = BIASED_RANDOM();
        while(true) {

            //0，1都以p(1-p)的等概率返回
            if(a == 1 && b == 0) {
                return 1;
            }
            if(a ==0 && b == 1) {
                return 0;
            }
        }
    }