算法导论上几个简单的习题

5.1-2 用random(0,1)来实现random(a,b),并估计运行时间.
这个cu上面有讨论。
我想了一个超级白痴的 random(a,b) = random(0,1)*(b-a)+a     实数
不晓得cu上搞得这么复杂。怪也~ , 实际取决于random(0,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();
            }
    

 

5.1-3 假设你希望以各1/2的概率输出0和1。你可以自由使用一个输出0和1的过程BIASED-RANDOM。它以概率p输出1，以概率1-p输出0，其中0
想了许久。。。嗯。没想出来。。。
NBIASED-RANDOM
while TRUE
do
x = BIASED-RANDOM
y = BIASED-RANDOM
if x != y
then return x
两个字：精妙....

希望以各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^b) return a
            if(a == 1 && b == 0) {
                return 1;
            }
            if(a ==0 && b == 1) {
                return 0;
            }
        }
    }

 

10.1.6 说明如何用两个栈来实现一个队列，并分析有关队列操作的运行时间。
10.1.7 说明如何用两个队列来实现一个栈，并分析有关栈操作的运行时间。

用两个栈来实现队列比较简单，因为栈是先进后出，队列是先进先出，有两个栈，做两次先进后出，那么就成先进先出了（就有点负负得正的意思）。假设两个栈为A,B，入队的时候直接将数据压入第一个栈A，出队的时候直接从栈B出栈，若B为空，则将栈A数据全部弹出，一个一个的压入栈B。时间复杂度和标准队列一样，为O(1)。
用两个队列来实现栈就有点复杂了。队列是先进先出，两个先进先出合起来也还是先进先出啊，该怎么反过来呢？想到的办法是两个队列轮流存储数据。任意时刻一个队列为空，一个队列不为空。每次提取数据的时候，将非空队列的前n-1个数据转出到另外一个队列中。然后将第n个数据出队。每次入队都将数据添加在非空队列上。但这样子入队时间复杂度为O(1),出队时间复杂度为O(n)，很大啊。有更好的办法么？

 

9.1-2 在最坏情况下，同时找到n个数字中的最大值和最小值需要 3/2n-2 次比较。
找到 最大值 需要比较 n-1 次
找到 最小值 需要比较 n-1 次
同时找到 最大值 和 最小值 需要 2n-2 次
该怎么减少到 3/2n-2次呢？
找到 最大值 的比较次数已经是最少的，已经不能再减少；找最小值也一样的，那该怎么减少呢？
问题的关键在于两者的结合，也就是要同时。对任意一个元素，它不可能同时为最大值和最小值。
在同时找到最大值和最小值时，每个元素都参与了与最大值和最小值的比较，比较了两次。将数组成对处理。两两互相比较，将大的与最大值比较，小的与最小值比较。每两个元素需要的比较次数是，两两比较一次，大者与最大值比较一次，小者与最小值比较一次，共三次。

《算法导论》习题答案和教师手册 
http://blog.chinaunix.net/u/18517/showart_487811.html