알고리즘 서론 - 2. 랜 덤 알고리즘 연습 문제 선택

알고리즘 서론 에서 의 연습 문 제 는 대부분이 경전 이 고 많은 문 제 를 풀 지 못 하 며 인터넷 에서 답 을 찾 은 다음 에 스스로 천천히 이해 하 는 과정 이 저 에 게 도움 이 되 었 습 니 다.나 는 일부 연습 문 제 를 정선 하여 찾 아 볼 수 있 도록 아 이 디 어 를 압축 파일 로 썼 다.이 박문 을 시작 으로 저 는 MathJax 를 사용 하여 공식 을 표시 하려 고 합 니 다. 예전 에 몇 편의 박문 에서 그림 을 사용 한 것 이 아니 라 만약 에 귀하 의 조회 에 무슨 문제 가 있 으 면 저 에 게 알려 주세요.
앞의 두 문 제 는 알고리즘 입문 1 절 에서 고 른 것 으로 너무 적 으 면 단독으로 한 편 을 만 들 지 못 했다.
연습 실행 시간 이 $\ Theta (nlgn) $인 알고리즘 을 알려 줍 니 다. $n $개의 정수 로 구 성 된 집합 $S $와 다른 정수 $x $를 지정 할 때 $S $에 두 개의 요소 와 $x $인 요 소 를 판단 할 수 있 습 니 다.
사고방식: 우선 병합 정렬 으로 그룹 $S $를 정렬 합 니 다. 필요 한 실행 시간 은 $\Theta(nlgn)$ 。두 보초병 의 한 끝 과 한 끝 으로 중 부 를 순찰 합 니 다. 만약 두 보초병 의 합 이 공교롭게도 $x $라면 해 를 찾 을 수 있 습 니 다. 보초병 의 합 이 $x $보다 크 면 오른쪽 보초병 을 왼쪽으로 한 칸 이동 합 니 다. 보초병 의 합 이 $x $보다 작 으 면 왼쪽 보초병 을 오른쪽으로 한 칸 이동 시 켜 두 보초병 이 만 날 때 까지 이 과정 에 필요 한 운행 시간 은 분명히 $\ Theta (n) $입 니 다. 전체 알고리즘 의 운행 시간 은 $\Theta(nlgn)+\Theta(n)=\Theta(nlgn)$ 。
사고 문제 2 - 4. d 실행 시간 이 $\ Theta (nlgn) $인 알고리즘 을 제시 하고 $n $개 요소 의 배열 $S $중 역순 이 맞 는 수 를 확인 합 니 다.(알림: 병합 정렬 을 수정 합 니 다.)
사고방식: $S $의 어떤 하위 집합 $[s {p}, s {r}] $를 두 개의 하위 집합 $[s {p}, s {q}] $로 나눈다. 그리고 $[s {q + 1}, s {r}] $ 。$[s_{p},s_{r}]$ 중 역순 쌍 의 수 는 두 부분 집합 각자 내부 의 역순 대 수 와 부분 집합 간 역순 대 수 를 나타 내 는 것 과 같다. 전 자 는 한 요소 만 집중 할 때 까지 역순 대 수 는 $0 $이 고 후 자 는 두 부분 집합 이 이미 순 서 를 배열 한 상황 에서 도 선형 운행 시간 에서 구 할 수 있다 (이 과정의 위조 코드 는 다음 과 같다).

INVERSE_NUM(s, p, q, r)
/*s[p~q] and s[q+1~r] are sorted*/
while i=q to p, j=r to q+1
    if s[i]>=s[j]
        result+=j-q
        i--
    else
        j--

여기 서부 터 는 랜 덤 알고리즘 부분 에서 정 선 된 부분 연습 문제 입 니 다.
연습 C. 1 - 7 증명 $$\ \ binom {n} {k} = \ binom {n - 1} {k} + \ binom {n - 1} {k - 1} $$
사고: $n $개 요소 에서 $k $개 요 소 를 선택 하 는 방법 수 = 특정한 요 소 를 선택 하고 나머지 $n - 1 $개 요소 에서 $k - 1 $개 요 소 를 선택 하 는 방법 수 + 이 요 소 를 선택 하지 않 고 나머지 $n - 1 $개 요소 에서 $k $개 요 소 를 선택 하 는 방법 수.
연습 C. 2 - 7 $n $개 이벤트 의 집합 을 어떻게 구성 하 는 지 설명 합 니 다. 두 개의 독립 을 만 들 지만 $k > 2 $개의 서로 독립 된 요소 의 부분 집합 은 존재 하지 않 습 니 다.
사고방식: 먼저 $s{1} $와 $s{2} $는 무 작위 실수 이 고 서로 독립 된 다음 $s 를 설정 합 니 다.{i}=s_{i-1}+s_{i - 2} $, $s{i} $로 구 성 된 서열 은 문제 설정 조건 을 만족 시 킵 니 다.
연습 C. 2 - 9 C. 2 - 10. 몬 티 홀 문제.
텔레비전 게임 에서 상품 은 세 개의 막 뒤에 놓 여 있다.선수 가 하나의 막 을 선택 한 후에 사회 자 는 남 은 두 개의 막 을 열 어 뒤에 빈 것 을 보 여 주 었 다. 이때 선 수 는 다른 막 을 선택 하여 자신 이 상 을 받 을 기 회 를 확대 해 야 합 니까?
정 답 은 선택 을 바 꿔 야 한 다 는 것 이다. 직관 과 는 어 긋 나 지만.그 이 유 는 사회자 가 어떤 막 뒤에 대상 이 있 는 지 알 고 있 기 때문이다. 만약 에 선수 가 상품 이 있 는 막 을 지정 하면 MC 는 무 작위 로 두 개의 빈 막 중 하 나 를 열 었 다.만약 에 선수 가 지정 한 막 이 비어 있 으 면 사회 자 는 남 은 빈 막 만 열 고 무 작위 로 한 조각 을 열지 않 는 다 (뒤에 상품 일 수도 있 고 게임 이 끝 났 는데 실제로 이런 상황 은 일어나 지 않 는 다).2 달러 / 3 달러 의 경우 사회 자 는 무 작위 로 선택 한 것 이 아니 라 조건 확률 을 계산 할 때 이 점 을 무시 하 는 경우 가 많다.
감옥 간 수 는 세 명의 범죄자 $X $, $Y $, $Z $중 하 나 를 무 작위 로 선택 하여 처형 합 니 다. $X $감옥 간수 에 게 $Y $와 $Z $누가 처형 되 는 지 물 었 습 니 다. 간 수 는 $Y $가 처형 된다 고 답 했 습 니 다. $X $자신의 생존 확률 이 $1 / 3 $에서 증가 했다 고 생각 합 니 다. $1 / 2 $, 그렇습니까?
정 답: 확률 이 $1 / 2 $로 올 라 가지 않 았 습 니 다. 여전히 $1 / 3 $입 니 다.여기 서 두 가지 직감 이 충돌 하 는 현상 이 나타 날 것 같 습 니 다. 범죄자 $X $가 간수 에 게 묻 는 질문 에는 판단 이 담 겨 있 습 니 다. 그 가 묻 는 것 은? $Y $와 $Z $누가 처형당 하 든, 이 세 사람 이 살아 남 든, $Y $와 $Z $중 한 사람 이 죽 어야 합 니 다. 간수 의 대답 은 사실 정보 가 없습니다. 그러나 범죄자 가 $Y $가 풀 려 나 든, 처형 되 든, 간수 가 처형 이 라 고 대답 하면 (이 경우 간수 가 자발적으로 누가 풀 려 나 는 지 회피 하지 않 습 니 다) $X $가 기뻐 할 이유 가 있 습 니 다.
C. 3 - 6 령 $X $를 비 네 거 티 브 랜 덤 변수 로 연습 합 니 다. $E [X] $가 좋 은 정의 (즉 수렴) 가 있다 고 가정 합 니 다.임의의 $t > 0 $에 대해 마 르 코 프 의 부등식 을 증명 합 니 다:
$$Pr\left\{X\geq a\right \}\leq \frac{E[X]}{a}$$
연속 무 작위 변수 에서 원 하 는 정의 에 따라:
$$E[X]=\int_{0}^{a}xf(x)dx+\int_{a}^{\infty}xf(x)dx\geq\int_{a}^{\infty}xf(x)dx\geq \int_{a}^{\infty}af(x)dx=aPr\left \{ x\geq a \right \}$$
연습 C. 4 - 5 는 매번 성공 확률 이 $1 / n $인 베 르 누 리 실험 에서 $n $회 성공 하지 못 할 확률 이 약 $1 / e $임 을 증명 합 니 다.
사고방식: $n $번 도 성공 할 확률 이 없습니다 $p $:
$$p(n)=(1-\frac{1}{n})^{n}$$
$n $가 비교적 클 때,
$$\lim_{n \to \infty } p(n)=\lim_{n \to 0 }(1-n)^{\frac{1}{n}}=\frac{1}{e}$$
연습 C. 4 - 6 두 사람 이 각각 평균치 동전 $n $회 를 던 집 니 다. 그들 은 정면 상 향 횟수 가 같은 확률 을 얻 을 수 있 습 니까?이 사고방식 을 이용 하여 검증:
$$\sum_{k=0}^{n}\binom{n}{k}^{2}=\binom{2n}{n}$$
사고방식: 두 사람 모두 $1 달러 를 던 졌 습 니 다. 정면 은 위로, $2 $는 정면 은 위로... 의 확률 을 계산 합 니 다.
$$Pr\{x_{A}=x_{B}\}=\sum_{k=0}^{n}Pr\{x_{A}=x_{B}=k\}=\sum_{k=0}^{n}\binom{n}{k}^{2}(\frac{1}{2})^{2}$$
비록 이것 은 정확 한 결과 이지 만, 우 리 는 $\ sum $기 호 를 간소화 하 기 를 희망 할 수 있 습 니 다.
절묘 한 사 고 는 두 사람 이 각각 $n $번 을 던 진 것 으로 볼 수 있 습 니 다. $n $번 을 던 진 것 으로 볼 수 있 습 니 다. 전 $n $번 은 $A $던 진 것 으로 볼 수 있 습 니 다. 후 $n $번 은 $B $던 진 것 으로 볼 수 있 습 니 다. 전혀 문제 가 없 죠?포 인 트 는 $A $에 대해 서 는 매번 정면 을 위로 향 하고 $B $에 대해 서 는 뒷면 을 위로 향 해 정면 을 위로 향 합 니 다 (그 는 뒷면 이 정면 이 라 고 생각 합 니 다). 동전 은 균일 하기 때문에 이렇게 해도 두 사람 이 같은 정면 개 수 를 얻 을 확률 에 영향 을 주지 않 습 니 다.이것 은 매우 간단 한 상황 입 니 다. $2n $번 던 지기 로 $n $개의 정면 이 생 겼 습 니 다 ($A $에 게).
그래서 두 사람 이 긍정 적 으로 올 라 갈 확률 은?
$$Pr\{x_{A}=x_{B}\}=\binom{2n}{n}(1/2)^{2n}$$
사고 문제 C - 1 은 다음 과 같은 가설 을 바탕 으로 $n $공 을 $b $같은 상자 에 넣 는 것 을 고려 합 니 다. 몇 가지 방법 이 있 습 니까?
(b) $n $개의 공이 다르다 고 가정 하면 상자 마다 공 은 순서 가 있 고 몇 가지 방법 이 있 습 니까?
$b $개 상 자 를 $b - 1 $와 막대기 로 보고 막대 기 는 공 을 분리 합 니 다. $n + b - 1 $개 물건 을 모두 배열 하 는 것 과 같 습 니 다. 방법 수 는 $(n + b - 1) 입 니 다! $.$b - 1 $는 막대기 와 같 기 때문에 $(b - 1) 로 나 누 기! $,정 답 은:
$$\frac{(n+b-1)!}{(b-1)!}$$
(c) 공이 같다 고 가정 하면 상자 도 똑 같 고 몇 가지 방법 이 있 습 니까?
공이 같다 면 $n! $개 (b) 중의 방법 만 하나의 (c) 방법 을 공유 할 수 있 습 니 다. 정 답 은:
$$\binom{b+n-1}{n}=\frac{(n+b-1)!}{(b-1)!\cdot n!}$$
연습 5.4 - 6 $n $개 공 을 $n $개 상자 에 투입 합 니 다. 매번 공 을 독립 적 으로 던 지고 상자 에 떨 어 질 기회 가 같 습 니 다. 마지막 빈 상자 의 수량 에 대한 기 대 는 얼마 입 니까?
사고방식: 이런 문 제 를 해결 하 는 관건 은 무 작위 표시 기 변수 입 니 다. 만약 에 원 하 는 정의 에 따라 빈 상자 가 $0 $인 확률 을 계산 하면 $1 $의 확률 로... 막 다른 골목 에 빠 질 수 있 습 니 다.정확 한 해법 은: 무 작위 표시 기 변 수 를 정의 합 니 다 $A{i} $는 $i $상자 가 비어 있 을 확률 을 표시 합 니 다.위의 연습 C. 4 - 5 에서 이미 구 했 습 니 다. 약 $1 / e $입 니 다. 그러면 빈 상자 의 수량 에 대한 기 대 는 $n / e $입 니 다.