本文主要是介绍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;
}
这篇关于SCAU：18063 圈中的游戏的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
