OpenJudge 2746 조세프 질문 1

 1 #include<stdio.h>

 2 typedef struct Node

 3 {

 4     int data;

 5     Node *next;

 6     Node(int i){   //Node  

 7         data=i;

 8         next=NULL;

 9     }

10 }node;

11 int main()

12 {

13     int i,m,n;

14     node *head,*p,*q;

15     while(scanf("%d%d",&n,&m),m||n)

16     {

17         if(m==1)              // ，m==1 ， 

18         {

19             printf("%d
",n);

20             continue;

21         }

22         head=new Node(1);//  

23         for(p=head,i=2;i<=n;i++)//   

24         {

25             q=new Node(i);//  

26             q->next=p->next;

27             p->next=q;

28             p=q;

29         }

30         p->next=head;// ，  

31         for(p=head;p->next!=p;p=p->next)// m  

32         {

33             for(i=1;i<m-1;i++)

34             p=p->next;

35             q=p->next;

36             p->next=q->next;

37             delete q;

38         }#include<stdio.h>

39 typedef struct Node

40 {

41     int data;

42     Node *next;

43     Node(int i){   //Node  

44         data=i;

45         next=NULL;

46     }

47 }node;

48 int main()

49 {

50     int i,m,n;

51     node *head,*p,*q;

52     while(scanf("%d%d",&n,&m),m||n)

53     {

54         if(m==1)              // ，m==1 ， 

55         {

56             printf("%d
",n);

57             continue;

58         }

59         head=new Node(1);//  

60         for(p=head,i=2;i<=n;i++)//   

61         {

62             q=new Node(i);//  

63             q->next=p->next;

64             p->next=q;

65             p=q;

66         }

67         p->next=head;// ，  

68         for(p=head;p->next!=p;p=p->next)// m  

69         {

70             for(i=1;i<m-1;i++)

71             p=p->next;

72             q=p->next;

73             p->next=q->next;

74             delete q;

75         }

76         printf("%d
",p->data);

77     }

78     return 0;

79 } 

80             

81 

82         printf("%d
",p->data);

83     }

84     return 0;

85 } 

86             

1. 첫 번째 방법: 분석: m개의 원소를 포함하는 수조를 설정하고 초기값은 수조의 모든 원소를 1에 놓는다.첫 번째 원소부터 순서대로 수조 원소를 더하고 n이 되면 이 원소의 하표를 출력한다.그리고 이 원소를 0으로 정리해 나중에 덧붙일 때 더 이상 작용하지 않도록 하는 것은 이 사람이 이미 아웃된 것과 같다.다음 원소부터 순서대로 수조 원소를 더하고 n이 될 때 이 원소의 하표를 출력합니다. 이렇게 하면 m개의 값을 출력한 후에 끝납니다.
2. 두 번째 방법 분석은 순환 체인 테이블로 문제를 해결하려면 먼저 하나의 순환 체인 테이블을 구성해야 한다. 순환 체인 테이블을 구성하는 방법은 매우 간단하다. 마지막 사람의 다음 지침을 첫 번째 사람에게 가리키기만 하면 하나의 링을 구성한다. 그림에서 보듯이 순환 체인 테이블을 구성한 후에 순환 체인 테이블이 한 사람이 남을 때까지 삭제 작업을 할 수 있다.
3. 세 번째 방법은 방법 2의 연상에 따라 수조 원소의 값이 다음 수조 원소의 하표로 링을 구성하는 것을 통해 수조 하표인지 수조로 이전 원소를 뛰어넘어 다음 원소와 연결시키고 이미 링에서 나온 원소에 접근하지 않아 속도를 높일 수 있다.m개의 원소를 포함하는 수조를 설정하고, 각 수조 원소에 연결된 다음 원소의 번호를 저장합니다.누군가가 동그라미를 벗어날 때 대응하는 원소의 값을 앞의 원소에 넣어 앞의 원소가 이 원소를 뛰어넘어 다음 원소와 연결되게 하여 이미 동그라미가 나온 원소에 더 이상 접근하지 않게 한다.다섯 사람이 한 바퀴 도는 것을 예로 들면 수조 a가 다음과 같은 형식으로 데이터를 저장하기 시작한다. 수조 원소 A[1] A[2] A[3] A[4] A[5] 데이터 23451이 세 번째 사람이 원을 나갈 때 원소 a[3]의 값 4를 a[2]에 넣고 원소 a[2]가 원소 a[4]와 직접 연결된다.
4. 네 번째 방법은 우리로 하여금 수학 지식을 활용하고 추이 공식을 귀납할 수 있는지를 더욱 생각하게 한다.예를 들어 5명이 3으로 번호를 매긴 경우 3,1,5,2,4의 순서를 얻을 수 있다. 여기서 마지막 아웃사이더의 번호는 4이다. 실제로 첫 번째 아웃사이더(번호 3)가 아웃된 후에 번호 4와 5를 하나의 요소로 옮기면 나머지 4명이 계속 3으로 번호를 매긴 것으로 볼 수 있다. 나머지 4명을 다시 상술한 대로 처리하면 마지막 아웃사이더의 번호는 위치 1에 있다.일반적인 상황으로 확대한다. 즉, 모두 m명이 제s인으로부터 번호를 보고하기 시작하고 n에 따라 번호를 보고하는 경우 나머지 I인이 있을 때 제s번호의 사람이 아웃된 후에 뒤의 원소를 위로 옮기고 아웃사이더 번호의 추이 공식을 귀납한다. s(아웃사이더 번호)=(s+n-1)modI.예를 들어 모두 16명이 있는데 1인부터 번호를 매기고 8번을 매기는 경우 상기 추이 공식에 따라 계산하면 첫 번째 아웃사이더의 번호는 s=(1+8-1)mod 16은 8이고 나머지 15(즉 I=15)명은 두 번째 아웃사이더의 번호가 s=(8+8-1)mod 15는 0이다. 이 때는 특례이고 s=0일 때 아웃사이더 번호가 배수이자 마지막 번호(s=0일 때 s=I의 15번)이다.위치 1에서 마지막 아웃사이더 번호