约瑟夫问题

我就是我 2022-05-16 06:06 204阅读 0赞

Problem Description  
n个人想玩残酷的死亡游戏，游戏规则如下：

n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被杀，剩下的人继续游戏，活到最后的一个人是胜利者。

请输出最后一个人的编号。  
Input  
输入n和m值。  
Output  
输出胜利者的编号。  
Sample Input  
5 3  
Sample Output  
4  
知识点在于循环建表和选择函数的建立：  
1 循环建表：他和普通建表区别在于最后让尾节点指向头结点；tail->next=head;

2:挑选输出函数；

挑选函数需要的是：循环链表的头指针：链表节点个数：出圈数；  
函数内部：1定义：需要定义 报数的计数变量：和删除的个数，定义所要删除的 节点和他的前驱节点；  
2，让前驱节点指向尾节点： 让q先指向head，然后一个while循环，让q指向尾节点；  
3，下面报数循环：因为要删除n-1个数，所以删数变量小于n-1才能执行，不能等于，因为等于再执行就会删掉最后一个数，循环内部：我永远删除p 这个节点，而q是p的前驱节点就导致删除后，p永远指向删除后的下一节点，所以内部是p=q->next ;  
循环外部定义S报数变量为0，也就是说首次循环s为0；s++;就是在报数，  
当s==m的时候，这时候就要将p删去；也就是让p->next  
赋值给q->next;free(q);因为要统计删去的个数，所以cn++;以为s的值已经发生了改变，要下次循环s为0；所以s=0;  
当s不为m的时候，需要让q=p让q向下移动一步，在下次循环p=q->next;p也移动一下。  
因为你删去最后的是p，所以你返回的必须是q。

#include<stdio.h>
    #include <stdlib.h>
    struct node
    {
        int data;
        struct node *next;
    };
    struct node *creat(int N)
    {
        struct node *head,*tail,*p;
        int i;
        p=(struct node *)malloc(sizeof(struct node));
        p->data=1;
        p->next=NULL;
        head=p;tail=p;
        for(i=2; i<=N; i++)
        {
            p=(struct node*)malloc(sizeof(struct node));
            p->data=i;
            p->next=NULL;
            tail->next=p;
            tail=p;
        }
        tail->next=head;
        return head;
    }
    
    
    int sel(struct node *head,int n,int m)
    {
        int s=0;
        int cn=0;
        struct node *p,*q;
        q=head;
        while(q->next!=head)
        {
            q=q->next;
        }
        while(cn<n-1)
        {
            p=q->next;
            s++;
            if(s==m)
            {
                q->next=p->next;
                cn++;
                free(p);
                s=0;
            }
            else
                q=p;
        }
        return q->data;
    }
    
    int main()
    {
    
        int n,m;
        struct node *head;
        scanf("%d %d",&n,&m);
        head=creat(n);
        printf("%d\n",sel(head,n,m));
        return 0;
    }
    
    中间部分改成这样更加好记：
    
    
    struct node *creat(int N)
    {
        struct node *head,*tail,*p;
        int i;
        head=(struct node *)malloc(sizeof(struct node));
        head->data=1;
        head->next=NULL;
        tail=head;
        for(i=2; i<=N; i++)
        {
            p=(struct node*)malloc(sizeof(struct node));
            p->data=i;
            p->next=NULL;
            tail->next=p;
            tail=p;
        }
        tail->next=head;
        return head;
    }