Question

josephus problem 约瑟夫环 C语言

围成一个环
输入总人数n，报到m死，接着报数，输出最后剩下人的序号

Answer 1

//链表实现

#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
    int number;
    struct Node * next ;
}BOY, *PBOY ;

void print(PBOY H)
{
    //打印链表的值
    PBOY p ;

    printf("%d ", H->number) ;
    p = H->next ;
    while(p != H)
    {
        printf("%d ", p->number) ;
        p = p->next ;
    }
    printf("\n") ;
}

int main()
{
    int m, n, num = 1 ;
    PBOY    H ;
    BOY        *p, *q ;
    int i ;

    printf("m = ") ;
    scanf("%d", &m) ;
    printf("n = ") ;
    scanf("%d", &n) ;
    
    for(i = 1; i <= n; i++)    //根据人数建立链表
    {
        if(i == 1)
        {
            H = (PBOY)malloc(sizeof(BOY)) ;
            p = H ;
            H->number = 1 ;
            H->next = H ;
            continue ;
        }
        q = (PBOY)malloc(sizeof(BOY)) ;
        q->number = i ;
        q->next = p->next ;
        p->next = q ;
        p = q ;
    }

    printf("开始游戏:\n") ;
    print(H) ;
    printf("\n") ;

    //约瑟夫算法
    p = q = H ;
    while(p->next != p)
    {
        if(num % m == 0)
        {
            printf("%d号出队.\n剩余编号: ", p->number);//打印该节点值，并从链表删除该节点p
            q->next = p->next ;    //将p节点从链表中去掉
            free(p) ;    //释放节点
            p = q ;    //让p=q是为了和不出队时的代码统一，
            print(p->next) ;
            printf("\n") ;
        }
        q = p ;        //使用指针保留技术，记录p的前驱
        p = p->next ;
        num++ ;
    }
    printf("%d号胜利!\n", p->number) ;
    free(p) ;
    getchar() ;
    getchar() ;
    return 0 ;
}

Answer 2

还是要用数组吗？换其它方式可以吗？