NYOJ 191 POJ 1012 Joseph(约瑟夫环问题)

2024-08-27 02:58

本文主要是介绍NYOJ 191 POJ 1012 Joseph(约瑟夫环问题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

链接:click here~~

题意:假设有2k个人围着一个圆桌坐着,前k个是好人,后k个是坏人 。现在开始,每m个人踢掉一个,比如有6个人,m=5,那么,被踢掉的人依次是5,4,6,2,3,1。现在要求,在踢掉第一个好人前,必需把所有的坏人踢掉,问,给定一个k,求满足这个要求的最小的m,现在希望你写一个程序,快速的帮助小珂,计算出来这个m。

思路:我们来回想一下最基本的约瑟夫环问题, n个人(编号0~(n-1)),从0开始报数,报到(m-1)的退出,剩下的人继续从0开始报数。求最后余下的人编号,我们知道第一个人(编号一定是m%n-1) 出列之后,剩下的n-1个人组成了一个新的约瑟夫环(以编号为k=m%n的人开始):  k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2  并且从k开始报0,如果做一下转换:  k --> 0  k+1 --> 1  k+2 --> 2  ...  ...  k-2 --> n-2  k-1 --> n-1  变换后就完完全全成为了(n-1)个人报数的子问题,假如我们知道这个子问题的解:例如x是最终剩下的人,那么根据上面这个表把这个x带回去就是n个人情况的解,变回去的公式很简单,x'=(x+k)%n  如何知道(n-1)个人报数的问题--只要知道(n-2)个人的解,(n-2)个人的解--求(n-3)的情况 ---- 递推公式:  f[i]表示i个人玩游戏报m退出最后胜利者的编号,最后的结果自然是f[n] 。

递推公式  f[1]=0;  f[i]=(f[i-1]+m)%i; (i>1) 

思路分析参考:http://www.cnblogs.com/yu-chao/archive/2011/05/29/2062276.html

代码:

#include <math.h>
#include <queue>
#include <deque>
#include <vector>
#include <stack>
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>using namespace std;
#define Max(a,b) a>b?a:b
#define Min(a,b) a>b?b:a
#define mem(a,b) memset(a,b,sizeof(a))
int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};
const double eps = 1e-6;
const double Pi = acos(-1.0);
static const int inf= ~0U>>2;
static const int maxn = 502;
int k;
int f[] = {2, 7, 5, 30, 169, 441, 1872, 7632, 1740, 93313, 459901, 1358657, 2504881,13482720};
//bool check(int num)
//{
//    for(int i = 1; i <= k; i++)
//    {
//        int pos = i;
//        for(int j = k+1; j <= 2*k; j++)
//        {
//            pos = (pos+num)%j;
//            if(pos == 0) pos = j;
//        }
//        if(pos > k) return 0;
//    }
//    return 1;
//}
int main()
{while(~scanf("%d", &k)&& k){cout << f[k-1] << endl;}return 0;
}      
When you want to give up, think of why you persist until now!

这篇关于NYOJ 191 POJ 1012 Joseph(约瑟夫环问题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1110443

相关文章

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D