分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程https://www.captainai.net/troubleshooter
// 面试题62：圆圈中最后剩下的数字 // 题目：0, 1, …, n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里 // 删除第m个数字。求出这个圆圈里剩下的最后一个数字。 #include <cstdio> #include <list> using namespace std; // ====================方法1==================== int LastRemaining_Solution1(unsigned int n, unsigned int m) { if (n < 1 || m < 1) return -1; unsigned int i = 0; list<int> numbers; for (i = 0; i < n; ++i) numbers.push_back(i); list<int>::iterator current = numbers.begin(); while (numbers.size() > 1) { for (int i = 1; i < m; ++i) { current++; if (current == numbers.end()) current = numbers.begin(); } list<int>::iterator next = ++current; if (next == numbers.end()) next = numbers.begin(); --current; numbers.erase(current); current = next; } return *(current); } // ====================方法2==================== int LastRemaining_Solution2(unsigned int n, unsigned int m) { if (n < 1 || m < 1) return -1; int last = 0; for (int i = 2; i <= n; i++) last = (last + m) % i; return last; } // ====================测试代码==================== void Test(const char *testName, unsigned int n, unsigned int m, int expected) { if (testName != nullptr) printf("%s begins: \n", testName); if (LastRemaining_Solution1(n, m) == expected) printf("Solution1 passed.\n"); else printf("Solution1 failed.\n"); if (LastRemaining_Solution2(n, m) == expected) printf("Solution2 passed.\n"); else printf("Solution2 failed.\n"); printf("\n"); } void Test1() { Test("Test1", 5, 3, 3); } void Test2() { Test("Test2", 5, 2, 2); } void Test3() { Test("Test3", 6, 7, 4); } void Test4() { Test("Test4", 6, 6, 3); } void Test5() { Test("Test5", 0, 0, -1); } void Test6() { Test("Test6", 4000, 997, 1027); } int main(int argc, char *argv[]) { Test1(); Test2(); Test3(); Test4(); Test5(); Test6(); return 0; } // ------ Output ------ /* Test1 begins: Solution1 passed. Solution2 passed. Test2 begins: Solution1 passed. Solution2 passed. Test3 begins: Solution1 passed. Solution2 passed. Test4 begins: Solution1 passed. Solution2 passed. Test5 begins: Solution1 passed. Solution2 passed. Test6 begins: Solution1 passed. Solution2 passed. */
