magic card

소개글

"magic card"에 대한 내용입니다.

목차

1. 문제 분석
1) 마술 카드란 ?
2) 마술 카드 예시
3) 문제 해결

2. 첫 번째 코딩
1) 소스 코드
2) 실행 및 결과
3) 코딩 후 분석

3. 두 번째 코딩
1) 소스 코드
2) 실행 및 결과
3) 코딩 후 분석

4. 세 번째 코딩
1) 문제 분석
2) 소스 코드
3) 실행 및 결과
4) 코딩 후 분석

본문내용

1. 문제 분석

▶ 마술 카드란 ?
이산수학에서 다루는 전형적인 문제들 중 하나로 여러 카드에서 마음속으로 생각한 숫자가 카드에 있는지 없는지 경우의 수를 통하여 마음속에 생각한 숫자를 맞추는 마술이다.

▶ 마술 카드 예시
다음과 같이 0~7까지 적힌 3장의 카드 A, B, C 가 있다.

1. 마음속으로 0~7까지의 숫자중 하나를 생각한다.
2. A B C 세장의 카드를 순서대로 보면서 생각한 숫자가 있으면 YES ,
없으면 NO를 선택한다.
3. 세장의 카드에 각각 YES/ NO를 답하면 마지막에 자신이 생각한
숫자가 나온다.

먼저 세 장의 카드에 대하여 각각 YES 와 NO를 연속하여 누르는 것은 2가지의 경우의 수가 연속하여 3번 독립적으로 반복 되는 것을 의미한다.
이때 경우의 수 : 2 x 2 x 2 = 8 가지

따라서 3번의 YES 와 NO 의 답변으로 모두 8개의 숫자를 대응시켜 분류 할 수 있다. YES를 숫자 1, NO를 숫자 0 으로 표시 한다면 다음과 같다.

만약 마음속에 4를 생각하였다면, 숫자 4는 카드 C 에만 나와 있고, 카드 C에만 있는 숫자는 유일하게 4 뿐임을 [표 1.1] 에서 확인 할 수 있다.

이제 [표 1.1]을 간단한 식으로 표현해 보자 . 즉. YES를 숫자 1, NO를 숫자 0 으로 표시한다면, 마음속에 생각한 숫자를 계산하는 식은
A * 2^0 + B * 2^1 + C* 2^2 이다.

만약 마음속에서 4를 생각하였다면 숫자 4는 카드 C 에만 있으므로 위 식에서
0*2^0 + 0 * 2^1 + 1*2^2 = 4 이다.

▶ 문제 해결
마술카드의 소스는 책에 있기 때문에 구현하는 데에는 그렇게 어렵지 않을 것이라 생각됩니다. 책에 있는 소스는 2차원 배열로 크기를 지정한 후에 배열 안에 0~31까지의 숫자를 16개씩 저장되어 있습니다. 일단 배열을 포인터로 사용하고 크기를 동적할당을 사용하여 메모리의 효율성을 증대시켜야 할 것 같습니다.

참고 자료

없음