
题目链接:
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 ;
}