POJ 2359 Questions(约瑟夫环——数学解法)

时间:2023-03-08 22:20:41
POJ 2359 Questions(约瑟夫环——数学解法)

题目链接:

http://poj.org/problem?id=2359

题意描述:

输入一个字符串

按照下面的规则,如果剩下的最后一个字符是‘?’,输出“Yes”,如果剩下的最后一个字符是' '(空格),输出“No”,其他字符均输出“No comments”

规则:

将该字符串首尾相接,从第一个字符数,数到1999(如果数到结尾则从头开始数,构成约瑟夫环)时,将该字符删除,从删除字符的下一个开始从头数,

知道删除剩余最后一个字符。

解题思路:

刚开始读完题的时候,并没有想到是约瑟夫问题(事后恍然大悟)。约瑟夫问题,有两种解法,分别是模拟解法和数学解法。

  模拟的话,直接模拟报数过程,使用数组,链表均可。

  不过这里介绍一下更高效的数学解法,先上代码:

   int p=;
for(i=;i<=l;i++)
p=(p+)%i;

  由于我们只需要知道最后一个字符的位置,没必要模拟过程,所以我们通过一定的数学计算计算出要求的结果即可。

  具体讲解请参考博客:http://blog.csdn.net/allenhappy/article/details/26713241(原谅我的偷懒,他讲的相对还是很清楚的)

AC代码:

 #include<stdio.h>
#include<string.h>
#include<math.h>
#include<ctype.h>
#include<algorithm>
using namespace std;
const int inf=; char a[],b[];
int main()
{
int i,l;
b[]='\0';
while(gets(a) != NULL)
strcat(b,a);
l=strlen(b);
int p=;
for(i=;i<=l;i++)
p=(p+)%i; if(b[p]=='?')
printf("Yes\n");
else if(b[p]==' ')
printf("No\n");
else
printf("No comments\n");
return ;
}