/*
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;
}
责任编辑:小草