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 1000000int 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;
}