几个小算法问题

下面是我在一个bbs上看到的几个算法问题，难倒是不是很难，倒是有些地方值得注意，有进一步深究和讨论的必要，下面是我的一些想法，可能不够全面，以后也许随着知识的增长可以有更深刻的认识。

题目：
[color=darkblue]1.有一个随机数发生器，能以概率p生成0，以概率1-p生成1，问如何做一个随机数发生器
使得生成0和1的概率相等。
2.用上面那个生成0和1的概率相等的随机数发生器，怎样做一个随机数发生器使得它生成
的数在1...N之间均匀分布。
3、20个不同面值的硬币，排成一条直线，每个人都只能从线的两端取硬币
，轮流取，先手用什么样的策略可以保证拿到比后手多的钱？证明之
4、现有一批电脑，好坏不一。已知好的数目比坏的多。我们可以询问某一台电脑另一台电
脑的情况（好or坏），如果询问了一台坏电脑，它可能给出的是错误答案。现要求
设计一种策略，从中挑出一台好电脑，时间复杂度为O(n)。[/color]


第一题比较简单，可以用原发生器周期性地产生2个数，直到生成01或者10。
由于生成01和10的概率均为p(1-p)，故预先任意指定01为0（或1），10为1（或0）即可。即可等概率的产生0和1，但然，要考虑其他组合的不可用性，获取题目本身就隐含了这个bug或是缺陷吧。

int Rand_01()
{
	//produce random 0 and 1
	//with probability of 0 being p
	int temp1,temp2;
	while (true)
	{
		First(&temp1);
		First(&temp2);
		if (temp1 == 0 && temp2 == 1) return 0;
		if (temp1 == 1 && temp2 == 0) return 1;
		//other results ignored,but need more notice here ?????
	}
}

第二题，需要一些思考......想到位运算，因为i个二进制位随机的选择0或1，可以随机的构成0~2^i的数，而这些数构成了所有的组合数。因此是等概率出现的。比如：2位二进制位，这两位可以随机为0或1而互不影响，随机的构成了00 01 10 11，它们代表了四个数，且这四个数是等概率的。

int Rand_0N_1(double n)
{
	//use the procedure producing 0-1
	//Method one
	int i,result,size;
	result = n+1;
	size = (int)log(n)/log(2.0) + 1;
	while (result > n)
	{
		//filter for right number
		result = 0;
		for (i = 0;i < size+1;++ i)
		{
			result <<= 1; //move left
			result += rand01();
		}
	}
	return result;
}

上面采用了的是移位操作，当然也可以建立数组分别表示各位,思路基本相同，不再赘述。不过函数循环中产生的无效数也是等概率的产生的，只是不采用，相当于此次作用产生无效，故继续作用。所以最终表现的结果是（0~n等概率的）
关于此题还有一个不太成熟的算法，结果接近最终的结果：

int Rand_0N_2(double n)
{
	//Method Two
	int result=0;
	int i;
	for (i = 0;i < SS;++ i) result += rand01();
	return result%((int)n+1);
}

上述的SS是待讨论的阈值，当然值越大愈好，因为值愈大，result的值跨度就愈大，从0到SS，而产生他们的概率则是倒的双曲线（大概是吧，不是很精确，呵呵），也就是由小到大，在由大到小。当SS的值较大时，可将这些数按n为单位进行划分（也就是后面用到的求余操作），这样就将概率均分了，最终产生的数也就等概率了。
由此可知，在中间数（如n/2）产生的概率就高些，理论上是这样的，不过实验结果还算理想，基本上SS为n的平方即可达到理想结果。
此外，另外一种思路供参考(结果比较理想)：

int Rand_0N_3(double n)
{
	static int result=0;
	int i,size;
	size = (int)log(n)/log(2.0) + 1;
	for (i = 0;i < size;++ i) result += rand01();
	return result%((int)n+1);
}

第三题，我们可以如下解决：
[b]记[/b] SUM_1=奇数位置硬币的和
SUM_2=偶数位置硬币的和
不妨设SUM1>=SUM2
那么先手的你每次拿奇数就好。
注意到先手的你拿的时候 有偶数个硬币，那么头和尾的编号一个奇数一个偶数。
其他的就没有要说的了，只要保证自己每次拿到那组总和最大的一组即可。不过，如果，奇数组和偶数组的和是相同的，此算法只能保证拿到的不比后方少，也就是一种可行解，当然不是最优解，或许可以采用其他的算法（比如贪心算法、回溯法等）找到更好更优的解，自己还在探讨中，还没头绪......


第四题，我们可以做分析：
将所有电脑两两分组,
(1)如果相互报告均为好电脑,则随便淘汰一个,
(2)否则,即出现了报告为坏的情况,两个都淘汰.
两两一组的可能无非是：
[table]
| 好好 | 好好|
[/table]

[table]
| * 坏好 |
| * 坏坏 | 好坏|
[/table]

[table]
| 好好 |
| * 坏坏 | 坏坏
| * 好坏
[/table]

打*的是报告为坏的情况，两个都淘汰，因此每次淘汰要么一个好一个坏，要么两个坏，这样进行下去，就可逐步淘汰坏的，保留好的
G for Good, B for Bad.

All (GB) will be deleted, num(G)-num(B) will not change.

For the case of (BB) and (GG), num(G)-num(B)>=0.5num(G)-0.5num(B)=0.5(num(G)-
num(B))>0;
mention that: If (BB) reports (GB), both of the B will be deleted.