圆圈中最后剩下的数字(递推公式) 代码(C++)

?

?

题目: 0,1...,n-1这n个数字排成一个圆圈, 从数字0开始每次从这个圆圈里删除第m个数字.

求出这个圆圈里最后剩下的数字.

?

可以推导出约瑟夫环的递推公式, 使用循环进行求解, 时间复杂度O(n), 空间复杂度O(1).

?

代码:

?

/*
 * main.cpp
 *
 *  Created on: 2014.7.12
 *      Author: spike
 */

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; int LastRemaining(size_t n, size_t m) { if (n<1 || m<1) return -1; int last = 0; for (size_t i=2; i<=n; ++i) { last = (last+m)%i; } return last; } int main(void) { int result = LastRemaining(5, 3); printf(result = %d , result); return 0; }
     
    
   
  

?

?

result = 3

?

?

?

?

?

?