# 编程珠玑II C12笔记: rand num generator

## Problem:

`given m<n, generate random numbers of m within range(0..n).`

## Solutions:

• a Knuth’s solution of O(log n) time :
```select = m
remaining = n
for i = [0,n)
if ( bigrand() % remaining ) < select
print i
select--
remaining—```

But when n was large, it meets bootleneck. Improve with:

• a solution of O(m log m) time using :
```#include <iostream>
#include <cstdlib>
#include <set>
using namespace std;
void gensets(int m, int n){
set<int> S;
while(S.size()<m){
S.insert(std::rand() % n);
set<int>::iterator i;
for (i = S.begin(); i!=S.end(); ++i){
cout<< *i << endl;
}
}
}
int main(){
gensets(1000000, 10000000);
return 0;
}```
• shuffle solution O():

f

## Principles

talk to user

### Specify an Abstract Problem

get a clean, crisp problem statement.

### Explore the Desgn Space

think for a day and code for a min rather than per contra

choose the best

### Retrospect

Polya’s delightful How to Solve It can help programmer become a better problem solver.

31 篇文章24 人订阅

0 条评论

## 相关文章

31840

312100

### #哆啦A梦

write('by dongdong', font=("Bradley Hand ITC", 30, "bold"))

11300

### 使用ESTIMATE来对转录组表达数据根据stromal和immune细胞比例估算肿瘤纯度

ESTIMATE (Estimation of STromal and Immune cells in MAlignant Tumor tissues usin...

55320

19180

### Android高效内存2：让图片占用尽可能少的内存

Android高效内存：让图片占用尽可能少的内存 一、让你的图片最小化 1.1 大图小图内存使用情况对比 大图：440 * 336    小图：220 * 16...

315110

12.1K30

46850

24210

291100