建设部网站1667号公告,微信商城定制,海口专业网站建设地址,综合门户网站有哪些18063 圈中的游戏
时间限制:1000MS 代码长度限制:10KB 提交次数:0 通过次数:0
题型: 编程题 语言: G;GCC;VC Description
有n个人围成一圈#xff0c;从第1个人开始报数1、2、3#xff0c;每报到3的人退出圈子。编程使用链表找出最后留下的人。输入格式
输入一个数n;GCC;VC Description
有n个人围成一圈从第1个人开始报数1、2、3每报到3的人退出圈子。编程使用链表找出最后留下的人。
输入格式
输入一个数n1000000n0
输出格式
输出最后留下的人的编号 输入样例
3
输出样例
2
若不使用链表的第一种方法
#include stdio.h
#define N 1000000int main()
{int a[N], n, m0, i0, count0;scanf(%d, n);for(i0; in; i)a[i] 0;//数组初始化0表示在圈内的人while(count n-1)//出去n-1个人此循环才会结束{if(a[i] 0){m; //从1开始报数if(m3){a[i] 1;//表示此人已经出圈count;m0;//重置再从1开始报数}}i;//遍历数组元素if(in)//数了一圈从头来过i0;}i0;while(a[i])//找到a[i]0 的下标。 while(a[i]) 是一个条件判断语句。它的作用是检查数组 a 中索引 i 处的元素是否为真非零。在C语言中数组中的元素为0被视为假非零元素被视为真。i;printf(%d, i1);//注意要1才是圈子里的序号return 0;
}
不使用链表的第二种
#include stdio.hint 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.hstruct 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;
}
