HDOJ 1443 约瑟夫环的最新应用分析详解__30_n-i_Joseph_应用分_成一列_

当前位置: 编程技术>c/c++/嵌入式

HDOJ 1443 约瑟夫环的最新应用分析详解

来源: 互联网发布时间：2014-10-15

本文导语: k个男生和k个女生站成一列，前面k个是男生，后面k个是女生，从第一个男生开始报数，报到队列最后一个同学，循环到队首继续报，并且如果一个同学报到的数是m，这个同学就出列，然后后面的同学继续从1开始报数，现在求...

k个男生和k个女生站成一列，前面k个是男生，后面k个是女生，从第一个男生开始报数，报到队列最后一个同学，循环到队首继续报，并且如果一个同学报到的数是m，这个同学就出列，然后后面的同学继续从1开始报数，现在求一个数m，使k个女生全部出列，而男生没有出列。

输入：男生女生的个数k(男生女生人数相等都为k，输出：m值
例：输入：2，输出：7
输入：4，输出：30

本题是约瑟夫环变形先引入Joseph递推公式，设有n个人（0,...,n-1），数m，则第i轮出局的人为f(i)=(f(i-1)+m-1)%(n-i+1),f(0)=0; f(i) 表示当前子序列中要退出的那个人（当前序列编号为0~(n-i));
拿个例子说：K=4,M=30;

代码如下:

f(0)=0;
      f(1)=(f(0)+30-1)%8=5; 序列（0,1,2,3,4,5,6,7）中的5
      f(2)=(f(1)+30-1)%7=6; 序列（0,1,2,3,4,6,7）中的7
      f(3)=(f(2)+30-1)%6=5; 序列（0,1,2,3,4,6）中的6
      f(4)=(f(3)+30-1)%5=4; 序列（0,1,2,3,4）中的4
      ........

依据题意，前K个退出的人必定是后K个人，所以只要前k轮中只要有一次f(i)

您可能感兴趣的文章:

本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术，将尽最大努力为读者提供更好的信息聚合和浏览方式。
本站(WWW.)站内文章除注明原创外，均为转载、整理或搜集自网络。欢迎任何形式的转载，转载请注明出处。