有一个函数 foo() 能够返回 1～5的随机数，那么请使用 foo（），设计一个程序实现 1～n的随机数。要求输出的随机数足够随机，有机会取值1~n的任意数字。前几天面试遇到的，没看懂什么意思啊
换一个角度，如果foo返回的是0-1的随机数，这时我们只需要建立一个二进制的随机数生成器就可以满足要求了。
现在foo返回1-5，那么需要减1，建立5进制随机数生成器数，产生的随机数最大值必须大于等于n，如果生成的随机数超过n就重新生成一次，直到小于n。
或者直接生成5进制下非常非常大的数，然后对n取余数也是可以的，不过需要注明可以忽略。
就是要求你利用foo函数，来实现1-n的任意随机数生成。要求1-n是等概率的
https://blog.csdn.net/IT_Studio/article/details/107601255
https://blog.csdn.net/sea_muxixi/article/details/79969826
网上有很多例子可供参考
您好，你面试的这道理，意思是：目前已经给出的一个foo()函数，这个函数能随机返回1~5。面试题想让你利用这个foo函数，再实现一个可以无限随机的函数出来。
解题思路可以这样：
（1）先扩展一个1至9的的随机函数，比如foo_9();作为多位数的最高位。
（2）再扩展一个1至10的随机函数，比如foo_10();然后将这个返回值减去1，那么实际返回的便是0~9；这个函数用于多位数的除了最高位外的其他位；
（3）组合运行上面的两个函数，第一个运行的必须是foo_9();然后再随机次数运行foo_10();然后将每一次的返回数组合起来便是一个多位数了。。比如：3607856
这样，看起来随机了，但是还是不够真正随机，因为foo_10()的运行次数是随机的；因此，还要再设计一个随机次数的函数，比如foo_num();
下面的代码是foo_9的实例：
int foo_9(){
int x = ~(1<<91); // max int
while(x > 21)
x = 9 * (foo() - 1) + foo() // Rand25
return x%9 + 1;
}
用rand生成随机数
将这个数取余5+1
就是1-5的随机数了
还要记得srand重置种子
要生成一个1-7的随机数，等可能概率。
首先，考虑第一个问题：等可能概率。随机数是等概率的事件，就是1，2，3，4，5，出现的概率应该是相同的，而不是其中某一种概率大一点。
看这个公式 5*（x-1）+x；（x是1-5的随机数）
那么 5*（x-1）会是等可能的0，5，10，15，20
x会是等可能的1，2，3，4，5；
那么这个值就是等可能的0-25。
然后，考虑第二个问题：如何产生1-7？
产生1-7最直观的方法就是：对7取模加一；
但是0-25对7取模最后结果0-6产生的概率不一样；
很简单，如果大于21，再随机一次就好了。
举个例子
// 随机生成等概率1-5的函数实现
int random5() {
int x = rand(); //调用随机函数
if (x > 32000) return random5();
return x % 5 + 1; //1-5
}
// 由random5（）构造 random7()
int random7() {
int x = 5 * (random5() - 1) + random5();
if (x > 21) return random7(); // 筛选的过程
return x % 7 + 1;
}
利用利用foo函数来解决
// 把value转成5进制的数
int* get5Base(int value) {
int * res = (int *)calloc(32, sizeof(int));
int index = 31;
while (value != 0) {
res[index--] = value % 5;
value = value / 5;
}
return res;
}
// 等概率随机产生一个0~n-1范围上的数，只不过是5进制表达的。
int* getRan5BaseLessN(int* num) {
int *res = (int *)calloc(32, sizeof(int));
int start = 0;
while (num[start] == 0) {
start++;
}
int index = start;
int lastEqual = 1;
//精粹，控制随机数的范围在0~n-1（5进制表示）之间
while (index < 32) {
res[index] = foo() - 1;
if (lastEqual) {
if (res[index] > num[index]) {
index = start;
continue;
} else {
lastEqual = res[index] == num[index];
}
}
index++;
}
return res;
}
// 把5进制的数转成10进制
int getNumFrom5Base(int* num) {
int res = 0;
for (int i = 0; i < 32; i++) {
res = res * 5 + num[i];
}
return res;
}
// 随机生成1-5
int foo() {
return rand() % 5 + 1;
}
// 随机生成1-n
int fooN(int n) {
int * num = get5Base(n - 1);
int * randNum = getRan5BaseLessN(num);
return getNumFrom5Base(randNum) + 1;
}
#define N 13
int main() {
int num[N] = {0};
for (int i = 0; i < 1000; i++) {
num[fooN(N) - 1]++;
}
for (int i = 0; i < N; i++) {
printf("%d ", num[i]);
}
printf("\n");
}
等比例缩放一下，需要注意四舍五入时引起的最大数据和最小数据的概率变化。
比如n取6时，
P = foo() *（6 - 1） / （5 - 1）;
直接这样的话会导致1.25以内的数字取不到
所以
P = (foo() - 1) * (n - 1) / (5 - 1) + 1;
若随机数和n都是仅为整数，还要考虑所用的编译器是全舍还是四舍五入，乘法可能会导致原本舍弃的部分意外地加上去