데이터 구조 실천 - 원숭이 선왕
[프로젝트 - 원숭이 가 왕 을 선택한다] 원숭이 들, 번 호 는 1, 2, 3... m 입 니 다. 이 원숭이 들 (m 개) 은 1 - m 순서대로 한 바퀴 돌 았 습 니 다.첫 번 째 부터 n 번 째 까지 셀 때마다 이 원숭이 는 이 바퀴 를 떠 나 야 한다. 이렇게 순서대로 내 려 와 우리 에 마지막 원숭이 만 남 을 때 까지 이 원숭이 는 대왕 이다.m 와 n 을 입력 하면 대왕 으로 출력 되 는 원숭이 는 몇 번 입 니까?
알림: (1) 링크 해법: 원숭이 들 을 순환 단일 링크 로 표시 할 수 있 습 니 다.결점 을 나타 내 는 구조 체 에는 두 명의 구성원 이 있다. 하 나 는 원숭이 의 번 호 를 저장 하고 하 나 는 다음 사람 을 가리 키 는 지침 이 며, 번호 가 m 인 결점 은 번호 가 1 인 결점 을 가리 키 며 링 의 사슬 을 구성한다.n 번 째 까지 셀 때 이 결점 은 삭제 되 고 하나의 결점 만 있 을 때 까지 계속 세 어 집 니 다.(2) 구조 배열 을 사용 하여 순환 체인 을 나타 낸다. 구조 체 에 한 구성원 을 설치 하여 해당 하 는 원숭이 가 이미 도태 되 었 는 지 여 부 를 나타 낸다.첫 번 째 사람 이 탈락 하지 않 은 숫자 부터 n 까지 셀 때마다 구조 에 있 는 표 시 를 0 으로 바 꾸 어 원숭이 가 탈락 했다 는 뜻 이다.배열 의 m 번 째 요 소 를 센 후에 첫 번 째 숫자 부터 다시 시작 하여 m - 1 이 도 태 될 때 까지 순환 합 니 다.(3) 이 문 제 는 컴퓨터 과학 의 전형 적 인 문제 로 많은 실제 문 제 는 이런 모델 로 추상 화 할 수 있다.관심 있 는 학생 은 조세 프 문 제 를 검색 하 세 요.
[참고 해답 (C + + 구현)]
#include <iostream>
using namespace std;
struct Monkey
{
int num; //
struct Monkey *next; //
};
int main()
{
int m,n,i,j,king;
Monkey *head, *p1,*p2;
cin>>m>>n;
if(n==1)
{
king=m;
}
else
{
//
p1=p2=new Monkey;
head = p1;
p1->num=1;
for(i=1; i<m; i++) // m-1
{
p1=new Monkey; //p1
p1->num=i+1;
p2->next=p1;
p2=p1; //p2
}
p2->next=head; // ，
//
p1=head;
for(i=1; i<m; i++) // m-1 ， m-1
{
// p1 ， n-1 n
for(j=1; j<n-1; j++) // n-1 ，
p1=p1->next; // ， ，
// ，
p2=p1->next; //p2
//cout<<" "<<i<<" "<<p2->num<<endl; //
p1->next=p2->next; //p2 “ ”
p1=p2->next; //
delete p2; //
}
king=p1->num;
delete p1;
}
cout<<king<<endl;
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
