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");
}

(0)

相关推荐

  • 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)%

  • Tornado 多进程实现分析详解

    引子 Tornado 是一个网络异步的的web开发框架, 并且可以利用多进程进行提高效率, 下面是创建一个多进程 tornado 程序的例子. #!/usr/bin/env python # -*- coding:utf-8 -*- import os import time import tornado.web import tornado.httpserver import tornado.ioloop import tornado.netutil import tornado.proces

  • Webpack source map实战分析详解

    目录 一.webpack基础 二.source-map 2.1 认识source-map 2.2 如何使用source-map 2.3 source-map文件分析 2.4 source-map常见值 2.5 source-map不常见值 2.6 source-map最佳实践 一.webpack基础 推荐我的另一篇文章:Webpack基础 二.source-map 2.1 认识source-map 代码通常运行在浏览器上时,是通过打包压缩的: 真实跑在浏览器上的代码,和我们编写的代码其实是有差异

  • Java CompletableFuture实现原理分析详解

    目录 简介 CompletableFuture类结构 CompletableFuture回调原理 CompletableFuture异步原理 总结 简介 前面的一篇文章你知道Java8并发新特性CompletableFuture吗?介绍了CompletableFuture的特性以及一些使用方法,今天我们主要来聊一聊CompletableFuture的回调功能以及异步工作原理是如何实现的. CompletableFuture类结构 1.CompletableFuture类结构主要有两个属性 pub

  • Java逃逸分析详解及代码示例

    概念引入 我们都知道,Java 创建的对象都是被分配到堆内存上,但是事实并不是这么绝对,通过对Java对象分配的过程分析,可以知道有两个地方会导致Java中创建出来的对象并一定分别在所认为的堆上.这两个点分别是Java中的逃逸分析和TLAB(Thread Local Allocation Buffer)线程私有的缓存区. 基本概念介绍 逃逸分析,是一种可以有效减少Java程序中同步负载和内存堆分配压力的跨函数全局数据流分析算法.通过逃逸分析,Java Hotspot编译器能够分析出一个新的对象的

  • Python日志打印里logging.getLogger源码分析详解

    实践环境 WIN 10 Python 3.6.5 函数说明 logging.getLogger(name=None) getLogger函数位于logging/__init__.py脚本 源码分析 _loggerClass = Logger # ...略 root = RootLogger(WARNING) Logger.root = root Logger.manager = Manager(Logger.root) # ...略 def getLogger(name=None): "&quo

  • C++ 匈牙利算法案例分析详解

    匈牙利算法是由匈牙利数学家Edmonds于1965年提出,因而得名.匈牙利算法是基于Hall定理中充分性证明的思想,它是部图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法. -------等等,看得头大?那么请看下面的版本: 通过数代人的努力,你终于赶上了剩男剩女的大潮,假设你是一位光荣的新世纪媒人,在你的手上有N个剩男,M个剩女,每个人都可能对多名异性有好感(-_-||暂时不考虑特殊的性取向),如果一对男女互有好感,那么你就可以把这一对撮合在一起,现在

  • Java AbstractMethodError案例分析详解

    背景 AbstractMethodError异常对于我来说还是比较不常遇见的,最近有幸遇到,并侥幸的解决了,在这里把此种场景剖析一番,进入正题,下面是AbstractMethodError在Java的异常机制中所处的位置: 现在明确了AbstractMethodError所具有的特性: 1.它是Error的子类,Error类及其子类都是被划分在非检查异常之列的,就是说这些异常不能在编译阶段被检查出来,只能在运行时才会触发. 2.通过API文档里面的解释大致得出的结论就是说A依赖于B,但是执行的时

  • 分析详解python多线程与多进程区别

    目录 1 基础知识 1.1 线程 1.2 进程 1.3 两者的区别 2 Python 多进程 2.1 创建多进程 方法1:直接使用Process 方法2:继承Process来自定义进程类,重写run方法 2.2 多进程通信 Queue Pipe 2.3 进程池 3 Python 多线程 3.1 GIL 3.2 创建多线程 方法1:直接使用threading.Thread() 方法2:继承threading.Thread来自定义线程类,重写run方法 3.3 线程合并 3.4 线程同步与互斥锁 3

  • Android WindowManger的层级分析详解

    目录 一. Window 分类 二. Window层级 (1)应用程序窗口: (2)子窗口: (3)系统窗口: (三)如何真正查看 Window 的优先级 (四) 层级高低具体分析(对比Toast以及软键盘) (五)如何定制系统层级 一. Window 分类 应用 Window(ApplicationWindow: 对应一个 Acitivity) 子 Window    (SubWindow:不能单独存在,需要依附在特定的父 Window 中,比如常见的一些 Dialog 就是一个子 Windo

随机推荐