조세 프 링 문제 의 수학 해법

문제 설명: 이미 알 고 있 는 n 명 (번호 1, 2, 3... n 으로 각각 표시) 이 원탁 주위 에 둘 러 앉 았 다.번호 가 k 인 사람 부터 번 호 를 매기 고 m 까지 센 사람 이 나 옵 니 다.그의 다음 사람 은 또 1 부터 숫자 를 매기 기 시 작 했 고 m 까지 센 그 사람 이 또 나 왔 다.원탁 주위 사람들 이 모두 나 올 때 까지 이 규칙 을 반복 한다.마지막 남 은 사람의 초기 번 호 를 구하 세 요.
    문 제 를 n 개인 (번호 0 ~ (n - 1) 으로 전환 하여 0 부터 번 호 를 보고 하고 (m - 1) 의 탈퇴 로 보고 하 며 나머지 는 0 부터 계속 번 호 를 보고 할 수 있 습 니 다. 승자 의 번 호 를 구하 면 얻 은 해 1 을 더 하면 원래 문제 의 해 입 니 다.
      일반적으로 우 리 는 하나의 순환 대기 열 을 사용 하여 조세 프 링 의 구 해 과정 을 모 의 한다. 그러나 n 이 비교적 클 때 모 의 방식 으로 구 해 를 하려 면 탈퇴 과정 을 모 의 하 는 데 많은 시간 이 필요 하 다. 또한 대량의 메모리 공간 을 차지 하여 대기 열 에 있 는 n 개인 을 모 의 해 야 하기 때문에 좋 은 해법 이 아니다. 대부분의 상황 에서 우 리 는 가장 많은 것 만 알 아야 한다.그 다음 에 그 사람의 번 호 는 이런 과정 을 모 의 하 는 것 이 아니 라 이런 상황 에서 수학 공식 이 존재 하 는 지 마지막 사람의 번 호 를 직접 구 할 수 있 는 지 를 고려 할 수 있다.
       우 리 는 첫 번 째 사람 (번 호 는 반드시 m% n - 1) 이 나 온 후에 나머지 n - 1 명 이 새로운 조세 프 링 을 구성 했다 는 것 을 알 고 있다.: 우 리 는 먼저 첫 번 째 사람 이 나 온 후의 상황 을 보면 알 수 있 습 니 다. 첫 번 째 로 나 온 사람의 번 호 는 반드시 m% n - 1 입 니 다. 이 사람 이 나 온 후에 나머지 n - 1 사람 이 새로운 조세 프 링 을 만 들 었 습 니 다. 이 조세 프 링 의 첫 번 째 사람 이 처음에 나 온 링 에서 의 번 호 는 k = m% n (첫 번 째 로 나 온 사람의 다음) k 입 니 다.  k+1  k+2  ... n - 2, n - 1, 0, 1, 2,... k - 2 그리고 k 부터 0 을 보고 합 니 다.    사실 첫 번 째 로 열 거 된 사람의 번호 m% n - 1 = k - 1 은 그 가 열 거 된 후에 나머지 사람들 은 또 하나의 새로운 고리 가 되 었 다.
   원 번호  새 번호    k     ---      0    k+1 ---     1   k+2 ---      2     ...  ....
   n-1 ---   n-k-1
   0    ---    n-k
   1    ---   n-k+1
        ...  ...
   k-3 ---     n-3
   k-2  ---    n-2
  (k - 1 이미 정렬 됨)
하나의 순환
        이 를 통 해 알 수 있 듯 이 이것 이 바로 원래 문제 에서 n 을 n - 1 로 교체 하 는 상황 이다. 최종 승 리 를 설정 한 사람 은 이런 번호 환경 에서 (이미 하나의 요 소 를 열거 하고 번호 범 위 는 0 - - n - 2) 의 번 호 를 x 로 설정 하면 우 리 는 이 사람 이 원래 번호 환경 (초기 번호 범위 0 - n - 1) 에서 의 번호 (x + k)% n 을 구 할 수 있다.
        우 리 는 f (n) 로 n 개인의 상황 (번호 환경) 에서 의 승자 의 번 호 를 표시 하면 우리 가 요구 하 는 것 은 f (n) 이다.
        그럼 n - 1 명 아래 에 있 는 이 x 를 어떻게 알 아 요? yes, 바로 n - 2 명 상황 에서 얻 은 x '를 되 돌려 줍 니 다. 그러면 n - 2 상황 에서 의 x' 를 어떻게 알 아 요? 당연히 n - 3 명 을 구 하 는 것 입 니 다. 이것 이 바로 재 귀 하 는 과정 입 니 다. f(n) = (f(n-1)+m)%n.
        마지막 에 한 사람 (최신 번호 0) 이 남 았 을 때 m 가 몇 이 든 이 사람 은 항상 승자, 즉 f (1) = 0 이다.
        이상 의 추리 에 근거 하여 전달 식 을 얻 을 수 있다.        f(1) = 0       f(n) = (f(n-1)+m)%n        그러면 우 리 는 f (n) 를 요구 하면 f (1) 에서 되 돌리 면 된다.
(주의 하 세 요. 우리 의 이 알고리즘 은 번 호 를 1 - n 으로 0 - n - 1 로 바 꾸 었 기 때문에 마지막 으로 구 한 번호 + 1 이 야 말로 최초의 문제 의 풀이 입 니 다. 즉, f (n) + 1 입 니 다.

int f(int n, int m)
   {
       int r = 0;// f(1)=0;
       for(int i = 2; i <= n; i++)
           r = (r + m) % i;// f(i)=[f(i-1)+m]%n;
       return r + 1; // f(n)=1；
    }

        이런 방법 은 시 뮬 레이 션 방법 보다 훨씬 빠르다. 우 리 는 문제 에 부 딪 혔 을 때 수학 공식 이 있 는 지 생각해 볼 수 있다.
       출처 참고: Jackie ` s blog