면접 알고리즘 문제 (3)

제목:
함수 rand 5 () 를 지정 하면 이 함 수 는 1 - 5 의 정 수 를 무 작위 로 생 성 할 수 있 고 생 성 확률 이 같 습 니 다.현재 이 함수 구조 함수 rand 7 () 을 사용 하여 함수 rand 7 () 을 무 작위 로 1 - 7 의 정 수 를 생 성 할 수 있 도록 합 니 다.
생각:
많은 사람들의 첫 반응 은 rand 5 () + rand ()% 3 을 이용 하여 rand 7 () 함 수 를 실현 하 는 것 이다. 이 방법 은 확실히 1 - 7 사이 의 임 의 수 를 만 들 수 있 지만 자세히 생각해 보면 숫자 가 생 성 될 확률 이 같 지 않다 는 것 을 알 수 있다.rand ()% 3 에 0 이 생 길 확률 은 1 / 5 이 고 1 과 2 가 생 길 확률 은 2 / 5 이기 때문에 이 방법 은 6 과 7 이 생 길 확률 이 5 가 생 길 확률 보다 크다.
정확 한 방법 은 rand 5 () 함 수 를 이용 하여 1 - 25 사이 의 숫자 를 생 성하 고 그 중의 1 - 21 을 1 - 7 로 비 추어 22 - 25 를 버 리 는 것 이다.예 를 들 어 생 성 (1, 1), (1, 2), (1, 3) 은 rand 7 () 중의 1 로 보고 나머지 4 가지 가 나 오 면 버 리 고 다시 생 성 한다.
간단 한 실현:
public class Test {
	public int rand7() {
		int x = 22;
		while(x > 21) {
			x = rand5() + (rand5() - 1)*5;
		}
		return 1 + x%7;
	}

}

좋은 웹페이지 즐겨찾기