个人中心
gpt4 book ai didi

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

转载 作者：qq735679552 更新时间：2022-09-28 22:32:09 27 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章HDOJ 1443 约瑟夫环的最新应用分析详解由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

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)<k则此m不符合题意。 注意： 本题有几点需要注意，否则很容易超时； 第一点、运用公式j=(j+m-1)%(n-i)，推导出下一个出现的元素在第几号位置，如果j<k的话，不符合题意。 第二点、就是m,当只剩下k+1个数的时候，则上一个消失的数一定是在目前仅剩的bad左边或者是右边，所以m%(k+1)==0或者1 有了这两个条件，可以加快程序的速度。。。 完整的实现代码如下:

复制代码 代码如下

#include "stdio.h" #include "stdlib.h" int x[15]; /* 运用公式j=(j+m-1)%(len-i);推导出下一个出现的元素在第几号位置，如果j<k的话，不符合题意。 若有7个人，报到3的人依次出列 第一次 j=(j+m-1)%(len-i)=(0+3-1)%(7-0)=2   下标为2的3出列   新序列为  1 2 4 5 6 7 第二次 j=(j+m-1)%(len-i)=(2+3-1)%(7-1)=4   下标为4的6出列   新序列为  1 2 4 5 7 第三次 j=(j+m-1)%(len-i)=(4+3-1)%(7-2)=1   下标为1的2出列   新序列为  1 4 5 7 第四次 j=(j+m-1)%(len-i)=(1+3-1)%(7-3)=3   下标为3的7出列   新序列为  1 4 5 第五次 j=(j+m-1)%(len-i)=(3+3-1)%(7-4)=2   下标为2的5出列   新序列为  1 4 第六次 j=(j+m-1)%(len-i)=(2+3-1)%(7-5)=0   下标为0的1出列   新序列为  4 第七次 j=(j+m-1)%(len-i)=(0+3-1)%(7-6)=0   下标为0的4出列   新序列为空，至此，所有人已经全部出列，出列的顺序为：3 6 2 7 5 1 4 */ int test(int k,int m) {  int i,j=0,len=k*2;  for(i=0;i<k;i++)  {   j=(j+m-1)%(len-i);    //约瑟夫环公式   if(j<k)    return 0;     //遇到前k轮中有小于k的直接返回0  }  return 1; } /* 接下来说说m的取值范围：我们考察一下只剩下k+1个人时候情况，即坏人还有一个未被处决， 那么在这一轮中结束位置必定在最后一个坏人，那么开始位置在哪呢？这就需要找K+2个人的结束位置， 然而K+2个人的结束位置必定是第K+2个人或者第K+1个人，这样就出现两种顺序情况：GGGG.....GGGXB 或  GGGG......GGGBX (X表示有K+2个人的那一轮退出的人）所以有K+1个人的那一轮的开始位置有两种可能即最后一个位置或K+1的那个位置，限定m有两种可能： GGGG......GGGBX 若K+2个人的结束位置在最后一个(第K+2个)，则m%(k+1)==0 GGGG......GGGXB 若K+2个人的结束位置在倒数第二个(第K+1个)，则m%(k+1)==1 */ void Joseph(void) {  int m,k;  for(k=1;k<15;k++)  {   m=k+1;   while(1)   {    if(test(k,m))     // m%(k+1)==0的情况    {     x[k]=m;     break;    }    if(test(k,m+1))     // m%(k+1)==1的情况    {     x[k]=m+1;     break;    }    m+=k+1;   }  } } int main(void) {     int k;  Joseph();  while(scanf("%d",&k),k)   printf("%d\n",x[k]);  system("pause"); } 。

最后此篇关于HDOJ 1443 约瑟夫环的最新应用分析详解的文章就讲到这里了,如果你想了解更多关于HDOJ 1443 约瑟夫环的最新应用分析详解的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

27 4 0
文章推荐： 基于C语言sprintf函数的深入理解
文章推荐： 流量站用广告做网赚需注意的几个问题小结
文章推荐： 对7种博客赚钱方法的一些思考 最信赖Adsense
文章推荐： 深入Main函数中的参数argc,argv的使用详解
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com