SCAU：18063 圈中的游戏

18063?圈中的游戏

时间限制:1000MS? 代码长度限制:10KB
提交次数:0 通过次数:0

题型: 编程题???语言: G++;GCC;VC

Description

有n个人围成一圈，从第1个人开始报数1、2、3，每报到3的人退出圈子。编程使用链表找出最后留下的人。

输入格式

输入一个数n，1000000>=n>0 

输出格式

输出最后留下的人的编号

输入样例

3

输出样例

2

若不使用链表的第一种方法

#include <stdio.h>
#define N 1000000

int main()
{
    int a[N], n, m=0, i=0, count=0;
    scanf("%d", &n);
    for(i=0; i<n; i++)
        a[i] = 0;//数组初始化0，表示在圈内的人
    while(count < n-1)//出去n-1个人，此循环才会结束
    {
        if(a[i] == 0)
        {
            m++; //从1开始报数
            if(m==3)
            {
                a[i] = 1;//表示此人已经出圈
                count++;
                m=0;//重置，再从1开始报数
            }
        }
        i++;//遍历数组元素
        if(i==n)//数了一圈，从头来过
            i=0;
    }
    i=0;
    while(a[i])//找到a[i]==0 的下标。 while(a[i]) 是一个条件判断语句。它的作用是检查数组 a 中索引 i 处的元素是否为真（非零）。在C语言中，数组中的元素为0被视为假，非零元素被视为真。
        i++;
    printf("%d", i+1);//注意要+1，才是圈子里的序号
    return 0;
}

不使用链表的第二种

#include <stdio.h>

int lastRemaining(int n) 
{
    int i, last = 0; // 最后剩下的人的初始编号为0

    // 对于每一轮，i 从 2 开始，每次循环只剩下一个人时结束
    for (i = 2; i <= n; i++)
        last = (last + 3) % i; // 根据规则计算下一个要被删除的人的编号

    return last + 1; // 返回最后剩下的人的编号
}

int main() 
{
    int n;
    scanf("%d", &n);
    printf("%d\n", lastRemaining(n));
    return 0;
}

使用链表的方法

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

struct Node {
    int data;
    struct Node *next;
};

struct Node *createList(int n) {
    struct Node *head = NULL, *temp = NULL, *current = NULL;
    int i;

    for (i = 1; i <= n; i++) {
        temp = (struct Node *)malloc(sizeof(struct Node));
        temp->data = i;
        temp->next = NULL;

        if (head == NULL) {
            head = temp;
            current = temp;
        } else {
            current->next = temp;
            current = temp;
        }
    }
    current->next = head; // 将最后一个节点指向头节点，形成循环链表
    return head;
}

int findLast(struct Node *head, int n) {
    struct Node *prev = NULL, *current = head;
    int count = 1;

    while (current->next != current) {
        if (count == 3) {
            prev->next = current->next;
            free(current);
            current = prev->next;
            count = 1;
        } else {
            prev = current;
            current = current->next;
            count++;
        }
    }

    int lastRemaining = current->data;
    free(current); // 释放最后一个节点的内存
    return lastRemaining;
}

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

    struct Node *head = createList(n);
    int lastRemaining = findLast(head, n);
    printf("%d\n", lastRemaining);

    return 0;
}