首页 > 代码库 > 剑指offer系列源码-圆圈中最后剩下的数
剑指offer系列源码-圆圈中最后剩下的数
题目1356:孩子们的游戏(圆圈中最后剩下的数) 时间限制:10 秒内存限制:32 兆特殊判题:否提交:1073解决:391 题目描述: 每年六一儿童节,JOBDU都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为JOBDU的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为1的小朋友开始报数。每次喊到m的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续1...m报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到JOBDU名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢? 输入: 输入有多组数据。 每组数据一行,包含2个整数n(0<=n<=1,000,000),m(1<=m<=1,000,000),n,m分别表示小朋友的人数(编号1....n-1,n)和HF指定的那个数m(如上文所述)。如果n=0,则结束输入。 输出: 对应每组数据,输出最后拿到大奖的小朋友编号。 样例输入: 1 10 8 5 6 6 0 样例输出: 1 3 4
这个是个约瑟夫环的题:
解法一:使用链表解法容易超时
#include <iostream> #include<stdio.h> #include<algorithm> #include<list> using namespace std; int lastRemaining(unsigned int n,unsigned int m){ if(n<1||m<1){ return -1; } unsigned int i = 0; list<int> numbers; for(int i=1;i<=n;i++){ numbers.push_back(i); } list<int>::iterator current = numbers.begin(); while(numbers.size()>1){ for(int i=1;i<m;i++){ current++; if(current==numbers.end()){ current = numbers.begin(); } } list<int>::iterator next = ++current; if(next==numbers.end()){ next = numbers.begin(); } --current; numbers.erase(current); current = next; } return *current; } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF&&n){ printf("%d\n",lastRemaining(n,m)); } return 0; }
#include <iostream> #include<stdio.h> #include<algorithm> #include<list> using namespace std; int lastRemaining(unsigned int n,unsigned int m){ if(n<1||m<1){ return -1; } int last = 0; for(int i=2;i<=n;i++){ last = (last+m)%i; } return last+1; } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF&&n){ printf("%d\n",lastRemaining(n,m)); } return 0; }
剑指offer系列源码-圆圈中最后剩下的数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。