josephus 问题的算法（转载）

Josephus 问题：

一群小孩围成一个圈，任意假定一个数 m，从第一个小孩起，顺时针方向数，每数到第 m 个小孩时，该小孩便离开。小孩不断离开，圈子不断缩小，最后剩下的一个小孩便是胜利者。究竟胜利的是第几个小孩呢？

案例分析：

解答这个问题，首先要定义一个数组，其元素个数就是小孩个数。必须预先设置一个小孩个数常量，以便定义一个数组。

对每个小孩赋以一个序号作为小孩的标志。由于数组是局部作用域的，一旦分配之后，就删不去，得等到作用域结束才会自动抹去，所以当小孩离开时，只能修改该数组元素值来表示小孩的离开。

数组是线性排列的，小孩是围成圈的，用数组表示小孩围成的圈，要有一种从数组尾部跳到数组头部的技巧，这就是“加1取模”。当数到数组尾的时候，下一个数组下标值可以算得为0，从而回到数组首以继续整个过程。程序如下：

#include "stdafx.h"

#include<iostream>

#include<iomanip>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

    //建立小孩数组

    const int num = ;        //小孩个数

    int interval;            //每次数 interval 个小孩，便让该小孩离开

    int a[num];                //小孩数组

    //给小孩编号

    for(int i=; i<num; i++)    //小孩的编号只与小孩的个数有关

        a[i]=i+;

    //输入小孩间隔 interval

    cout<<"please input the interval:";

    cin>>interval;

    //将全体参加的小孩输入

    for(int i=; i<num; i++)    //顺序输出开始时的小孩编号

        cout<<a[i]<<",";

    cout<<endl;

    int k=;                //表示处理第 k 个离开的小孩

    int i=-;                //数组下标（下一个值 0 就是第一个小孩的下标）

    //处理获胜前的小孩

    while(true)

    {

        //在圈中数 interval 个小孩

        for(int j=; j<interval; )

        {

            i=(i+) % num;    //对下标加 1 取模（使得最后和一个小孩的下一个是第一个小孩）

            if(a[i] != )        //如果该小孩在圈中，则承认该数有效

                j++;

        }

        if(k == num)

            break;            //该小孩是最后的胜利者

        cout<<a[i]<<",";    //输出离开的小孩编号

        a[i] = ;                //表示该小孩已经离开

        k++;                //准备处理下一个圈中的小孩

    }

    //break 语句跳转到此

    cout<<endl<<"No."<<a[i]<<"boy's won."<<endl;

    return ();

}

原文地址：《Visual C++ 编程从基础到应用》第四章末尾案例

巴特西

josephus 问题的算法（转载）

最新文章

热门文章