POJ 1012 Joseph 约瑟夫问题
http://poj.org/problem?id=1012
早上去图书馆复习苦逼的复习。。。。万恶的数逻。T T我还要自我安慰的说复习完了奖励回来刷水题~
10点多的时候外面校运会大吼撑杆跳的那个。等到解说说要破纪录了,哥哥我果断收拾东西,跑去看,结果即将到的时候说跳过去了记录破了T T哭瞎了。
---------------------------------------------------大家好,我是分割线---------------------------------------------------
暴力的话肯定悲剧。好吧,不会做。搜题解的。(说好的奖励刷水题QAQ)
首先说一下约瑟夫问题:N个人围成一圈,从第一个开始报数,第m个将被杀掉,最后剩下一个,其余人都将被杀掉。
题目大意:
给定一个数k,前面k个人是好人,后面k个人是坏人,要求找到最少的报数号码m,使得在好人被杀之前坏人全部死亡。
设有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不符合题意。
可以打表直接过的。
#include<cstdio>
int ans[29]={0};
int joseph[15];
int main()
{
int k;
while(scanf("%d",&k),k)
{
if(!joseph[k])
{
int n= k<<1;
ans[0]=0;
int m=1;
for(int i=1;i<=k;i++)
{
ans[i]=( ans[i-1]+m-1) %(n-i+1);
if(ans[i] <k)
{
m++;
i=0;
}
}
joseph[k]=m;
}
printf("%d\n",joseph[k]);
}
}
打表。
#include<cstdio>
int joseph[]={0,2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881,1245064};
int main()
{
int k;
while(scanf("%d",&k),k)
{
printf("%d\n",joseph[k]);
}
}
最新文章
- BAT“搅局”B2B市场,CIO们准备好了吗?
- 【集合框架】JDK1.8源码分析之HashMap(一)
- Java操作Sqlite数据库-jdbc连接
- Verilog学习笔记认识提升篇(一)...............时序的基本概念(待补充)
- androidd 程序默认安装位置和数据存储位置(公用和私用)
- NeHe OpenGL教程 第十四课:图形字体
- 【原】创建Hive表,分号分隔符“;”引起的异常
- POJ 3164 Command Network 最小树形图模板
- 谈谈android 布局 的优化
- [深入React] 7.组件生命周期
- MYSQL 退出的三个方式
- 快速构建Windows 8风格应用24-App Bar构建
- 在SOUI中使用网格布局
- 关于Gson定制的分析
- 网页布局之grid
- label与input之间的对应
- c++字符串前几位,后几位的截取
- 在MarkDown中插入数学公式对照表(持续更新)
- 网站部署中遇到的问题-未能加载文件或程序集“System.Data.SQLite”或它的某一个依赖项
- (STM32F4) Real-time Clock