首页 > 其他 > 详细

递推解决约瑟夫环问题

时间:2021-04-12 22:20:07      阅读:27      评论:0      收藏:0      [点我收藏+]

题目:
https://leetcode-cn.com/problems/find-the-winner-of-the-circular-game/
定义状态函数f(n,k) 为编号从0开始n个人在第k次淘汰情况下的幸存者

很显然第一次淘汰编号k-1的人,下一次从编号k开始
而f(n-1,k)根据定义是在编号0开始,我们只需要对坐标进行映射即可
于是有递推公式
f(n,k)=(f(n-1,k)+k)%n

代码:

class Solution {
public:
    int fun(int n,int k){
        if(n==1) return 0;
        return (fun(n-1,k)+k)%n;   
    }
    int findTheWinner(int n, int k) {
        return fun(n,k)+1;//定义编号从0开始 题目是从1开始
    }
};

递推解决约瑟夫环问题

原文:https://www.cnblogs.com/OfflineBoy/p/14649736.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!