Question

c与c++语言 求解Josephus问题

求解Josephus问题：设有n个数构成一个环链，要求从第k个数开始数数，数到m的那个数被弹出，然后从该数的下一个数重新数数，数到m的那个数又被弹出，如此重复，直到所有的数均被弹出为止。输出这些数弹出的序列。
如上 谢谢

Answer 1

#include <stdio.h>
#include <stdlib.h>
pNode* createCircleList(int n){
    pNode* head=(pNode*)malloc(sizeof(pNode));
    head->next=NULL;
    head->data=0;
    pNode* node=head;
    for(int i=1;i<n-1;i++){
        pNode* p=(pNode*)malloc(sizeof(pNode));
        p->data=i;
        p->next=NULL;
        node->next=p;
        node=node->next;
    }
    pNode* p=(pNode*)malloc(sizeof(pNode));
    p->data=n;
    p->next=head;
    node->next=p;
    return head;
}

pNode* find(pNode* head,int n){
    pNode* p=head;
    for(int i=1;i<n;i++)
        p=p->next;
    return p;
}

void remove(pNode* node,int m,int count){
    pNode* p=node;
    for(int i=0;i<count;i++){
        printf("%d ",p);
        p=p->next;
    }
    printf("\n");
    p=node;
    if(count!=1){
        for(int i=1;i<m-1;i++)
            p=p->next;
        pNode* pDel=p->next;
        p->next=pDel->next;
        pDel=NULL;
        free(pDel);
        remove(p->next,m,count-1);
    }else{
        node->next=NULL;
        free(node->next);
        printf("%d\n",p->data);
    }
}

int main()
{
    
    int n,k,m;
    scanf("%d %d %d",&n,&k,&m);
    pNode* head=createCircleList(n);
    printf("%d\n",head);
    pNode* start=find(head,k);
    printf("%d\n",start);
    remove(start,m,n);
}

输出的最后一个信息是数据，其他数据是为了方便理解和查看错误

Answer 2

这个用链表来实现非常简单，先创建一个环状的链表，首尾相连的，实现非常简单，手机回答的，就不贴程序了

Answer 3

1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 int didSolve(int n,int m) {
5 int p[50];
6 memset(p,0,sizeof(int)*50);
7
8 int i = 0;
9 int c = 0;
10 int r = n;
11 while(r != 1) {
12 c = 0;
13 while(c != m) {
14 if (p[i] == 0) {
15 printf("p(%d) say:%d\n",i+1,c);
16 c ++;
17 }
18 if (c == m) {
19 p[i] = 1;
20 printf("%d \n",i + 1);
21 }
22 i ++;
23 if (i == n) {
24 i = 0;
25 }
26 }
27 r --;
28 }
29 return 0;
30 }
31
32 int deal() {
33 int n=0,m=0;
34 scanf("%d %d",&n,&m);
35 didSolve(n,m);
36 return 0;
37 }
38 int main(int argc,char *argv[]) {
39 int testCase = 0;
40 scanf("%d",&testCase);
41 while(testCase --) {
42 deal();
43 }
44 return 0;
45 }