/*
  Name: 约瑟夫环问题算法集锦
  Copyright: 始发于goal00001111的专栏；允许自由转载，但必须注明作者和出处
  Author: goal00001111搜集整理
  Date: 03-12-08 18:14
  Description:
有编号从1到N的N个人坐成一圈报数，报到M的人出局，下一位再从1开始， 如此持续，
直止剩下一位为止，报告此人的编号X。
输入N,M，求出X。
共搜集整理了7类10种算法，对于初学者和算法爱好者来说——看了绝对值！
*/
#include<iostream>
#include <time.h>

using namespace std;

int Fun_1(int n, int m);
int Fun_2(int n, int m);
int Fun_3(int n, int m);
int Fun_4(int n, int m);
int Fun_5(int n, int m);
int Fun_6(int n, int m);
int Fun_7(int n, int m);
int Fun_8(int n, int m);
int Fun_9(int n, int m);
int Fun_10(int n, int m);

int main(int argc, char* argv[])
{
    int n, m;
    //cout << "Input max, step: ";
//    cin >> n >> m;
    time_t startTime;
    time_t endTime;
    
    time(&startTime);
    for (int i=10; i<11; i++)
       cout << Fun_1(i, 8);
    time(&endTime);
    cout << "No.1 time = " << difftime(endTime, startTime) << endl;
    
    time(&startTime);
    for (int i=10; i<11; i++)
       cout << Fun_2(i, 8);
    time(&endTime);
    cout << "No.2 time = " << difftime(endTime, startTime) << endl;
    
    time(&startTime);
    for (int i=10; i<11; i++)
       cout << Fun_3(i, 8);
    time(&endTime);
    cout << "No.3 time = " << difftime(endTime, startTime) << endl;
    
    time(&startTime);
    for (int i=10; i<11; i++)
       cout << Fun_4(i, 8);
    time(&endTime);
    cout << "No.4 time = " << difftime(endTime, startTime) << endl;
    
    time(&startTime);
    for (int i=10; i<11; i++)
       cout << Fun_5(i, 8);
    time(&endTime);
    cout << "No.5 time = " << difftime(endTime, startTime) << endl;
    
    time(&startTime);
    for (int i=10; i<11; i++)
       cout << Fun_6(i, 8);
    time(&endTime);
    cout << "No.6 time = " << difftime(endTime, startTime) << endl;
    
    time(&startTime);
    for (int i=10; i<11; i++)
       cout << Fun_7(i, 8);
    time(&endTime);
    cout << "No.7 time = " << difftime(endTime, startTime) << endl;
    
    time(&startTime);
    for (int i=10; i<11; i++)
       cout << Fun_8(i, 8);
    time(&endTime);
    cout << "No.8 time = " << difftime(endTime, startTime) << endl;
    
    time(&startTime);
    for (int i=10; i<11; i++)
       cout << Fun_9(i, 8);
    time(&endTime);
    cout << "No.9 time = " << difftime(endTime, startTime) << endl;
    
    time(&startTime);
    for (int i=10; i<11; i++)
       cout << Fun_10(i, 8);
    time(&endTime);
    cout << "No.10 time = " << difftime(endTime, startTime) << endl;
    
    system("pause");
    return 0;
}

//采用了设置个人编号和计数器方法，屏蔽已经出圈人的位置
int Fun_1(int n, int m)
{
    int *a = new int[n]; //设置一个数组用来存储n个人的编号
    
    for (int i=0; i<n; i++) //注意C语言中的数组下标从0开始
    {
        a[i] = i + 1;
    }
    int s = 1; //累计出圈的人数，设初值为1，那最后一个就不用出圈了
    int count = 0; //计数器，数到m就归零
    
    while(s < n)
    {
        for (int i=0; i<n; i++)//只要还有超过1个人在圈里，就不断的遍历数组
        {
            if (a[i] == 0) //编号为0，表示此人已经出圈
                continue;
            count++;    //报一次数
            if (count == m) //报数为m的那个人出圈
            {
                a[i] = 0; //设此位置编号为0，表示此人已经出圈
                ++s; //出圈人增加一个
                count = 0; //计数器归零
            }
        }
    }
    int pos;
    for (int i=0; i<n; i++) //遍历数组，看看还有谁没有出圈，找的就是他
    {
        if (a[i] != 0)
        {
            pos = a[i];
            break;
        }
    }
    delete []a;
    return pos;
}

//采用了计数器方法，也使用了数组，但数组中存储的不是个人的编号，而是是否出圈的信息
int Fun_2(int n, int m)
{
    int *a = new int[n]; //设置一个数组用来存储n个人是否出圈，1表示在圈内，0表示在圈外
    
    for (int i=0; i<n; i++) //首先设置所有人都在圈内
    {
        a[i] = 1;
    }
    int s = 1; //累计出圈的人数，设初值为1，那最后一个就不用出圈了
    int count = 0; //计数器，数到m就归零
    
    while(s < n)
    {
        for (int i=0; i<n; i++)//只要还有超过1个人在圈里，就不断的遍历数组
        {
            count += a[i]; //若a[i]=0，就直接跳过了
            if (count == m) //报数为m的那个人出圈
            {
                a[i] = 0; //设此位置编号为0，表示此人已经出圈
                ++s; //出圈人增加一个
                count = 0; //计数器归零
            }
        }
    }
    int pos;
    for (int i=0; i<n; i++) //遍历数组，看看还有谁没有出圈，找的就是他
    {
        if (a[i] == 1)
        {
            pos = i + 1;
            break;
        }
    }
    delete []a;
    return pos;
}

//采用了数组队列的方法，每出圈一个人，就从队列中删除
int Fun_3(int n, int m)
{
    int *a = new int[n]; //设置一个数组用来存储n个人的编号
    
    for (int i=0; i<n; i++) //注意C语言中的数组下标从0开始
    {
        a[i] = i + 1;
    }
    int front=0, rear=n-1;  //对头front指向第一个元素，队尾rear指向最后一个元素
    int count = 0; //计数器，数到m就归零
    
    while ((front) != (rear))//当队列元素还有一个，注意这里不需要队列为空，而是留一个元素
    {
        count++;    //报一次数
        if (count == m) //报数为m的那个人出圈
        {
            front = ++front % n; //将该元素从队列中删除
            count = 0; //计数器归零
        }  
        else //否则把对头的元素放到队尾去
        {
            rear = ++rear % n;//队尾前移，以存储从对头转来的元素
            a[rear] = a[front];
            front = ++front % n; //对头前移，指向新的元素
        }            
    }
    delete []a;
    return a[front];  
}

//很巧妙的方法，不用屏蔽位置, 需要计数器，采用数组，但数组中存储的不是本人的编号，而是是下一个人的编号  
int Fun_4(int n, int m)
{
    int *a = new int[n]; //设置一个数组用来存储n个人是否出圈，1表示在圈内，0表示在圈外
    
    for (int i=n-2; i>=0; i--) //存储下一个人的编号
    {
        a[i] = i + 1;
    }
    a[n-1] = 0; //最后一个人的下一位是第一个人
    int s = 0; //累计出圈的人数，设初值为1，那最后一个就不用出圈了
    int count = 0; //计数器
    int pos; //当前位置
    int nextPos = 0;//下一位置
    
    while(s < n)
    {
        pos = nextPos;//获取当前位置
        nextPos = a[pos];//获取当前位置的下一位置
        count++;
        if (count == m)//改变当前位置的下一位置
        {
            count = 0; //计数器归零
            s++; //累计出圈人
            a[pos] = a[nextPos];
        }   
    }
    
    delete []a;
    
    if (nextPos != 0)
        return nextPos;
    else
        return n;
}

//很巧妙的方法，Fun_4()的一个改进
int Fun_5(int n, int m)
{
   int *a = new int[n]; //设置一个数组用来存储n个人是否出圈，1表示在圈内，0表示在圈外
    
    for (int i=n-2; i>=0; i--) //存储下一个人的编号
    {
        a[i] = i + 1;
    }
    a[n-1] = 0; //最后一个人的下一位是第一个人
    int pos = n - 1; //当前位置
    
    do
    {
        for (int i=0; i<m-1; i++)
            pos = a[pos];  
        a[pos] = a[a[pos]];
    } while (pos != a[pos]);
    
    delete []a;
    
    return pos + 1;
}

//很巧妙的方法，直接确定出列的人，并不断改变数组的长度
int Fun_6(int n, int m)
{
    int *a = new int[n]; //设置一个数组用来存储n个人的编号
    
    for (int i=0; i<n; i++) //注意C语言中的数组下标从0开始
    {
        a[i] = i + 1;
    }
    
    int pos = (m - 1) % n;//这是第一个要出列的人的下标
    
    while (n > 1) // 当队列中还有不止一个人的时候，要就进行出列的动作
    {
        for (int i=pos; i<n-1; i++) //这个家伙走了以后，后面的人应该依次顶上来
        {
            a[i] = a[i+1];
        }
        n--;    // 并且整个队列的人少了一个，也就是长度要减掉一
        pos = (pos + m - 1) % n; //这是下一个要出列的人
    }
    pos = a[0];
    delete []a;
    return pos;
}

//采用循环链表结构，来进行删除操作
int Fun_7(int n, int m)
{
    struct node
    {
        int data;
        struct node *next;
    };
    struct node * head, *s, *temp;
    head = new struct node;//存储第一个人的序号信息
    head->data = 1;
    temp = head->next = head;
    for (int i=2; i<=n; i++)//存储所有人的序号信息
    {
        s = new struct node;
        s->data = i;
        s->next = head;
        temp->next = s;
        temp = s;
    }
    s = head;
    while (s->next != s)
    {
        for (int i=1; i<m; i++)//先数m-1个数
        {
            temp = s;
            s = s->next;
        }
        //把数到m的人从链表中删除
        temp->next = s->next;
        delete s;
        s = temp->next;
    }
    int pos = s->data; //最后一个人
    delete s;
    return pos;
}

/*
数学方法:
令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然
是f[n],因为实际生活中编号总是从1开始，我们输出f[n]+1
递推公式
f[1]=0;
f=(f[i-1]+m)%i;   (i>1)
*/
// 递归算法
int F(int n, int m)
{
    if (n == 1)
      return 0;   
    return (F(n-1, m) + m) % n;
}
int Fun_8(int n, int m)
{     
    return F(n, m) + 1;
}

//非递归算法
int Fun_9(int n, int m)
{
    int r = 0;
    for (int i = 2; i <= n; i++)
        r = (r + m) % i;
    return r + 1;
}

int Fun_10(int n, int m)
{
    int p, i = 1;
    while( i < n )
    {
        p = i * m;
        while (p > n)
            p = p - n + (p - n - 1)/(m - 1);
        i++;
    }
    p = n * m;
    while (p > n)
        p = p - n + (p - n - 1)/(m - 1);
        
    return p;
}

评论