- 浏览: 72708 次
- 性别:
- 来自: 杭州
最新评论
约瑟夫环 (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; }
发表评论
-
最小c编译器
2011-11-08 14:09 1480最小c编译器(来源 (最好在linux下操作))代码有好几个 ... -
the development of c language(转)
2011-11-08 09:25 1313c语言之父Dennis Ritchie 写的关于c语言开发历 ... -
C语言,你真的弄懂了么?
2011-11-07 12:42 1769程序(来源 ): #include <stdi ... -
pe文件格式实例解析
2011-11-07 10:05 0环境:windows xp 速龙3000+(即x86兼容32位 ... -
小型elf "Hello,World"程序
2011-11-06 23:59 1374参考链接:http://timelessname.com/el ... -
elf文件格式实例解析
2011-11-05 23:00 6357试验环境:archlinux 速龙3000+(即x86兼 ... -
高质量的c源代码
2011-11-03 10:18 1153现在自由软件及开源软件越来越流行,有大量的附带源程序 ... -
fltk 库
2011-09-26 19:47 1839fltk是一个小型、开源、支持OpenGL 、跨平台(win ... -
《Introduction to Computing Systems: From bits and gates to C and beyond》
2011-09-25 23:33 2184很好的一本计算机的入门书,被很多学校采纳作为教材,作者Yale ... -
csapp bufbomb实验
2011-09-16 14:21 4621csapp (《深入理解计算机系统》)一书中有一个关于缓冲区 ... -
the blocks problem(uva 101 or poj 1208)
2011-09-11 20:57 1839题目描述见:uva 101 or poj 1208 ... -
the blocks problem(uva 101 or poj 1208)
2011-09-11 20:56 0题目描述见:uva 101 or poj 1208 ... -
部分排序算法c语言实现
2011-09-02 14:51 1020代码比较粗糙,主要是用于对排序算法的理解,因而忽略了边界和容错 ... -
编译器开发相关资源
2011-08-31 08:40 1213开发编译器相关的一些网络资源: how difficu ... -
zoj 1025 Wooden Sticks
2011-07-23 20:25 969题目见:zoj 1025 先对木棒按照长度进行排序,然后再计 ... -
zoj 1091 Knight Moves
2011-07-23 09:05 848题目见zoj 1091 使用宽度搜索优先来求解, ... -
zoj 1078 palindrom numbers
2011-07-22 19:31 1148题目见zoj 1078 主要是判断一个整数在基数为2 ... -
zoj 1006 do the untwist
2011-07-22 13:24 939题目见zoj 1006 或poj 1317 简单 ... -
zoj 3488 conic section
2011-07-22 12:23 1010题目见zoj 3488 很简单的题目,却没能一次搞定,因 ... -
zoj 1005 jugs
2011-07-22 11:43 843题目内容见zoj1005 由于A,B互素且A的容 ...
相关推荐
zoj 3770 Ranking System.md
【标题】"ZOJ 1002" 是一个在线编程竞赛题目,源自ZOJ(Zhejiang Online Judge),这是一个面向ACM/ICPC(国际大学生程序设计竞赛)的在线评测系统。题目编号1002,通常表示该题是ZOJ平台上的一个问题,可能涉及算法...
【标题】"zoj 源码700题"是指一个包含700多道ZOJ(在线判题系统Zhejiang Online Judge)编程竞赛题目的源代码集合。这个资源对于学习算法、提高编程技能以及准备编程竞赛的学员来说极具价值。 【描述】"包含了zoj...
ZOJ,全称“浙江大学程序在线评测系统”(Zhejiang University Online Judge),是一个提供信息学(算法竞赛)题库及程序评测的网站。以下是关于ZOJ的详细介绍: 一、基本信息 名称:浙江大学程序在线评测系统(ZOJ)...
浙江大学ZOJ(Zhejiang University Online Judge)是一个在线编程练习平台,主要服务于计算机科学和技术的学习者,特别是对算法和编程有浓厚兴趣的学生。这个平台提供了大量的编程题目,涵盖了各种难度和主题,帮助...
Problem Arrangement zoj 3777
【标题】"ZOJ1027解题指南"是一个针对特定编程竞赛题目——ZOJ1027的解决方案集合。ZOJ,全称为“Zhejiang Online Judge”,是浙江大学主办的一个在线编程竞赛平台,提供了丰富的算法题目供参赛者练习和挑战。本解题...
标题中的"ZOJ.gz_ ZOJ_ZOJ 1016_max flow_zoj 1045_zoj.rar" 提到了两个ZOJ(Zhejiang Online Judge)的题目,分别是1016和1045,这两个数字通常代表在线编程竞赛中的题目编号。这些题目通常涉及到算法和数据结构的...
ZOJ(Zhejiang Online Judge)是一个著名的在线编程竞赛平台,主要面向计算机科学与信息技术的学生和爱好者,提供了大量的算法题目供参赛者练习和提交代码。"ZOJ题目答案源码"是一个压缩包文件,其中包含了700多道...
【ZOJ.zip】是一个压缩包,里面包含了与ZOJ(Zhejiang Online Judge)相关的ACM(International Collegiate Programming Contest)题解。ZOJ是一个在线编程竞赛平台,它为参赛者提供了一系列算法题目进行练习,以...
zoj 题库 详细解答 解题代码 该资源主要涵盖了 zoj 题库中的各种编程题目,涵盖了基本算法、数据结构、数学运算等多个方面的知识点。下面是对该资源中出现的知识点的详细解释: 1. 第一次 ACM 总结(7th ACM) 该...
ZOJ,全称为Zhejiang Online Judge,是一个知名的在线编程竞赛平台,主要服务于浙江大学和国内其他高校的学生,提供丰富的算法题目供参赛者练习和比赛。这个压缩包文件名为"ZOJ 700多题源代码",意味着它包含了解决...
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
《ZOJ 4041问题的正确解法与程序分析》 ZOJ(Zhejiang Online Judge)是一个知名的在线编程竞赛平台,其中的题目编号为4041的题目吸引了众多程序员的关注。本篇文章将深入探讨ZOJ 4041的正确解法,并对提供的源代码...
标题“ZOJ1014.zip_zoj code_zoj1004”表明这是一个与ZOJ(ZeroJudge)在线判题系统相关的代码压缩包,其中可能包含了解决ZOJ问题1004的源代码。ZOJ是面向编程爱好者和学生的一个在线编程竞赛平台,它提供了各种算法...
zoj 1003 c语言的,要写这么多描述吗。。
ZOJ1805代码
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
#### #2548 Course Registration System 题目涉及课程注册系统的实现,可能需要设计一个数据结构来存储和管理课程信息。解决策略是使用数组或哈希表来实现高效的课程查找和管理。 #### #2554 Simple Grid 题目...
ZOJ(Zhejiang Online Judge)是一个著名的在线编程竞赛平台,尤其在ACM(国际大学生程序设计竞赛)领域中有着广泛的影响力。这个“ZOJ题解集合-截至2835”显然是一份包含了大量ZOJ题目解决方案的压缩包,其中涵盖了...