Random Alg first blood
3n+1问题，对于任意n，如果奇数，n=3*n+1, 偶数n=n/2,
这个问题3n+1,有结论，任何数都可以规约到1，10000也只要400左右，
但是证明oneness, 是困难的。
python
a=[]
a.sort()才会改变a结构
sorted(a) 只是把a排序结果返回出来，不改变a的结构
http://www.cnblogs.com/kkgreen/archive/2011/08/11/2134647.html
假设你希望以各1/2的概率输出0和1。你可以自由使用一个输出0或1的过程 BIASED-RANDOM。它以概率p输出1，以概率1-p输出0，其中0<p<1，但是你并不知道p的值。给出一个利用BIASED- RANDOM作为子程序的算法，返回一个无偏向的结果。你的算法的期望运行时间是多少？
分析：设计的思路是利用对称性。 假设有两个基于BIASED-RANDOM的伯努利试验序列A、B。每个试验序列都会产生0,1值序列;每一轮A和B各进行一次，如果该轮试验的结果是 ai>bi（即ai=1，bi=0）则算法结束，结果为1；如果ai<bi则算法结束结果为0；如果ai=bi则开始下一轮迭代。
由于每一轮试验都是独立的，所以只要能够证明每一轮在得出结果的条件下，得出1和得出0的概率相等就可以了。
while TRUE
do
x = BIASED-RANDOM
y = BIASED-RANDOM
if x != y
then return x
得出1的概率是p*q （x得出1，y得出0）
得出0的概率是q*p （x得出0，y得出1）
精妙！
Admis大神蛋哥推荐的题目
random algorithm
given random 0 or 1, return random integer [a, b]
区间扩增法，每一位编码，由于每个random是独立的，那么就是2^m个数覆盖了b-a+1个数就可以了。
bool Random01()
{
return rand()%2;
}
int RandInt(int a, int b)//[a, b]
{
int len=b-a+1;
int m=ceil(log2(len));
while(1)
{
int num=0;
for(int i=0;i<m;i++)
{
num=num*2+Random01();
}
if(num+a<=b ) return num;
}
}
蓄水池抽样第一发。
给定数组，随机返回数组中最大元素的位置。
假设当前是对n-1的目前最大值返回概率都为1/(n-1), 那么对于第n个元素，
如果说等于当前最大，如果1/n概率选择这个元素，那么前面的元素选中概率是(n-1)/n, 之前每个元素分别为1/(n-1), 那么之前n-1个元素选中概率分别为1/(n-1)* (n-1)/n= 1/n, 第n个元素选中概率是1/n.
如果当前元素更大，那么最大元素只有一个，选中这个概率是1
算法等概率正确性得到证明。
int GetRandomMax(int a[], int n)
{
int maxx=INT_MIN, pos=-1, num=0;
for(int i=0;i<n;i++)
{
if(a[i]<maxx) continue;
if(a[i]>maxx) {maxx=a[i], num=1;}
else num++;
if(rand()%num==0) pos=i;
}
return pos;
}