华为机试题： 约瑟夫问题（Java）

描述:	功能: 约瑟夫问题众所周知，原始的约瑟夫问题是这样的：有n个人，编号为1,2,..., n，站成一圈，  每次第m个将会被处决，直到只剩下一个人。约瑟夫通过给出m来决定赦免其中的一个人。  例如当n=6,m=5时，5,4,6,2,3将会被依次处决，而1将会幸免。  假如有k个好人，和k个坏人，所有人站成一圈，前k个人是好人，后k个人是坏人，  编写程序计算一个最小的m，使k个坏人都被处决，而不处决任何好人。        输入: k 为正整数        输出:          返回: 最小的m，使k个坏人都被处决，而不处决任何好人。

package huawei;


public final class Demo {
	
	/*
	功能: 约瑟夫问题众所周知，原始的约瑟夫问题是这样的：有n个人，编号为1,2,..., n，站成一圈，
	每次第m个将会被处决，直到只剩下一个人。约瑟夫通过给出m来决定赦免其中的一个人。
	例如当n=6,m=5时，5,4,6,2,3将会被依次处决，而1将会幸免。

	假如有k个好人，和k个坏人，所有人站成一圈，前k个人是好人，后k个人是坏人，
	编写程序计算一个最小的m，使k个坏人都被处决，而不处决任何好人。

	    
	输入: k 为正整数
	    
	输出: 
	     
	返回: 最小的m，使k个坏人都被处决，而不处决任何好人。
	     
	*/
	

	public static  int getMinimumM(int K)
	{
	    /*在这里实现功能*/

		int m = K, remainPeople = 2 * K;//从K下标开始查找，剩下的人数初始化为2 * K
		int currIndex = 0;//当前应该删除的位置
		int deleteNum = 0; //已经删除的人数
		int start = 1; //从当前位置开始计数
		
		while(true)
		{
			/*从start位置开始数1，数到m，就到currIndex位置,
			       当currIndex为0的时候，为最后一个元素*/
			currIndex = (start + m - 1) % remainPeople;
			
			if(currIndex > K || currIndex == 0)
			{
				/*判断是否删除K个，如果是的话，则m已经找到*/
				deleteNum++;
				if (deleteNum == K)
				{
					return m;
				}
				
				/*删除一个元素，这个元素位于 [K..2K]之间*/
				remainPeople --;
				
				/*判断下一个起点*/
				if(currIndex == 0) start = 1;
				else start = currIndex;	
			}
			else //这个m不符合要求
			{
				start = 1;
				remainPeople = 2 * K;
				deleteNum = 0;
				m++; //判断下一个m
			}
			
		}
	}
}