바 시 게임 (bash game) 유형 n 개의 아 이 템 만 있 습 니 다. 두 사람 이 1 ~ m 씩 번갈아 가 며 마지막 에 이 긴 사람 이 이 깁 니 다. 분석 하 다. 총체 적 으로 몇 가지 상황 으로 나 눌 수 있다
$n = 0 $, 선두
$0
$n = m + 1 $, 선두
$n = k * (m + 1) + r $, 선손 승 (선손 으로 r 개 를 가 져 가 후수 에 k * (m + 1) 을 남 긴 국면)
$n = k * (m + 1) $, 선두
코드
int Bash_Game(int n,int m) //
{
if(n==0) return0;
if(n%(m+1)!=0) return1;
return0;
}
짐 게임 (짐 게임) 유형 한 무 더 기 를 여러 무더기 로 바 꾸 기;즉, 세 무더기 의 각 몇 개의 물품 이 있 는데 두 사람 은 돌아 가면 서 한 무더기 에서 임의의 많은 물품 을 취하 고 매번 에 적어도 한 개 를 취하 도록 규정 한다. 많 으 면 제한 이 없고 마지막 에 빛 을 얻 는 사람 이 이긴다. 분석 하 다. 이 부분 은 기타 블 로그 내용 을 포함 하고 있다. 주소:https://www.cnblogs.com/jiangjun/archive/2012/11/01/2749937.html
먼저 생각해 보면 마지막 에 두 무더기 의 물건 이 똑 같이 많 고 (0 이 아니 라) 세 번 째 무더기 가 0 이면 이런 상황 에 직면 한 쪽 은 반드시 패 한 다 는 것 을 알 수 있다
.
그러면 우 리 는 (a, b, c) 로 특정한 정 세 를 나타 낸다. 먼저 (0, 0, 0) 는 분명히 필 패 상태 이 고 누가 (0, 0, 0) 에 직면 하 든 반드시 실패 할 것 이다.두 번 째 필 패 태 는 (0, n, n) 자신 이 한 더미 에서 k (k ≤ n) 개 물품 을 가 져 가 는 것 이다. k 가 얼마 든 상대방 이 다른 더미 에서 k 개 물품 을 가 져 가면 마지막 에 자신 은 (0, 0, 0) 의 상황 에 직면 하고 반드시 패 할 것 이다.자세히 분석 해 보면 (1, 2, 3) 도 반드시 패 하 는 상태 이다. 자신 이 어떻게 잡 든 그 다음 에 상대방 은 정 세 를 (0, n, n) 으로 바 꿀 수 있다
.
그러면 이런 기이 한 정 세 는 어떤 특징 이 있 습 니까?누가 이렇게 강 요 했 는 지 모 르 겠 지만 이런 상황 을 2 진법 과 연결 시 켜 서 연산 기호, 이 또는 '^', a ^ b = a 'b + ab' (a '는 비 a) 를 말 할 수 있다. 우 리 는 기호 XOR 로 이런 연산 을 나타 낸다. 이런 연산 은 일반 덧셈 과 다른 점 은 1 XOR 1 = 0 이다.먼저 (1, 2, 3) 의 비트 모드 2 더하기 결 과 를 봅 니 다. 1 = 2 진 012 = 2 진 103 = 2 진 11 XOR - - - 0 = 2 진 00 (위치 에 주의 하지 않 음)
기이 한 정세 (0, n, n) 에 대해 서도 마찬가지 로 결과 도 0 의 어떠한 기이 한 정세 (a, b, c) 에 도 a XOR b XOR c = 0
이 있다.
만약 에 우리 가 직면 한 것 이 비 필 패 상태 (a, b, c) 라면 어떻게 필 패 상태 로 바 꿔 야 합 니까?가령 a < b < c, 우 리 는 c 를 a XOR b 로 바 꾸 기만 하면 된다.다음 과 같은 연산 결과 가 있 기 때 문 입 니 다. a XOR b XOR (a XOR b) = (a XOR a) XOR (b XOR b) = 0 XOR 0 = 0 c 를 a XOR b 로 바 꾸 려 면 c - (a XOR b) 와 같은 연산 만 하면 됩 니 다
.
짐 게임 모델 은 n 개의 물건 이 쌓 여 있 고 두 사람 이 돌아 가면 서 특정한 물건 에서 임 의적 으로 많은 물건 을 찾 을 수 있 으 며 매번 에 적어도 하 나 를 취하 고 다 자 는 제한 이 없 으 며 마지막 에 빛 을 얻 는 사람 이 이 길 수 있 도록 규정 할 수 있다.이 게임 의 변 수 는 쌓 아 올 리 는 k 와 쌓 아 올 리 는 아 이 템 수 N1, N2,..., Nk 입 니 다.대응 하 는 조합 문 제 는 선수 가 이 길지 후수 가 이 길지, 그리고 두 게임 인 이 어떻게 아 이 템 을 가 져 가 야 자신의 승 리 를 보장 할 수 있 느 냐 하 는 것 이다
.
Nim 취 물품 게임 을 더욱 이해 하기 위해 특수 한 상황 을 살 펴 보 자.게임 시작 시 한 무더기 의 아 이 템 만 있 으 면, 선 수 는 모든 아 이 템 을 가 져 가 승리 한다.현재 2 무더기 의 아 이 템 이 설치 되 어 있 으 며, 아 이 템 수량 은 각각 N1 과 N2 이다.게이머 들 이 승 리 를 거 두 는 것 은 N1 과 N2 의 가치 가 구체 적 으로 얼마 인지 에 달 려 있 지 않 고 그들 이 같 느 냐 에 달 려 있다.
두 무더기 의 전략 이 있 습 니 다. 지금 우 리 는 어떻게 두 무더기 의 취 자 전략 에서 임의의 더미 로 확장 합 니까?
먼저 기억 해 보 세 요. 모든 정수 에 대응 하 는 이 진수 가 있 습 니 다. 예 를 들 어 57 (10) = 111001 (2), 즉 57 (10) = 25 + 24 + 23 + 20 입 니 다.그래서 우 리 는 모든 물품 수 는 2 의 멱 수의 하위 더미 로 구성 된다 고 볼 수 있다.이렇게 57 개의 물품 이 무더기로 포 함 된 것 은 각각 25, 24, 23, 20 의 각 키 더미 로 구 성 된 것 으로 볼 수 있다
.
지금 은 N1, N2, Nk 의 일반적인 Nim 게임 을 고려 하고 있다.각 수의 Ni 를 이 진수 (수의 자릿수 가 같 고 같 지 않 을 때 앞에서 0 을 보충 합 니 다) 로 표시 합 니 다. N1 = as.. a1a 0N 2 = bs... b1b 0..................................................따라서 Nim 게임 은 균형 적 이 고 as + bs +... + ms 는 짝수, 즉 as XOR bs XOR... XOR ms = 0.. a1 + b1 +... + m1 은 짝수, 즉 a1 XOR b1 XOR... XOR m1 = 0a0 + b0 +... + m0 은 짝수, 즉 a0 XOR b0 XOR... XOR m0 = 0
그래서 우 리 는 짐 게임 에서 먼저 이 기 는 전략 을 얻 을 수 있다. Bouton 의 정리: 먼저 비 균형 적 인 짐 게임 에서 이 길 수 있 고 후 수 는 균형 적 인 짐 게임 에서 이 길 수 있다.즉, 상태 (x1, x2, x3,..., xn) 는 P 상태 이 고 x1 xor x2 xor x3 xor... xor xn = 0 이다.이런 조작 은 Nim 과 (Nim Sum) 라 고도 부 릅 니 다. 우 리 는 두 무더기 의 물건 을 가 진 Nem 게임 을 시험 으로 합 니 다.게임 을 시작 할 때 게임 은 불 균형 상태 에 있 습 니 다.이렇게 하면 선 수 는 일종 의 취 자 방식 을 통 해 그 로 하여 금 자 리 를 잡 은 후에 후수 에 게 남 겨 주 는 것 은 균형 상태 에서 의 게임 이다. 그 다음 에 후수 가 어떻게 자 리 를 잡 든 지 간 에 선 수 를 남 겨 주 는 것 은 반드시 불 균형 상태 게임 이다. 이렇게 반복 해서 진행 하면 후수 가 마지막 균형 상태 에서 자 리 를 잡 은 후에 선 수 는 모든 물건 을 한꺼번에 가 져 가서 이 길 수 있다.만약 에 게임 이 시 작 될 때 게임 카드 의 균형 상태 가 되면 상기 방식 에 따라 자 리 를 잡 으 면 최종 적 으로 후수 가 이 길 수 있다
.
다음은 이 승리 전략 을 활용 하여 4 더미 의 Nim 게임 을 고려 합 니 다.그 중 각 무더기 의 크기 는 각각 7, 9, 12, 15 개의 동전 이다.2 진법 으로 각 수 를 0111, 1001, 1100 과 1111 로 표시 하면 다음 과 같은 표를 얻 을 수 있다.
$2^{3}=8$ $2^{2}=4$ $2^{1}=2$ $2^{0}=1$ 크기 7 의 더미 0 1 1 1 크기 가 9 인 더미 1 0 0 1 크기 가 12 인 더미 1 1 0 0 크기 가 15 인 더미 1 1 1 1 Nim 게임 의 균형 조건 을 통 해 알 수 있 듯 이 이 게임 은 불 균형 상태의 Nim 게임 이기 때문에 먼저 승리 전략 에 따라 반드시 최종 승 리 를 거 둘 수 있다.구체 적 인 방법 은 여러 가지 가 있 는데 먼저 크기 가 12 인 더미 에서 11 개의 동전 을 가 져 가서 게임 을 균형 있 게 할 수 있다 (아래 표).
$2^{3}=8$ $2^{2}=4$ $2^{1}=2$ $2^{0}=1$ 크기 7 의 더미 0 1 1 1 크기 가 9 인 더미 1 0 0 1 크기 가 12 인 더미 0 0 0 1 크기 가 15 인 더미 1 1 1 1 그 다음 에 후수 가 아무리 씨 를 뽑 아 도 먼저 씨 를 뽑 은 후에 게임 을 균형 있 게 하 는 것 은 똑 같은 이치 이다. 먼저 도 크기 가 9 인 무 더 기 를 선택 하고 5 개의 동전 을 가 져 가 4 개 남 거나 먼저 15 인 더미 에서 13 개 를 가 져 가 2 개 를 남 길 수 있다.
결국 Nim 게임 의 관건 은 게임 이 시 작 될 때 게임 이 어떤 상태 (균형 또는 불 균형) 에 있 느 냐 와 선수 가 서브 게임 의 승리 전략 에 따라 게임 을 할 수 있 느 냐 하 는 것 이다
. 코드
int Nimm_Game(int n) // n f[] , 1
{
int sum=0;
for(int i=1;i<=n;i++)
sum^=f[i];
if(sum) return1;
return0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
