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

5.1-2 用random(0,1)来实现random(a,b),并估计运行时间.
这个cu上面有讨论。http://bbs2.chinaunix.net/thread-1192193-1-1.html
我想了一个超级白痴的 random(a,b) = random(0,1)*(b-a)+a
不晓得cu上搞得这么复杂。怪也~

 

5.1-3 假设你希望以各1/2的概率输出0和1。你可以自由使用一个输出0和1的过程BIASED-RANDOM。它以概率p输出1，以概率1-p输出0，其中0<p<1，但是你并不知道p的值。给出一个利用BIASED-RANDOM作为子程序的算法，返回一个无偏向的结果，即以概率1/2返回0，以概率1/2返回1。作为p的函数，你的算法的期望运行时间是多少？
想了许久。。。嗯。没想出来。。。
NBIASED-RANDOM
while TRUE
do
x = BIASED-RANDOM
y = BIASED-RANDOM
if x != y
then return x
两个字：精妙....

 

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

评论

2 楼 zolo1226 2011-02-20  

第一题解答有问题，式子没看出有什么意义

1 楼 breakhearts 2009-02-23  

你的第一题和最后一题都有问题，第一题random(0,1)不是返回0-1之间的小数，而是以1/2概率返回0或者1。最后一题是让你证明这个问题最少需要那么多次比较，你只是找了个算法，没证明那种是最优的。