Declaration: images and content based on www.bilibili.com/video/av783…

Subject overview

 

 

Circular linked list implementation

#include<bits/stdc++.h> using namespace std; typedef struct node{ int data; struct node *next; }Node,*Point; //typedef int main(){int n,m; Int count=0; // Answer array subscript int answer[301]; // Store the answer while(1){// keep loop cin>>n>>m; if(n==0||m==0) break; Else {Point head,tail,p,q; * (initializes the head Node) head=(Point)malloc(sizeof(Node)); Head ->next=NULL; tail=head; For (int I =0; i<n; P =(Point)malloc(sizeof(Node)); p=(Point)malloc(sizeof(Node)); P ->data= I +1; tail->next=p; p->next=head->next; // tail=p; } p=head->next; //p points to the first data node (non-sentinel) q=tail; //q is the precursor of p int I =1; While (q! If (I ==m){q->next=p->next; free(p); P =q->next; i=1; }else{q=p; p=p->next; i++; } } answer[count++]=p->data; free(p); Head ->next=NULL; }} for(int j=0; j<count; Cout <<answer[j]<<endl; }}Copy the code

Array flag bit implementation

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<cstdio> using namespace std; int main() { int n, m; int number; //number=n int count=1; Int I, pos; Int ans[301], answer = 0; while (~scanf("%d%d", &n, &m)) { if (n == 0 || m == 0) break; number = n; int monkey[301] = { 0 }; for ( i = 0; i < n; i++) { monkey[i] = i + 1; } pos = 0; While (number > 1) {// If (monkey[pos] > 0) {// If (count! // count++; pos = (pos + 1) % n; } else { monkey[pos] = 0; // Kill count = 1; // recount number--; Pos = (pos + 1) % n; } } else { pos = (pos + 1) % n; } } for ( i = 0; i < n; i++) { if (monkey[i] > 0) { //printf("%d\n", monkey[i]); ans[answer++] = monkey[i]; } } } for (i = 0; i<answer; i++) { cout << ans[i] << endl; } return 0; }Copy the code

Arrays mimic linked lists

#include<iostream> using namespace std; int main() { int n, m; int ans[301], answer = 0; while (1) { cin >> n >> m; if (n == 0 || m == 0) break; int count = 1; Int pos = 0; Int prior = n-1; Int monkey[301] = {0}; for (int i = 0; i < n; i++) { monkey[i] = (i + 1) % n; } // loop list int number = n; while (number > 1) { if (count ! = m) {// Prior = pos; pos = monkey[pos]; //monkey[pos] holds the next position of pos count++; } else {number--; // Kill count = 1; Monkey [prior] = monkey[pos]; Pos = monkey[pos]; // Prior changes to the previous pos position, skip pos pos = monkey[pos]; }} ans[answer++] = monkey[pos]+1; } for (int I = 0; i < answer; i++) { cout << ans[i] << endl; } return 0; }Copy the code

Final state