算法 - n个数字形成的圆圈中循环删除第m个数字（C++）

//****************************************************************************************************
//
//  n个数字形成的圆圈中循环删除第m个数字 - C++ - by Chimomo
//
//  题目： n个数字（0, 1 , … , n-1）形成一个圆圈。从数字0开始，每次从这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。
//  当一个数字删除后，从被删除数字的下一个继续删除第m个数字。求出在这个圆圈中剩下的最后一个数字。
//
//  Answer:
//  The keys are:
//      1) If we shift the ids by k, namely, start from k instead of 0, we should add the result by k%n.
//      2) After the first round, we start from (k+1)(possibly % n) with n-1 elements, that is equal to an (n-1) problem while start from (k+1)th element instead of 0, so the answer is (f(n-1,m)+(k+1))%n.
//      3) Set k = m-1, so f(n,m) = (f(n-1,m)+m)%n.
//      Obviously, f(1,m) = 0. Now this is an O(n) solution.
//
//****************************************************************************************************

#include <iostream>
#include <stdio.h>

using namespace std;

int f(int n, int m)
{
	int fn = 0;

	for(int i = 2; i <= n; i++)
	{
		fn = (fn + m) % i;
	}

	return fn;
} 

int main(int argc, char* argv[])
{
	cout << f(100, 66) << endl;

	return 0;
}

// Output:
/*
77
*/

算法 - n个数字形成的圆圈中循环删除第m个数字（C++）,布布扣,bubuko.com

算法 - n个数字形成的圆圈中循环删除第m个数字（C++）

原文：http://blog.csdn.net/troubleshooter/article/details/23863783