조세 프 링 의 문제 해결 방법 과 분석

조세 프 링 의 문제
모두 가 조세 프 링 의 문 제 를 들 어 본 적 이 있 을 것 이 라 고 믿는다. 유명한 유 다 역사학자 조 셉 스 는 로마인 들 이 조 타 트 를 점령 한 후 39 명의 유태인 과 조 셉 스 및 그의 친구 들 이 숨 었 다 고 한다.
한 동굴 에서 39 명의 유태인 들 이 죽 을 지 언 정 적 에 게 잡 히 지 않 기로 결정 하여 자살 방식 을 결정 했다. 41 명 이 원 을 그 리 며 첫 번 째 사람 부터 숫자 를 매기 기 시 작 했 고 세 번 째 사람 에 게 보고 할 때마다 그 사람 은 반드시
모두 가 자살 할 때 까지 자살 한 다음 에 다시 신고 해 야 한다.그러나 Josephus 와 그의 친 구 는 따 르 고 싶 지 않 았 다. Josephus 는 그의 친구 에 게 먼저 따 르 는 척 하 라 고 했다. 그 는 친 구 를
자신 과 16 번 째 와 31 번 째 자리 에 앉 아 죽음 의 게임 을 피 했다.
공 부 를 잘 하면 당신 의 생명 을 구 할 수 있다 고 말 하 는 모든 사람들 이 열심히 공부 하 기 를 바 랍 니 다!!!
자, 이제 코드 로 이 문 제 를 해결 하려 고 합 니 다. 그리고 제 가 사용 하 는 것 은 링크 입 니 다.우 리 는 먼저 파 라 메 터 를 확인 해 야 한다. 우 리 는 조세 프 링 에 또 한 번 의 과정 이 필요 하 다 는 것 을 인정 해 야 한다.그래서.
파 라 메 터 는 링 링크 의 입구 점 과 num 입 니 다. 지금 우 리 는 그의 알고리즘 이 매우 간단 합 니 다. 이 문 제 를 언제 멈 출 지 생각해 야 합 니까?그것 이 바로 고리 안에 하나의 원소 만 남 았 을 때 다.
               .
               .
               .
               .
               .
               .
그래서 이 요소 의 next 가 자신의 머리 를 가리 키 면 그 가 바로 생존자 이다.
종료 조건 까지 판단 하면 그 반 은 성 공 했 습 니 다. 이제 순환 체 안에서 진행 된다 면?우 리 는 매번 결점 을 NUM 의 자 리 를 뒤로 옮 겨 야 한다. 사실은 num - 1 번 을 간 것 이다.
그 결점 의 내용 을 삭제 하면 됩 니 다.코드 실현 은 사실 매우 간단 하고 판단 조건 과 순환 방식 이 매우 관건 적 이다.
코드 는 다음 과 같 습 니 다:

pNode josephCycle(pList* pplist, int num) { pNode cur = *pplist; pNode del = *pplist; int i = 0; assert(pplist); if (*pplist == NULL) { printf("    
"); return NULL; } while (1) { i = num - 1; if (cur->next == cur) { break; } while (i--) { cur = cur->next; } printf(" kill ->%d
", cur->data); del = cur->next; cur->data = cur->next->data; cur->next = cur->next->next; free(del); } printf("win-> %d
", cur->data); return cur; }

결과: