최근 인터뷰에서 아래 질문을 받았습니다
0 또는 1을 무작위로 반환하는 함수 BinaryRandom ()이 주어지면 BinaryRandom ()을 사용하여 주어진 입력보다 작거나 같은 난수를 생성하는 int MyRandom (int) 함수를 만듭니다.
나는 매일 스택 오버플로와 GeeksForGeeks 사용자이고 GeeksForGeeks에서 비슷한 종류의 문제를 회상하므로 아래 링크를 참조하십시오.
https://www.geeksforgeeks.org/implement-random-0-6-generator-using-the-given-random-0-1-generator/
유일한 차이점은 GeeksForGeeks 범위에 0-6이었고 제 경우 범위는 <= N입니다 (N은 입력 정수입니다).
위의 솔루션은 다음 링크를 사용하여 SO에서 파생됩니다.
알고리즘 초심자로서 위에서 이해하기가 어렵습니다. 누구든지 위의 질문에 대한 간단한 해결책을 제안 해 주시겠습니까? 아니면 간단한 이해를 주시겠습니까?
0 또는 1을 반환하는 BinaryRandom () 함수가 주어지면 주어진 입력보다 작거나 같은 난수를 만드는
함수 intMyRandom(int)
를 만듭니다.
int MyRandom(int max);
max
-> 의 비트 너비를 찾으십시오 bitwidth
. 0까지 오른쪽 시프트를 계산할 수 있습니다. 예를 들어를 사용 max == 42
하면 6 비트가 필요합니다.
호출하여 난수를 형성한다 BinaryRandom()
. 예를 들어 6 비트로 숫자를 형성합니다 [0...63]
.
int r = 0;
// Double the value each iteration and add new bit.
for (i = 0; i<bitwidth; i++) r = 2*r + BinaryRandom();
범위를 벗어나지 않는지 확인 : 인 경우 r > max
2 단계를 반복합니다.
반환 r
.
2 단계를 다시 실행해야하는 기회를 줄이는 방법 (표시되지 않음)이 있지만 r_from_more_than_6_iterations%42
.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다