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