C/C++고전 알고리즘 의 조세 프 문제 에 대한 상세 한 설명

조세 프 문제 가 무엇 입 니까? 
조세 프 문제:n 명 이 한 바퀴 를 돌 고 초기 번 호 는 1~n 으로 배열 되 었 다.약속 번호 가 x 인 사람 부터 번 호 를 매기 기 시 작 했 고 m 명 이 한 바퀴 를 돌 았 다.그 다음 에 1 부터 번 호 를 매기 기 시 작 했 고 m 번 째 숫자 에 도달 한 사람 은 다시 한 바퀴 를 물 러 났 다.이런 식 으로 미 루 면 마지막 권 에 한 사람 만 남 았 다.이 사람 이 바로 승자 이 고 승자 의 번 호 를 구 했다.
좀 복잡 하지 않 습 니까?사실 이 문 제 는 아 날로 그 유형의 알고리즘 문제 로 귀결 되 고 문제 의 요구 에 따라 아 날로 그 하면 됩 니 다.
이봐,코드 한 줄 로 조세 프 문 제 를 해결 하 자!
？？？가다
조급해 하지 마라,우리 한 걸음 한 걸음 공부 하 자.
방법 1:배열
이 문 제 를 처음 만 났 을 때 나 는 배열 로 만 들 었 다.나 는 절대 다수의 사람들 도 어떻게 하 는 지 알 고 있 을 것 이 라 고 추측 했다.방법 은 다음 과 같다.
하나의 배열 로 1,2,3...n 이라는 n 개의 번 호 를 저장 합 니 다.그림(여기 서 우 리 는 n=6,m=3 을 가정 합 니 다)

 그리고 끊임없이 배열 을 옮 겨 다 니 며 선 택 된 번호 에 대해 우 리 는 표 시 를 합 니 다.예 를 들 어 번호 arr[2]=3 이 선택 되 었 습 니 다.그러면 우 리 는 표 시 를 할 수 있 습 니 다.예 를 들 어 arr[2]=-1 은 arr[2]에 저 장 된 번호 가 이미 아웃 되 었 음 을 표시 합 니 다.

그 다음 에 이런 방법 에 따라 배열 을 옮 겨 다 니 며 계속 표 시 를 합 니 다.배열 에 하나의 요소 만 있 을 때 까지-1 이 아 닙 니 다.그러면 나머지 요 소 는 우리 가 찾 는 요소 입 니 다.제 가 시범 을 보 여 드릴 게 요.
 
이런 방법 은 간단 합 니까?생각 은 간단 하지만 인 코딩 은 그리 간단 하지 않 습 니 다.임계 조건 이 특히 많 습 니 다.배열 의 마지막 요 소 를 옮 겨 다 닐 때마다 아래 표 시 를 0 으로 다시 설정 하고 옮 겨 다 닐 때 이 요소 가-1 인지 판단 해 야 합 니 다.이런 배열 의 방식 으로 하면 절대 간단 하 다 고 생각 하지 마 세 요.인 코딩 과정 은 여전히 사람 을 매우 시험 합 니 다.
이런 방법의 시간 복잡 도 는 O(n*m)이 고 공간 복잡 도 는 O(n)이다.
다음은 배열 방법의 참고 코드 를 드 립 니 다.

#include<algorithm>
#include<iostream>
using namespace std;
int main(){
	int a[1001]={0}; //         
	int n,m;//n      ，m        
	cin>>n>>m;
	int count=0;//       
	int k=-1;//           ，   0，   1，     x  ， k=x-2
	while(count<n-1){  //      n-1  
		int i=0;//        
		while(i<m){
			k=(k+1)%n; //      
			if(a[k]==0){
				i++;
				if(i==m){
					a[k]=-1;
					count++;
				}
			}
		}
	}
	for(int i=0;i<n;i++){
		if(a[i]==0){
			printf("%d
",i+1);
			break;
		}
	}
	return 0;
}

방법 2:링 링크
링크 를 배 운 사람 은 모두 링크 로 조세 프 링 문 제 를 처리 할 것 이다.링크 로 처리 하 는 것 은 위 에서 처리 하 는 사고 와 차이 가 많 지 않다.링크 로 처리 할 때 선 택 된 번호 에 대해 표 시 를 하 는 것 이 아니 라 직접 제거 하 는 것 이다.링크 에서 한 요 소 를 제거 하 는 시간 복잡 도가 낮 고 O(1)이기 때문이다.물론 위의 배열 의 방법 도 제거 하 는 방식 을 사용 할 수 있 지만 배열 이 제거 하 는 시간 복잡 도 는 O(n)이다.그래서 체인 테이블 의 해결 방법 은 다음 과 같다.
1.요 소 를 저장 하기 위해 링 링크 를 만 듭 니 다.

2.그리고 링크 를 옮 겨 다 니 며 삭제 합 니 다.링크 가 한 노드 만 남 을 때 까지 저 는 여기 서 모두 보 여 드 리 지 않 습 니 다.
 
관심 있 는 친 구 는 스스로 다음 코드 를 실현 할 수 있 으 니,여 기 는 놓 지 않 겠 습 니 다.
조세 프 문 제 를 어떻게 실현 하 는 지 살 펴 보 자!
방법 3:귀속
사실 이 문 제 는 재 귀 로 해결 할 수 있다.재 귀 는 우리 가 누 군 가 를 삭제 할 때마다 우 리 는 이 사람들 에 게 다시 번 호 를 매 긴 다 는 것 이다.그리고 우리 의 어 려 운 점 은 삭제 전과 삭제 후 번호 의 매 핑 관 계 를 찾 는 것 이다.
우 리 는 재 귀 함수 f(n,m)의 반환 결 과 를 생존 병사 의 번호 로 정의 합 니 다.분명히 n=1 일 때 f(n,m)=1 입 니 다.만약 우리 가 f(n,m)와 f(n-1,m)간 의 관 계 를 찾 을 수 있다 면 우 리 는 재 귀적 인 방식 으로 해결 할 수 있 을 것 이다.우 리 는 인원 수가 n 이 라 고 가정 하고 m 에 신고 한 사람 은 자살 한다.처음
… 1 ... m - 2
m - 1
m
m + 1
m + 2 ... n …
한 번 삭제 한 후에 번호 가 m 인 노드 를 삭제 했다.삭제 후 n-1 개의 노드 만 남 았 습 니 다.삭제 전과 삭제 후의 번호 변환 관 계 는 다음 과 같 습 니 다.
삭제 전---삭제 후
… --- …
m - 2 --- n - 2
m - 1 --- n - 1
m----없 음(번호 가 삭제 되 었 기 때 문)
m+1---1(다음 부 터 는 여기 서 번 호 를 매기 기 때문이다)
m + 2 ---- 2
… ---- …
새로운 링 에는 n-1 개의 노드 만 있 습 니 다.또한 삭제 전 번 호 는 m+1,m+2,m+3 의 노드 가 삭제 후 번호 가 1,2,3 의 노드 가 되 었 다.
old 가 이전의 노드 번 호 를 삭제 하기 위해 new 가 한 노드 뒤의 번 호 를 삭제 하기 위해 old 와 new 간 의 관 계 는 old=(new+m-1)%n+1 이다.
 주:어떤 사람들 은 왜 old=(new+m)%n 이 아 닌 지 의심 할 수 있 습 니 다.번 호 는 0 에서 시작 하 는 것 이 아니 라 1 에서 시작 하기 때문이다.new+m==n 이면 마지막 계산 결 과 는 old=0 입 니 다.그래서 old=(new+m-1)%n+1.이렇게 하면 우 리 는 f(n,m)와 f(n-1,m)간 의 관 계 를 얻 을 수 있 고 f(1,m)=1.그래서 우 리 는 재 귀적 인 방식 으로 할 수 있다.
 코드 는 다음 과 같 습 니 다:

int f(int n, int m){
    return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1;
}

침대,나중에 누군가가 조세 프 문 제 를 손 으로 쓰 라 고 했 으 니 이 코드 를 던 져 주세요. 
총결산
C/C++고전 알고리즘 의 조세 프 문제 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 C/C+조세 프 문제 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!