ZOJ 1913 유클리드 게임 게임 이론
1688 단어 └ -- 바둑 이론수학알고리즘
샤 오 밍 과 샤 오 홍 은 유클리드 게임 을 하고 있다.그들 은 두 개의 자연수 에서 시작 하여 첫 번 째 게이머 인 샤 오 밍 은 두 수의 비교적 큰 수 에서 비교적 작은 수의 가능 한 한 큰 정수 배 를 빼 고 차이 가 마이너스 가 아니면 된다.그 다음 에 두 번 째 게이머 샤 오 홍 은 얻 은 두 개의 수 를 똑 같이 조작 한 다음 에 샤 오 밍 이다.이렇게 돌아 가면 서 게임 을 진행 합 니 다. 한 게이머 가 큰 수 를 작은 수의 한 배 수 를 뺀 후에 0 이 될 때 까지 게임 이 끝나 면 이 유 저 는 승자 입 니 다.
입력 형식
여러 그룹의 테스트 데 이 터 를 입력 하 십시오.각 조 에 두 개의 정 수 를 입력 하면 게임 이 시작 되 는 두 개의 수 를 나타 내 고 게임 은 항상 샤 오 밍 이 먼저 시작한다.0 을 두 개 입력 하면 입력 이 끝 납 니 다.
출력
각 조 의 입력, 수출 의 마지막 승자 에 대해 우 리 는 그들 두 사람 이 모두 최고의 고수 이 고 모든 게임 이 최선 의 선택 을 했다 고 생각한다.구체 적 인 출력 형식 은 출력 사례 를 보십시오.
샘플 입력
34 12 15 24 0 0
샘플 출력
xiaoming wins xiaohong wins
생각:
세 가지 상황 으로 나 눌 수 있다
m 는 비교적 큰 수 n 은 비교적 작은 수 이다.
m% n = = 0 시: 누가 이기 면 누가 이긴다
m / n 이 1 과 같 을 때 취 법 (m, n) - > (n, m% n) 만 있 습 니 다.
m / n > = 2 시 누가 이기 면 누가 이 깁 니까? (n, m% n) 이 필 패 상태 일 때 취 하 는 사람 은 이 를 (m% n + n, n) 로 취 할 수 있 기 때 문 입 니 다. 반드시 패 태 를 다른 사람 에 게 옮 길 것 이다. 반대로 만약 (m% n + n, n) 이 필 패 상태 라면
취 하 는 자 는 (n, m% n) 이것 도 선수 우세 라 고 한다
코드:
#include
#include
#include
using namespace std;
int main()
{
int a,b,tt,t;
while(scanf("%d%d",&a,&b)==2&&a+b)
{
tt=1;
while(1)
{
if(b>a)
{
t=a;
a=b;
b=t;
}
if(a%b==0||a/b>=2)
break;
tt=!tt;
a=a%b;
}
if(tt==1)
printf("xiaoming wins
");
else
printf("xiaohong wins
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
수학은 공통 테스트를 그래프로.Mac OS Catanalina 버전 10.15.6 언어 : Python Spyder 그래프와 Python을 사용하여 친숙한 것을 만지고 싶었습니다. 문제 함수 y = sin θ+√3 cos(θ) (0 <= θ <=...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
