7.cpp

来自「一道ACM的题」· C++ 代码 · 共 69 行

#include <stdio.h>
#include <stdlib.h>


/*
 * 这道题目跟经典的约瑟夫题目很像,也可以在中间操作部分用传统的约瑟夫模拟操作来进行,不过那样在里面会有太多的循环,不能通过系
 * 的时间要求,所以在主操作方面可以用数学的取余来模拟约瑟夫操作
 */

int main()
{
	bool f( int n, int m );

	int n;
	scanf( "%d", &n );

	while ( n != 0 )
	{
		if ( n == 1 )
			printf( "%d\n", 2 );
		else
		{
		for ( int i = n + 1; ; )
		{
			int temp = i % ( n * 2 );
			if ( temp > n || temp == 0  )		// temp 为第一次操作时到达的地方,一定要是在中间一人后面才可以
			{
				if ( f( n * 2, i ) )		// 调用最主要的判断函数,看目前这个数是否符合要求
				{
					printf( "%d\n", i );
					break;
				}
				i++;
			}
			else
				i += n	
		}
		}
		scanf( "%d", &n );
	}

	return 0;
}
				

// 模拟约瑟夫问题,因为不
bool f( int n, int m )
{
	int sum = 0;		// 表示现在成功多少次
	int now = n;		// 表示现在还有多少人
	int a, b = 0;		// a 表示目前的位置, b 表示 a 目前的位置离最后一位还有多少

	for ( ; ; )
	{
		a = ( m - b ) % now;	// 把 a 移到最后一位,这样就可以用取余直接算出这次最后到达的位置
		if ( a == 0 )			// 这句话关键,当 a == 0 时说明现在的位置是在最后一位,符合要求
			a = now;
		if ( a <= n / 2 )
			return false;
		sum++;
		if ( sum == n / 2 )		
			return true;

		b = now - a;			// 得到 a 离最后一个的距离
		now--;
	}
}