编程算法 - 圆圈中最后剩下的数字(递推公式) 代码(C++)
浏览数：26 /
时间：2015年06月08日
圆圈中最后剩下的数字(递推公式) 代码(C++)
本文地址: 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
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
