1.4.27 아다마르 행렬. n x n
아다마르 행렬 Hn은 불형 행렬로서 임의의 두 개의 행이 정확히 n/2 요소만큼 다르다는 특성을 가지고 있다. 이 특성은 오류-수정 코드를 설계하는 데 도움이 된다. H1은 1 x 1
행렬로서 True
인 요소 하나만 가지고 있다. n > 1에 대해 H2n은 Hn 4개를 정사각형으로 배치하고 나서 오른쪽 아래에 있는 n x n
행렬의 요소들의 값을 모두 뒤집으면 된다(그림 1.4.14). 여기에서 T
는 True
를, F
는 False
를 나타낸다.
▲ 그림 1.4.14 아다마르 행렬의 생성
명령 줄 인수로 정수 n을 입력받고 Hn을 출력하는 프로그램을 작성하라. n은 2의 거듭제곱이라고 가정하라.
1.4.28 루머. 앨리스는 밥을 포함한 n
명의 손님과 파티를 하고 있다. 밥이 먼저 다른 손님 중 한 사람에게 앨리스에 대한 루머를 이야기한다. 이 루머를 처음 들은 사람은 바로 (앨리스와 루머를 얘기해준 사람을 제외한 사람들 중에서 무작위로 선택한) 다른 손님에게 전달한다. (밥을 포함한) 어떤 사람이 루머를 두 번째 듣는 경우라면 이 소문을 전달하지 않는다. 파티에 참석한 모든 사람(물론 앨리스는 제외한다)들이 이 소문을 들을 수 있는 확률을 추정하는 프로그램을 작성하라. 그리고 루머를 듣게 될 사람 수의 기댓값을 계산하라.