yuesefuhuan.rar_M?n

有编号从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; //计数器归零