`

zoj 1088 System Overload

 
阅读更多

  约瑟夫环 (josephus problem )问题,有公式 可以直接套用

  我使用暴力破解方法求解(用时3秒多)。

   代码如下:

/* zoj 1088 System Overload */
#include <stdio.h>
#include <string.h>

#define MAXBUILDING 150

int minStepNum(int totalBuilding, int lastNum);

int main(void)
{
  int n;
  /* int minStepTab[MAXBUILDING];
  int i;
  for(i = 3; i < MAXBUILDING; i++)
  minStepTab[i] = minStepNum(i,2);*/
  while(scanf("%d", &n) == 1 && n != 0)
    /*   printf("%d\n", minStepTab[n]);*/
    printf("%d\n",minStepNum(n,2));
   return 0;
 }
int minStepNum(int totalBuilding, int lastNum)
{
  int minStep = 2;
  int count,i,flag;
  int isCutOff[MAXBUILDING];
  int buildings[MAXBUILDING];
  for(i = 0; i < totalBuilding; i++)
    buildings[i] = i+1;

  while(1)
    {
      memset(isCutOff,0,sizeof(isCutOff));
      isCutOff[0] = 1;
      flag = 0;
      for(i = count = 0; count < minStep * (totalBuilding-2);
	  i = (i+1)%totalBuilding)
	if(isCutOff[i] == 0)
	  {
	    count++;
	    if(count % minStep == 0 && buildings[i] == lastNum)
	      {
		flag = 1;
		break;
	      }
	    else if(count % minStep == 0)
	      isCutOff[i] = 1;
	  }
      if(count == minStep*(totalBuilding-2) && !flag)
	for(i = 0; i < totalBuilding; i++)
	  if(isCutOff[i] == 0)
	    return minStep;
      minStep++;
    }
  return 0;
}

 直接套用公式的代码(15ms):

#include <stdio.h>

int Josephus(int n, int m)
{
  if(n == 1)
    return 0;
  else
    return (Josephus(n-1,m)+m)%n;
}
int main(void)
{
  int n;
  int i;
  while(scanf("%d", &n) == 1 && n != 0)
    {
      for(i = 2;; i++)
	if(Josephus(n-1,i) == 0)
	  {
	    printf("%d\n",i);
	    break;
	  }
    }
  return 0;
}
 

起初我使用最原始的暴力破解法(未使用任何优化),结果超时了(可能需要15秒左右,超出了规定的10秒限制)

 产生超时结果对应代码:

/* zoj 1088 System Overload */
#include <stdio.h>
#include <string.h>

#define MAXBUILDING 150

int lastNumber(int totalBuilding, int stepNum);
int minStepNum(int totalBuilding, int lastNum);

int main(void)
{
  int n;
  int minStepTab[MAXBUILDING];
  int i;
  for(i = 3; i < MAXBUILDING; i++)
    minStepTab[i] = minStepNum(i,2);
  while(scanf("%d", &n) == 1 && n != 0)
    printf("%d\n", minStepTab[n]);
    /*    printf("%d\n",minStepNum(n,2));*/
  return 0;
}
int minStepNum(int totalBuilding, int lastNum)
{
  int i;
  for(i = 2; lastNumber(totalBuilding,i) != lastNum; i++) ;
  return i;
}
int lastNumber(int totalBuilding, int stepNum)
{
  int building[MAXBUILDING],isCutOff[MAXBUILDING];
  int i,count;
  memset(isCutOff,0,sizeof(isCutOff));
  for(i = 0; i < totalBuilding; i++)
    building[i] = i+1;
  isCutOff[i=0] = 1;
  /*  count = 0;*/
  for(count = 0;count < stepNum * (totalBuilding-2); i = (i+1)%totalBuilding)
    if(isCutOff[i] == 0)
    {

      count++;
      if(count % stepNum == 0)
	isCutOff[i] = 1;
    }
  for(i = 0; i < totalBuilding; i++)
    if(isCutOff[i] == 0)
      return building[i];
  return 0;
}
	
分享到:
评论

相关推荐

    zoj 3770 Ranking System.md

    zoj 3770 Ranking System.md

    zoj 1002_zoj1002_

    【标题】"ZOJ 1002" 是一个在线编程竞赛题目,源自ZOJ(Zhejiang Online Judge),这是一个面向ACM/ICPC(国际大学生程序设计竞赛)的在线评测系统。题目编号1002,通常表示该题是ZOJ平台上的一个问题,可能涉及算法...

    zoj 源码700题

    【标题】"zoj 源码700题"是指一个包含700多道ZOJ(在线判题系统Zhejiang Online Judge)编程竞赛题目的源代码集合。这个资源对于学习算法、提高编程技能以及准备编程竞赛的学员来说极具价值。 【描述】"包含了zoj...

    ZOJ:浙江大学程序在线评测系统.docx

    ZOJ,全称“浙江大学程序在线评测系统”(Zhejiang University Online Judge),是一个提供信息学(算法竞赛)题库及程序评测的网站。以下是关于ZOJ的详细介绍: 一、基本信息 名称:浙江大学程序在线评测系统(ZOJ)...

    浙江大学ZOJ题目分类

    浙江大学ZOJ(Zhejiang University Online Judge)是一个在线编程练习平台,主要服务于计算机科学和技术的学习者,特别是对算法和编程有浓厚兴趣的学生。这个平台提供了大量的编程题目,涵盖了各种难度和主题,帮助...

    Problem Arrangement zoj 3777

    Problem Arrangement zoj 3777

    zoj1027解题指南

    【标题】"ZOJ1027解题指南"是一个针对特定编程竞赛题目——ZOJ1027的解决方案集合。ZOJ,全称为“Zhejiang Online Judge”,是浙江大学主办的一个在线编程竞赛平台,提供了丰富的算法题目供参赛者练习和挑战。本解题...

    zoj.gz_ ZOJ_ZOJ 1016_max flow_zoj 1045_zoj.rar

    标题中的"ZOJ.gz_ ZOJ_ZOJ 1016_max flow_zoj 1045_zoj.rar" 提到了两个ZOJ(Zhejiang Online Judge)的题目,分别是1016和1045,这两个数字通常代表在线编程竞赛中的题目编号。这些题目通常涉及到算法和数据结构的...

    ZOJ题目答案源码

    ZOJ(Zhejiang Online Judge)是一个著名的在线编程竞赛平台,主要面向计算机科学与信息技术的学生和爱好者,提供了大量的算法题目供参赛者练习和提交代码。"ZOJ题目答案源码"是一个压缩包文件,其中包含了700多道...

    ZOJ.zip_Jugs A_ZOJ NTA_zoj acm_zoj acm 1216_zoj code

    【ZOJ.zip】是一个压缩包,里面包含了与ZOJ(Zhejiang Online Judge)相关的ACM(International Collegiate Programming Contest)题解。ZOJ是一个在线编程竞赛平台,它为参赛者提供了一系列算法题目进行练习,以...

    zoj 题库 详细解答 解题代码

    zoj 题库 详细解答 解题代码 该资源主要涵盖了 zoj 题库中的各种编程题目,涵盖了基本算法、数据结构、数学运算等多个方面的知识点。下面是对该资源中出现的知识点的详细解释: 1. 第一次 ACM 总结(7th ACM) 该...

    zoj 700源代码

    ZOJ,全称为Zhejiang Online Judge,是一个知名的在线编程竞赛平台,主要服务于浙江大学和国内其他高校的学生,提供丰富的算法题目供参赛者练习和比赛。这个压缩包文件名为"ZOJ 700多题源代码",意味着它包含了解决...

    ACM训练必备POJ ZOJ题目分类及解题思路

    学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路

    zoj.rar_zoj_zoj4041

    《ZOJ 4041问题的正确解法与程序分析》 ZOJ(Zhejiang Online Judge)是一个知名的在线编程竞赛平台,其中的题目编号为4041的题目吸引了众多程序员的关注。本篇文章将深入探讨ZOJ 4041的正确解法,并对提供的源代码...

    ZOJ1014.zip_zoj code_zoj1004

    标题“ZOJ1014.zip_zoj code_zoj1004”表明这是一个与ZOJ(ZeroJudge)在线判题系统相关的代码压缩包,其中可能包含了解决ZOJ问题1004的源代码。ZOJ是面向编程爱好者和学生的一个在线编程竞赛平台,它提供了各种算法...

    zoj 1003c 语言的

    zoj 1003 c语言的,要写这么多描述吗。。

    ZOJ1805代码

    ZOJ1805代码

    zoj1951的AC代码

    本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够

    zoj题目简单归类zoj题目简单归类

    #### #2548 Course Registration System 题目涉及课程注册系统的实现,可能需要设计一个数据结构来存储和管理课程信息。解决策略是使用数组或哈希表来实现高效的课程查找和管理。 #### #2554 Simple Grid 题目...

    ZOJ题解集合-截至2835

    ZOJ(Zhejiang Online Judge)是一个著名的在线编程竞赛平台,尤其在ACM(国际大学生程序设计竞赛)领域中有着广泛的影响力。这个“ZOJ题解集合-截至2835”显然是一份包含了大量ZOJ题目解决方案的压缩包,其中涵盖了...

Global site tag (gtag.js) - Google Analytics