1 ~ 100 까지 랜덤하게 숫자를 뽑을때 중복되지 않게 뽑으면서 속도까지 빠르려면 어떤 방법이 있을까??
일반적으로 사실 for문 을 잘 돌리면 중복 되지 않게 뽑는건 어렵지 않다..
다만 중복 for문에 의해 속도가 느려질뿐... 1 ~ 10 정도의 작은 수는 괜찮지만 1000, 10000 같이 숫자가 커질수록 부하는 몇배로 커진다...
우선 한가지 생각해본 방법은
미리 배열에 1 ~100까지 담아두고 하나씩 빼오는 것.
그러다 이미 빠진 숫자가 나오면 그 옆의 숫자를 가져오는 것을 생각해봤다.
01 | IString arrNum[100]; |
02 | for(int i = 1 i < 101; i++) |
03 | { |
04 | arrNum[i] = i+1; |
05 | } |
06 | for(int i = 1; i < 101; i++) |
07 | { |
08 | sTemp = (short)rand() % 100 ; |
09 | while(arrNum[sTemp].Compare("")==0) |
10 | { |
11 | sTemp++; |
12 | if(sTemp == 100) sTemp = 1; |
13 | } |
14 | arrNum[sTemp] = ""; |
15 | } |
16 | printf("%d", sTemp); |
①②③④⑤⑥⑦⑧⑨⑩....... 이렇게 100까지 저장해 둔다.
랜덤을 돌려서 5가 나오면
①②③④""⑥⑦⑧⑨⑩....... 5는 공백이 된다.
쭉 for문을 돌다가 또 5가 나오면 그 옆 숫자인 6을 가져오고.. 6도 비어있으면 그 옆의 7... 이런식으로 한칸 옆의 숫자를 가져오면서 돌게 된다.
하지만 위 코드도 단점이 있었다..
낮은 확률이긴 하지만 마지막에 가면 근접한 숫자들이 뭉쳐서 나올때가 있다.
그래서 검색을 하고 하고 또 해서 찾아낸 방법.
01 | int sCard = 100; |
02 | int *x = new int[sCard]; |
03 | for (int j = 0 ; j < sCard; j++) |
04 | x[j] = j; |
05 | |
06 | for (int j = 0; j < sCard; j++) |
07 | { |
08 | int tmp = 0; |
09 | int k = 0; |
10 | int l = 0; |
11 | for(int m = 0; m < 8; m++) |
12 | { |
13 | tmp += rand() << (32 - ((m + 1) * 4)); |
14 | } |
15 | k = (tmp % (sCard - j)) + j; |
16 | l = x[j]; |
17 | x[j] = x[k]; |
18 | x[k] = l; |
19 | } |
20 | free(x); |
아참.. 위 코드는 0~ 100이 되겠다..
인덱스 가져올 일이 있어서 0 부터로 짯음...
사실 소스에서
1 | for(int m = 0; m < 8; m++) |
2 | { |
3 | tmp += rand() << (32 - ((m + 1) * 4)); |
4 | } |
5 | k = (tmp % (sCard - j)) + j; |
이부분은 이해를 못하고 있다..
먼가 중요한 부분이고 위 소스 때문에 난수가 제대로 나오는것 같은데 아직 정확히 이해는 못하고 있다 ;ㅁ;
'프로그래밍 > C++ / C' 카테고리의 다른 글
| [c++] CHttpConnection에서 한글 전송 시 null 문제 (0) | 2011.01.13 |
|---|---|
| [C++/C] 트랜잭션 ... (0) | 2010.12.23 |