1 /*************************************************************************  2     > File Name: 45_LastNumberInCircle.cpp  3     > Author: Juntaran  4     > Mail: JuntaranMail@gmail.com  5     > Created Time: 2016年09月04日 星期日 20时21分57秒  6  ************************************************************************/  7    8 #include <stdio.h>  9 #include <bits/stdc++.h> 10  11 using namespace std; 12  13  14 // 环形链表 15 int LastRemaining1(int n, int m) 16 { 17     if (n<1 || m<1) 18         return -1; 19      20     int i = 0; 21      22     list<int> numbers; 23     for (int i = 0; i < n; ++i) 24         numbers.push_back(i); 25      26     list<int>::iterator current = numbers.begin(); 27     while (numbers.size() > 1) 28     { 29         for (int i = 1; i < m; ++i) 30         { 31             current ++; 32             if (current == numbers.end()) 33                 current = numbers.begin(); 34         } 35         list<int>::iterator next = ++current; 36         if (next == numbers.end()) 37             next = numbers.begin(); 38          39         --current; 40         numbers.erase(current); 41         current = next; 42     } 43     return *current; 44 } 45  46 // 数组模拟环 47 int LastRemaining2(int n, int m) 48 { 49     if (n<1 || m<1) 50         return -1; 51      52     int array[n]; 53     int i = -1; 54     int step = 0; 55     int count = n; 56      57     while (count > 0) 58     { 59         i ++; 60         if (i >= n)            // 模拟环 61             i = 0; 62         if (array[i] == -1) 63             continue; 64         step ++; 65         if (step == m) 66         { 67             array[i] = -1; 68             step = 0; 69             count --; 70         } 71     } 72     int ret = i; 73     return ret; 74 } 75  76 // 数学解法 77 int LastRemaining3(int n, int m) 78 { 79     if (n<1 || m<1) 80         return -1; 81      82     int ret = 0; 83     for (int i = 2; i <= n; ++i) 84         ret = (ret + m) % i; 85      86     return ret; 87 } 88  89 int main() 90 { 91     int n = 100; 92     int m = 5; 93      94     int ret1 = LastRemaining1(n, m); 95     int ret2 = LastRemaining2(n, m); 96     int ret3 = LastRemaining3(n, m); 97      98     printf("ret1 is %d\n", ret1); 99     printf("ret2 is %d\n", ret2);100     printf("ret3 is %d\n", ret3);101     102     return 0;103 }