Question

1、新约瑟夫问题【问题描述】(newnumber.pas/c/cpp)将1～M这M个自然数按由小到大的顺序沿顺时针围成一

Answer 1

/// 运行是可以从键盘输入,也可以重定向到文件：newnumber.exe < newnumber.in > newnumber.out

#include

#include

#include

using namespace std;

/// 链表的循环移动

/**

@param[in] lst std::list链表

@param[in,out] it 链表的迭代子

@param[in] step 移动步数.正数代表向后移动,负数代表向前移动

*/

template < class T ,class IT >

void round_move( list< T > &lst,IT &it,int step )

{

if ( step > 0 )

for( int i = 0; i < step; i++ )

{

it++; if ( it == lst.end() ) it = lst.begin();

}

else

for( int i = 0; i > step; i-- )

{

if ( it == lst.begin() ) it = lst.end(); it--;

}

}

/// 新约瑟夫问题,result是结果

void newnumber( vector< int > &result,const int M,const int S,const int N,const int K )

{

list< int > lst;

for( int i = 1; i ::iterator it = lst.begin();

round_move( lst,it,S - 2 );

for( int i = 0; i < M; i++ )

{

list< int >::iterator found_it;

if ( i % 2 == 0 )

{

round_move( lst,it,N );

found_it = it;

round_move( lst,it,1 );

}

else

{

round_move( lst,it,-K );

found_it = it;

round_move( lst,it,-1 );

}

result.push_back( *found_it );

lst.erase( found_it );

}

}

void main()

{

int M,S,N,K;

cin >> M >> S >> N >> K;

vector< int > result;

newnumber( result,M,S,N,K );

for( size_t i = 0; i < result.size(); i++ )

cout