ghost79

约瑟夫问题的数组实现

[问题描述]

有N个人，其编号分别为1－N。这N个人按顺序排成一个圈。现在给定一个正整数M，从第一个人开始依次报数，数到M的人出列，然后又从下一个人开始又从1开始依次报数，数到M的人又出列．．．如此循环，直到最后一个人出列为止。 
 
[输入] 

输入只有一行，包括2个整数N，M。之间用一个空格分开。

[输出] 

输出只有一行，包括N个整数。

[示例] 

输入：
8 5

输出：
5 2 8 7 1 4 6 3

[问题解答]

#include <iostream>

using namespace std;

int main( void )
{
    int n, m;
    cin >> n >> m;

    int *p = new int[ n ];
    for( int i = 0; i < n; i++ ) p[ i ] = i + 1;
    
    int outPos = 0;
    for( int totalPerson = n; totalPerson > 0; totalPerson-- )
    {
        outPos = ( outPos +  m - 1 ) % totalPerson ;
        cout << p[ outPos ] << " ";
        
        for( int j = outPos; j < totalPerson; j++ ) p[ j ] = p[ j + 1 ];
    }
    
    delete []p;
    system( "PAUSE" );
    return 0;
}

posted on 2009-04-09 13:18 C家家 阅读(191) 评论(1)  编辑 收藏