| [ QuizWit ] in KIDS 글 쓴 이(By): staire (강 민 형) 날 짜 (Date): 1999년 12월 22일 수요일 오후 06시 16분 58초 제 목(Title): Re: 그래프 + 확률 문제 N = k 일때 전부 연결될 확률을 P(k) 라 두면 P(k+1)은 추가된 점 하나가 이미 주어진 점 k개 중 하나 이상과 연결되어 있으면 되니까 P(k+1) = P(k) * [1 - (1 - p)^k] = P(k) * (1 - q^k), 이때 q = 1 - p. P(2) = p = 1 - q 이므로 P(N) = P(N-1) * [1 - q^(N-1)] P(N-1) = P(N-2) * [1 - q^(N-2)] P(N-2) = P(N-3) * [1 - q^(N-3)] : : P(3) = P(2) * [1 - q^2] 변변 곱하면 P(N) = P(2) * (1 - q^2) * (1 - q^3) * ... * [1 - q^(N-1)] = (1 - q) * (1 - q^2) * (1 - q^3) * ... * [1 - q^(N-1)] 그러니까 P(N) = prod(k = 1 to N-1) [1 - (1 - p)^k]. 음 이만하면 별로 복잡해 보이지 않는데요... ----------- Prometheus, the daring and enduring... |