最新公告
  • 欢迎您光临欧资源网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 第一个:令i个人玩游戏报m退出最后胜利者的编号

    问题描述:n个人(编号为0~(n-1)),从0开始计数,报告(m-1))退出,其余从0继续计数。求胜人的号码。

    我们知道第一个人(编号必须是m%n-1))出队,剩下的n-1个人组成一个新的约瑟夫环(从编号为k=m%n的人开始):

    k k+1 k+2 … n-2, n-1, 0, 1, 2, … k-2

    并从 k 开始报告 0。

    现在让我们转换他们的数字:

    k –> 0

    k+1 –> 1

    细三角环视频解法_m环想细解法_m环解法

    k+2 –> 2

    k-2 –> n-2

    k-1 –> n-1

    转化后就变成了(n-1)个人举报的子问题。如果我们知道这个子问题的解法:比如x是最后的赢家,那么根据上表不就是n人情况的解法吗?!!改回来的公式很简单,相信大家都能推导出来:x’ =(x+k)%n

    m环想细解法_m环解法_细三角环视频解法

    怎么知道(n-1)个人上报问题的解法?对m环想细解法,只要知道(n-2)个人的解法。(n-2)个人解法?当然可以) ) 是先求(n-3))的情况—-这显然是一个倒退问题!嗯,思路出来了,递归公式写如下:

    设 f[i] 表示我玩游戏并报告 m 退出的最后一个获胜者的号码,最终结果自然是 f[n]

    递归公式

    f[1]=0;

    f[i]=(f[i-1]+m)%i; (i>1)

    有了这个公式,我们只需要从 1-n 阶计算 f[i] 的值m环想细解法,最终的结果就是 f[n]。由于在现实生活中编号总是从 1 开始,我们输出 f[n]+1

    由于是逐级递归的,所以不需要保存每个f[i],程序也很简单:

    主函数()

    {

    整数 n,m,i,s=0;

    scanf(“%d%d”, &n, &m);

    对于 (i=2; 我

    站内大部分资源收集于网络,若侵犯了您的合法权益,请联系我们删除!
    欧资源网 » 第一个:令i个人玩游戏报m退出最后胜利者的编号

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    欧资源网
    一个高级程序员模板开发平台

    发表评论