解决约瑟夫环问题（数据结构）

Question

#include<stdio.h>
#include<stdlib.h>
#include<string.h> 
typedef struct node{
    int data;  //存放密码 
    int number;  //存放序号 
    struct node* next;
}node;
  

int main(){
    int n,m;//人的个数 ,随机数 
    struct node *head=NULL;
    struct node *p,*q;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        p=(node*)malloc(sizeof(node));
        p->number=i+1;//人的序号 
        scanf("%d",&p->data);//人的密码
        p->next=NULL;
        if(head==NULL){//链表为空 
            head=p;
        } 
        else{
            q->next=p;
        }
        q=p;//都是尾节点 
    }
    if(head!=NULL){//如果链表不为空 
        q->next=head;
    }
    node* current = head;
    node* previous = NULL;
    //创建不带节点的循环单链表结束
    //遍历删除节点
    int Num=0,length=n;
    for(int i=0;i<n;i++)
    {
        node* temp=NULL; 
        Num=m%length;
        // 遍历链表找到待删除节点的前一个节点
        for (int i = 1; i < Num; i++) {
            previous = current;
            current = current->next;
        }
        temp=current;
        printf("%d ",current->number);
        m=current->data;//更新m值 
        // 如果删除的是头节点，需要更新头指针
        if (current == head) {
            head = current->next;
            }

        // 修改前一个节点的 next 指针，跳过当前节点
        if (previous != NULL) {
            previous->next = current->next;
        }

        // 释放当前节点的内存
        free(temp);
        length--;
        current=previous->next;
    } 
    
    return 0;
}
- 

-

我答案正确了，但是oj上边确给了25分，我不知道哪里出问题了，麻烦解惑

Answer 1

【以下回答由 GPT 生成】

问题分析

给定约瑟夫环的初始密码序列和随机数m，按照规则从初始密码序列中选取密码，每选取一个密码，就将该密码从序列中删除，并根据选取的密码的值更新随机数m。要求根据给定的n和m找到最终的密码序列。

解决方案

1. 首先，对给定的初始密码序列构建循环单链表。
2. 然后，根据给定的随机数m和密码序列的长度n，计算出待删除节点的序号Num。
3. 遍历链表找到待删除节点的前一个节点，并保存待删除节点的指针。
4. 将待删除节点从链表中断开，并更新头指针（如果删除的是头节点）或修改前一个节点的next指针（如果删除的是中间或尾节点）。
5. 重复步骤2-4，直到链表中只剩下一个节点。
6. 打印输出剩下的最后一个节点即为最终的密码。

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node {
    int data;
    int number;
    struct node* next;
} node;

int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    // 构建循环单链表
    node* head = NULL;
    node* p, * q;
    for (int i = 0; i < n; i++) {
        p = (node*)malloc(sizeof(node));
        p->number = i + 1;
        scanf("%d", &p->data);
        p->next = NULL;

        if (head == NULL) {
            head = p;
        }
        else {
            q->next = p;
        }
        q = p;
    }
    if (head != NULL) {
        q->next = head;
    }

    // 删除节点操作
    node* current = head;
    node* previous = NULL;
    int Num = 0, length = n;

    for (int i = 0; i < n; i++) {
        node* temp = NULL;
        Num = m % length;

        // 找到待删除节点的前一个节点
        for (int j = 1; j < Num; j++) {
            previous = current;
            current = current->next;
        }

        temp = current;
        printf("%d ", current->number);
        m = current->data; // 更新m值

        // 更新链表
        if (current == head) {
            head = current->next;
        }
        previous->next = current->next;
        current = current->next;
        free(temp);

        length--;
    }

    // 打印最终的密码
    printf("%d", head->data);

    // 释放链表内存
    current = head->next;
    while (current != head) {
        node* temp = current;
        current = current->next;
        free(temp);
    }
    free(head);

    return 0;
}

复杂度分析

• 构建循环单链表的时间复杂度为O(n)。
• 删除节点的过程需要遍历链表，时间复杂度为O(n)，并且每次删除一个节点，总共需要删除n个节点。
• 因此，整体的时间复杂度为O(n^2)。
• 空间复杂度为O(n)，用于存储链表节点的内存空间。

【相关推荐】

• 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/660714
• 我还给你找了一篇非常好的博客，你可以看看是否有帮助，链接：有关OJ中PE的一些解决方法（持续更新。。。）
• 除此之外, 这篇博客: 【牛客网OJ】扑克牌大小中的 输入描述: 部分也许能够解决你的问题。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^