面试常问的思维题

1.1.给出rand（5）的函数，实现rand（7）的函数

rand(7) = 5×(rand(5)-1)+rand(5)，
因为5×(rand(5)-1)+rand(5)可以构造出1-25的每一个整数，7*3 = 21,所以如果超过21则重新计算，直到小于等于21，返回该值%7 + 1
实现代码如下：

int rand7(){
    int x;
    while(true){
        x = 5*(rand5() - 1) + rand5();
        if(x <= 21)
            break ;
    }
    return x%7 + 1;
}

1.2.给出rand（5）的函数，实现rand（n）的函数

其实这就用到了二进制的知识
我们不妨先用rand(5)得到rand(2),然后通过二进制组成rand(n)
实现代码如下：

int rand1(){
    int x;
    while(true){
        x = rand5();
        if(x <= 4)
            break ;
    }
    return x%2;
}
int randn(){
    int x;
    int cnt = ceil(log(n))
    while(true){
        x = 0
        for(int i=0;i<cnt;i++){
            if(rand1() == 1){
                x += (1<<i);   
            }
        }
        if(x < n)break ;
    }
    return x + 1;
}