本文地址: http://blog.csdn.net/caroline_wendy
题目: 0,1...,n-1这n个数字排成一个圆圈, 从数字0開始每次从这个圆圈里删除第m个数字.
求出这个圆圈里最后剩下的数字.
能够推导出约瑟夫环的递推公式, 使用循环进行求解, 时间复杂度O(n), 空间复杂度O(1).
代码:
/* * main.cpp * * Created on: 2014.7.12 * Author: spike */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> 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\n", result); return 0; }
result = 3
编程算法 - 圆圈中最后剩下的数字(递推公式) 代码(C++),布布扣,bubuko.com
编程算法 - 圆圈中最后剩下的数字(递推公式) 代码(C++)
原文:http://www.cnblogs.com/hrhguanli/p/3856238.html