第 18 题（数组）：
题目：n 个数字（0,1,…,n-1）形成一个圆圈，从数字 0 开始，
每次从这个圆圈中删除第 m 个数字（第一个为当前数字本身，第二个为当前数字的下一个
数字）。当一个数字删除后，从被删除数字的下一个继续删除第 m 个数字。
求出在这个圆圈中剩下的最后一个数字。
思路：看到这道题，直觉是不难，模拟一下过程就好了。我用的是数组来表示的，用first表示当前第一个数字是哪一个数，若删除一个数字则将后面的数字平移到前面。
/*
第 18 题（数组）：
题目：n 个数字（0,1,…,n-1）形成一个圆圈，从数字 0 开始，
每次从这个圆圈中删除第 m 个数字（第一个为当前数字本身，第二个为当前数字的下一个
数字）。当一个数字删除后，从被删除数字的下一个继续删除第 m 个数字。
求出在这个圆圈中剩下的最后一个数字。
start time = 10:38
end time = 11:30
*/ #include <stdio.h>
#include <stdlib.h>
#include <string.h> int findlast(int * n, int len, int m, int first) // n是输入数字的数组 len是输入数字的长度 m是要删除第几个数字 first是第一个数字是第几个数字
{
if(len == )
{
return n[];
}
else
{
int d = (m % len) + first - ;
for(int i = d - ; i < len - ; i++)
{
n[i] = n[i + ];
}
return findlast(n, len - , m, d %(len - ));
}
} int findlastn(int n, int m)
{
int * num = (int *)malloc(sizeof(int) * n);
for(int i = ; i < n; i++)
{
num[i] = i;
}
return findlast(num, n, m, );
} int main()
{ int ans = findlastn(, ); return ;
}
上网找答案，发现这是一个很经典的问题 约瑟夫环。有模拟O(MN)、数学O(N)两种常见方法。
网上的模拟都是用的循环链表：
来源http://www.cnblogs.com/dartagnan/archive/2011/09/16/2179143.html
int LastRemaining_Solution1(unsigned int n, unsigned int m)
{
// invalid input
if(n < || m < )
return -; unsigned int i = ; // initiate a list with n integers (0, 1, ... n - 1)
list<int> integers; for(i = ; i < n; ++ i)
integers.push_back(i); list<int>::iterator curinteger = integers.begin(); while(integers.size() > )
{
// find the mth integer. Note that std::list is not a circle
// so we should handle it manually for(int i = ; i < m; ++ i)
{
curinteger ++; if(curinteger == integers.end())
curinteger = integers.begin();
} // remove the mth integer. Note that std::list is not a circle
// so we should handle it manually list<int>::iterator nextinteger = ++ curinteger; if(nextinteger == integers.end())
nextinteger = integers.begin();
-- curinteger;
integers.erase(curinteger);
curinteger = nextinteger;
} return *(curinteger); }
数学方法很有启发性，从后向前推倒。把最后剩下的数字依次回推到最开始的值
过程http://www.360doc.com/content/12/0314/13/1429048_194255548.shtml
代码：http://www.cnblogs.com/dartagnan/archive/2011/09/16/2179143.html
int LastRemaining_Solution2(int n, unsigned int m)
{
// invalid input
if(n <= || m < )
return -; // if there are only one integer in the circle initially,
// of course the last remaining one is 0
int lastinteger = ; // find the last remaining one in the circle with n integers
for (int i = ; i <= n; i ++)
lastinteger = (lastinteger + m) % i; return lastinteger;
}
