/*
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;
}