1.4.38 리플 셔플. 길버트-섀넌-리즈(Gilbert–Shannon–Reeds) 모델로 리플 셔플(riffle shuffle)(카드 패를 둘로 나누어 양손에 하나씩 쥐고 동그랗게 누르면서 두 패를 섞는 방법)해 n장의 카드 한 벌을 재정렬시키는 프로그램을 작성하라. 먼저 이항 분포에 따라 무작위 정수 r을 생성하라(동전을 공평하게 n번 던져 앞면이 나오는 횟수를 r로 설정한다). 이제 카드 덱을 두 뭉치로 나누어라(앞에서 r만큼의 카드와 나머지 카드). 두 뭉치 중 한쪽에서 카드를 가져와 새로운 뭉치의 밑에 놓는 과정을 반복하라. 첫 번째 뭉치에 n1, 두 번째 뭉치에 n2의 카드가 남아 있다면 첫 번째 뭉치에서 카드를 가져올 확률은 n1 / (n1 + n2), 두 번째 뭉치에서 카드를 가져올 확률은 n2 / (n1 + n2)이다. 52장 카드 한 벌을 (거의) 균일하게 셔플링하려면 리플 셔플을 몇 번 해야 할지 조사하라.
1.4.39 이항 계수. 명령 줄에서 인수로 정수 n을 입력받아 이차 비균일 배열 a[][]를 생성하고 출력하는 프로그램을 작성하라. a[n][k]는 동전을 공평하게 n번 던졌을 때 앞면이 k번 나올 확률을 담고 있다. 이 숫자들은 이항 분포(binomial distribution)로 알려져 있다. k행에 있는 각 요소를 2n으로 곱하면 파스칼의 삼각형(Pascal’s triangle)으로 나열된 이항 계수(binomial coefficient)((x+1)n을 전개했을 때 xk의 계수)를 얻을 수 있다. 이항 계수를 구하려면 먼저 모든 n에 대한 a[n][0]을 0.0으로 설정하고, a[1][1]은 1.0으로 설정하라. 그러고 나서 이후의 행은 왼쪽에서 오른쪽으로 나가면서 a[n][k] = (a[n-1][k] + a[n-1][k-1])/2.0으로 계산하라.
▲ 그림 1.4.15 파스칼의 삼각형과 이항 분포