首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
n个数字(0,1,…,n-1)形成一个圆圈,从数字0开始,每次从这个圆圈中删除第m个数字(第一个为当前数字本身,第二个为当前数字的下一个数字)。当一个数字删除后,从被删除数字的下一个继续删除第m个数字。求出在这个圆圈中剩下的最后一个数字。
n个数字(0,1,…,n-1)形成一个圆圈,从数字0开始,每次从这个圆圈中删除第m个数字(第一个为当前数字本身,第二个为当前数字的下一个数字)。当一个数字删除后,从被删除数字的下一个继续删除第m个数字。求出在这个圆圈中剩下的最后一个数字。
admin
2019-03-29
46
问题
n个数字(0,1,…,n-1)形成一个圆圈,从数字0开始,每次从这个圆圈中删除第m个数字(第一个为当前数字本身,第二个为当前数字的下一个数字)。当一个数字删除后,从被删除数字的下一个继续删除第m个数字。求出在这个圆圈中剩下的最后一个数字。
选项
答案
/////////////////////////////////////////////////////////////////////// // n integers (0, 1, ... n - 1) form a circle. Remove the mth from // the circle at every time. Find the last number remaining // Input: n - the number of integers in the circle initially // m - remove the mth number at every time // Output: the last number remaining when the input is valid, // otherwise -1 /////////////////////////////////////////////////////////////////////// int LastRemaining_Solution1(unsigned int n, unsigned int m) { // invalid input if(n < 1 || m < 1) return -1; unsigned int i = 0; // initiate a list with n integers (0, 1, ... n - 1) list
integers; for(i = 0; i < n; ++ i) integers.push_back(i); list
::iterator curinteger = integers.begin(); while(integers.size() > 1) { // find the mth integer. Note that std::list is not a circle // so we should handle it manually for(int i = 1; i < m; ++ i) { curinteger ++; if(curinteger == integers.end()) curinteger = integers.begin(); } // remove the mth integer. Note that std::list is not a circle // so we should handle it manually list
::iterator nextinteger = ++ curinteger; if(nextinteger == integers.end()) nextinteger = integers.begin(); -- curinteger; integers.erase(curinteger); curinteger = nextinteger; } return *(curinteger); } 思路二的参考代码: /////////////////////////////////////////////////////////////////////// // n integers (0, 1, ... n - 1) form a circle. Remove the mth from // the circle at every time. Find the last number remaining // Input: n - the number of integers in the circle initially // m - remove the mth number at every time // Output: the last number remaining when the input is valid, // otherwise -1 /////////////////////////////////////////////////////////////////////// int LastRemaining_Solution2(int n, unsigned int m) { // invalid input if(n <= 0 || m < 0) return -1; // if there are only one integer in the circle initially, // of course the last remaining one is 0 int lastinteger = 0; // find the last remaining one in the circle with n integers for (int i = 2; i <= n; i ++) lastinteger = (lastinteger + m) % i; return lastinteger; }
解析
既然题目有一个数字圆圈,很自然的想法是我们用一个数据结构来模拟这个圆圈。在常用的数据结构中,我们很容易想到用环形列表。我们可以创建一个总共有m个数字的环形列表,然后每次从这个列表中删除第m个元素。
在参考代码中,我们用STL中std::list来模拟这个环形列表。由于list并不是一个环形的结构,因此每次跌代器扫描到列表末尾的时候,要记得把跌代器移到列表的头部。这样就是按照一个圆圈的顺序来遍历这个列表了。
这种思路需要一个有n个结点的环形列表来模拟这个删除的过程,因此内存开销为O(n)。而且这种方法每删除一个数字需要m步运算,总共有n个数字,因此总的时间复杂度是O(mn)。当m和n都很大的时候,这种方法是很慢的。
接下来我们试着从数学上分析出一些规律。首先定义最初的n个数字(0,1,…,n-1)中最后剩下的数字是关于n和m的方程为f(n,m)。
在这n个数字中,第一个被删除的数字是m%n-1,为简单起见记为k。那么删除k之后的剩下n-1的数字为0,1,…,k-1,k+1,…,n-1,并且下一个开始计数的数字是k+1。相当于在剩下的序列中,k+1排到最前面,从而形成序列k+1,…,n-1,0,…k-1。该序列最后剩下的数字也应该是关于n和m的函数。由于这个序列的规律和前面最初的序列不一样(最初的序列是从0开始的连续序列),因此该函数不同于前面函数,记为f’(n-1,m)。最初序列最后剩下的数字f(n,m)一定是剩下序列的最后剩下数字f’(n-1,m),所以f(n,m)=f’(n-1,m)。
接下来我们把剩下的的这n-1个数字的序列k+1,…,n-1,0,…k-1作一个映射,映射的结果是形成一个从0到n-2的序列:
k+1 -> 0
k+2 -> 1
…
n-1 -> n-k-2
0 -> n-k-1
…
k-1 -> n-2
把映射定义为p,则p(x)= (x-k-1)%n,即如果映射前的数字是x,则映射后的数字是(x-k-1)%n。对应的逆映射是p-1(x)=(x+k+1)%n。
由于映射之后的序列和最初的序列有同样的形式,都是从0开始的连续序列,因此仍然可以用函数f来表示,记为f(n-1,m)。根据我们的映射规则,映射之前的序列最后剩下的数字f’(n-1,m)= p
-1
[f(n-1,m)]=[f(n-1,m)+k+1]%n。把k=m%n-1代入得到f(n,m)=f’(n-1,m)=[f(n-1,m)+m]%n。
经过上面复杂的分析,我们终于找到一个递归的公式。要得到n个数字的序列的最后剩下的数字,只需要得到n-1个数字的序列的最后剩下的数字,并可以依此类推。当n=1时,也就是序列中开始只有一个数字0,那么很显然最后剩下的数字就是0。我们把这种关系表示为:
尽管得到这个公式的分析过程非常复杂,但它用递归或者循环都很容易实现。最重要的是,这是一种时间复杂度为O(n),空间复杂度为O(1)的方法,因此无论在时间上还是空间上都优于前面的思路。
转载请注明原文地址:https://kaotiyun.com/show/lRmZ777K
0
程序员面试
相关试题推荐
[A]Theperson-skillsmatchapproachtoselection[B]Theimpactsofbadselectiondecisions[C]Theimportanceofstructu
求1+2+…+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句(A?B:C)。
输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。 比如将二元查找树转换成双向链表4=6=8=10=12=14=16。
.asp.net如何实现MVC模式,举例说明!
组合问题(从M个不同字符中任取N个字符的所有组合)
值类型和引用类型的区别?写出C#的样例代码。
设置邮件发送于30天之前那么隐藏邮件。
邮件的删除。
在PPoint中,超级链接只有在()中起作用。A.幻灯片视图B.幻灯片放映C.幻灯片浏览视图D.大纲视图
若系统中存在n个等待事务Ti(i=0,1,2,…,n-1),其中:T0正等待被T1锁住的数据项A1,T1正等待被T2锁住的数据项A2,…,Ti正等待被Ti+1锁住的数据项Ai+1,…,Tn-1正等待被T0锁住的数据项A0,则系统处于___________状
随机试题
朱光潜,我国当代著名的______和______。他将______、______与______三者熔为一炉,形成,了其独特的美学思想。代表作有______、______、______等。其______和______等理论读物,深入浅出,内容切实,文笔流畅,
授权是指领导者授予下属一定的
急性呼吸窘迫综合征(ARDS)的主要发病环节是()。
判断水泥是否合格的指标包括()。
下列关于资产负债率、权益乘数和产权比率之间关系的表达式中,正确的是()。
“金无足赤,人无完人”,世界上很难找到一个全才的领导。况且,任何领导也难免由于工作需要而必须暂时离开工作岗位。这样为了不使自己行使权力的过程发生停滞或间断,你若作为某一部门或单位的领导,将怎样及时地把手中的一部分权力移出去由他人代为行使而不影响工作呢?
根据对组织的态度的不同可以将公众分为顺意公众、逆意公众和独立公众。顺意公众指的是对组织的政策和行为持赞赏和支持态度的公众;逆意公众指的是对组织的政策和行为持否定或反对态度的公众;独立公众指的是对组织的政策和行为持中间态度的公众。根据上述定义,以下属于顺意
文中成语“荼毒生灵”中的“荼”念作:根据这篇短文,下列对文章主旨理解最贴切的是:
如果使用恺撒密码,在密钥为4时attack的密文为______。
There_______somemisunderstandingbetweenthem,theyneversayhellotoeachother.
最新回复
(
0
)