다른 임의 함수를 사용하는 난수

Question

최근 인터뷰에서이 질문을 받았습니다 :

같은 확률로 1-5 사이의 숫자를 반환하는 공정한 Randon5() 함수가 제공됩니다. 이제는 Random5()를 사용하여 공정한 Random7() 함수를 작성할 필요가 있습니다.이 함수는 1-7 사이의 숫자를 리턴하며 사용할 다른 것은 없습니다.

미리 감사드립니다.

Answer 1

일반적으로 제한된 유한 시간에는이를 수행 할 수 없습니다. 7은 5의 거듭 제곱이 아니기 때문입니다. 프로 시저가 영원히 실행될 확률이 0이지만 즉 종료되지만 언제의 질문.

한 가지 방법은 1-5 생성기를 두 번 실행하여 1에서 25 사이의 임의의 숫자를 얻는 것입니다. 숫자가 21보다 크면 반복하십시오. 그렇지 않으면 1에서 21 사이의 숫자를 얻으면 7로 나누고 1을 더할 때 나머지를 가져옵니다. 7은 21을 나눕니다. 따라서 1에서 7 사이의 균일 한 난수가 제공됩니다.

시도 할 때마다 1에서 21 사이의 숫자를 얻으려면 실패 할 확률이 4/25뿐입니다. 따라서 성공하기 전에 프로 시저를 반복해야하는 예상 횟수는 2 분 미만입니다.