资 源 简 介
资源描述每年新年派对的最后一个节目就是选出下年的“幸运之星”,有丰厚的大礼包的噢~~。 O(∩_∩)O
所以每位参加派对的人士都摩拳擦掌跃跃欲试。选择的办法是这样约定的:
(1)所有参与的人员数n,让n个人一字排开,然后至左向右从1开始报数,凡报到奇数号的全部后退剔除,剩下的人员,
又至左向右报数,逢奇剔除,如此不断的递归下去,直至只有一个人为止,这个人就是“幸运之星”。
(2)所有参与的人员数n,先随机抽取一个m值(从黑暗小箱中随机摸一个,m可能比n小或相等,也可能大于n),所有
参与的人员列成环形,然后从位置1开始报数,凡报到m的倍数的人后退剔除,剩下的人员,从刚才位置继续报数,逢m的
倍数的人剔除,如此不断的递归下去,直至只有一个人为止,这个人就是“幸运之星”。 如:n=8,m=4,如下图所示,幸
运之星为6号。现在,请你分析上面两种节目方式,若想获得幸运大礼包,应该选哪个初始编号的位置来站?
注意此题设置的时限很短,也就不建议你采用队列或循环列表去模拟这个剔除的过程而得到最后的解答。这里,我们更应
该分析一下,这个问题的递归思路。有了分析的递归公式,就可以在很短时间内完成“幸运之星”的计算。