- 浏览: 70386 次
- 性别:
- 来自: 杭州
最新评论
约瑟夫环 (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 1420最小c编译器(来源 (最好在linux下操作))代码有好几个 ... -
the development of c language(转)
2011-11-08 09:25 1093c语言之父Dennis Ritchie 写的关于c语言开发历 ... -
C语言,你真的弄懂了么?
2011-11-07 12:42 1722程序(来源 ): #include <stdi ... -
pe文件格式实例解析
2011-11-07 10:05 0环境:windows xp 速龙3000+(即x86兼容32位 ... -
小型elf "Hello,World"程序
2011-11-06 23:59 1320参考链接:http://timelessname.com/el ... -
elf文件格式实例解析
2011-11-05 23:00 6277试验环境:archlinux 速龙3000+(即x86兼 ... -
高质量的c源代码
2011-11-03 10:18 1090现在自由软件及开源软件越来越流行,有大量的附带源程序 ... -
fltk 库
2011-09-26 19:47 1770fltk是一个小型、开源、支持OpenGL 、跨平台(win ... -
《Introduction to Computing Systems: From bits and gates to C and beyond》
2011-09-25 23:33 2115很好的一本计算机的入门书,被很多学校采纳作为教材,作者Yale ... -
csapp bufbomb实验
2011-09-16 14:21 4543csapp (《深入理解计算机系统》)一书中有一个关于缓冲区 ... -
the blocks problem(uva 101 or poj 1208)
2011-09-11 20:57 1801题目描述见: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 988代码比较粗糙,主要是用于对排序算法的理解,因而忽略了边界和容错 ... -
编译器开发相关资源
2011-08-31 08:40 1167开发编译器相关的一些网络资源: how difficu ... -
zoj 1025 Wooden Sticks
2011-07-23 20:25 940题目见:zoj 1025 先对木棒按照长度进行排序,然后再计 ... -
zoj 1091 Knight Moves
2011-07-23 09:05 814题目见zoj 1091 使用宽度搜索优先来求解, ... -
zoj 1078 palindrom numbers
2011-07-22 19:31 1118题目见zoj 1078 主要是判断一个整数在基数为2 ... -
zoj 1006 do the untwist
2011-07-22 13:24 900题目见zoj 1006 或poj 1317 简单 ... -
zoj 3488 conic section
2011-07-22 12:23 965题目见zoj 3488 很简单的题目,却没能一次搞定,因 ... -
zoj 1005 jugs
2011-07-22 11:43 806题目内容见zoj1005 由于A,B互素且A的容 ...
相关推荐
zoj 3770 Ranking System.md
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
Problem Arrangement zoj 3777
ZOJ题目答案源码
一个非常非常非常非常实用的zoj结题代码
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
zoj 1003 c语言的,要写这么多描述吗。。
ZOJ1805代码
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·
zoj1027解题指南和代码,还不错,是学校培训给的。
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复
zoj 题库 详细解答 解题代码 acm
zoj4041正确题解源代码,以及运行程序
大学ACM竞赛,ZOJ 1733 运用递归(优化)的方法。ac的代码。
zoj吐血制作,希望大家喜欢
能AC 通过的c++代码,包括zoj1002,1091,1789