(线性数据结构5.4.1)UVA 130 Roman Roulette(标准约瑟夫环问题+替换者)

 
/* 
 * UVA_130_1.cpp 
 * 
 *  Created on: 2013年10月31日 
 *      Author: Administrator 
 */  
  
#include <iostream>  
#include <cstdio>  
#include <vector>  
  
using namespace std;  
  
/** 
 * 模拟的实现使用动态数组是非常方便的，过程也很简单。数组初始存储每一个人的编号， 
 * 从第0个元素（1号）开始计数，每次杀死一个人前先不要将这个人的编号删除，而是先找出要来埋他的人， 
 * 将他们的编号互换，然后将埋他的人原来所在的位置删掉即可。最后计算出的是从1号开始计数，最后能幸存的人编号p， 
 * 那么从你前面第p个人开始你就是安全的（你站在第1位），即n - p。这个换算的原理是显而易见的。 
 */  
int main(){  
    int n,k;  
    while(scanf("%d%d",&n,&k)!=EOF,n||k){  
        int i;  
        vector<int> circle;  
        for(i = 1 ; i <= n ; ++i){  
            circle.push_back(i);  
        }  
  
        int t;  
        int m = (k - 1)%circle.size();//计算第一个被杀死的人的位置  
        while(circle.size() != 1){  
            t = (m - 1 + k)%(circle.size() - 1);//计算替换者的位置  
            t = (t + (t >= m))%circle.size();//判断替换着的位置与被杀者位置之间的关系,若被杀者的位置在替换着的前面,则需要+1  
  
            circle[m] = circle[t];//将替换者一道被杀者的位置上  
  
            circle.erase(circle.begin() + t);//删除替换者原来的位置  
  
            m = (m  - ( t < m ) + k)%circle.size();//计算下一个被杀者的位置,因为最后删掉的其实还是替换者的位置,所以如果替换者的位置在额被杀者的前面的话,那么就要-1  
        }  
  
        printf("%d\n",(n - circle.front() + 1)%n + 1 );  
    }  
  
    return 0;  
}

补充：软件开发 , C++ ,