约瑟夫环

怼烎@ 2022-07-15 13:39 198阅读 0赞

# 约瑟夫环 #

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后\[1\] 结果+1即为原问题的解。

# 一般的解决方法 #

直观上，通过循环链表非常的简单，只需要循环删除指定节点就可以了，但建循环链表的过程非常的繁琐，有没有更简单的方法。

# 动态规划的解决法案 #

动态规划从以下四个方面考虑问题：

*  状态(State)
 *  状态间的转移方程(Function)
 *  状态的初始化(Initialization)
 *  返回结果(Answer)

## 状态定义 ##

f(i)表示第i个人报数为m出列人的编号  
f(i+1) 表示第i+1个人报数为m出列人的编号

## 状态间的转移方程 ##

由约瑟夫问题可得到的递推方程为：f(i+1) = f(i) + m  
假设有n个人，则编号范围为0~n-1的环，因此退出的人的编号只能在0~n-1之间，那么 f(i+1) = (f(i) + m) % n

## 状态的初始化 ##

当约瑟夫问题只有一个人时，则f(1) = 0，即表示第 1 个报数为m的编号为0

## 返回结果 ##

表示第n个报数为m的人的编号：f(n)

# 代码 #

#include<iostream>  
    using namespace std;  
    int main()  
    {  
        int N;//人的总个数  
        int M;//间隔多少个人  
    
        cin>>N;  
        cin>>M;  
        int result=0;//N=1情况  
        for (int i=2; i<=N; i++)  
        {  
            result=(result+M)%i;  
        }  
        cout<<"最后退出的人是："<<result + 1<<endl;  // 编号从1开始
        return 0;  
    }

# 参考 #

[约瑟夫环问题][Link 1]

[Link 1]: http://blog.csdn.net/kangroger/article/details/39254619

发表评论取消回复

表情：

评论列表（有 0 条评论，198人围观）

还没有评论，来说两句吧...

相关阅读

相关约瑟夫环

约瑟夫环 1、参考资料 https://blog.csdn.net/shuaicihai/article/details/54847433 2、使用数组

痛定思痛。/ 2022年11月27日 06:54/ 0 赞/ 184 阅读

相关约瑟夫环

package com.someusefuldesign.demo; import java.util.ArrayList; /约瑟

桃扇骨/ 2022年08月13日 15:54/ 0 赞/ 182 阅读

相关约瑟夫环

\include<stdio.h> \include<stdlib.h> /\ 约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围

╰半夏微凉°/ 2022年08月07日 01:53/ 0 赞/ 204 阅读

相关约瑟夫环

约瑟夫环约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个

怼烎@/ 2022年07月15日 13:39/ 0 赞/ 199 阅读

相关约瑟夫环

N个人坐成一个圆环（编号为1 - N），从第1个人开始报数，数到K的人出列，后面的人重新从1开始报数。问最后剩下的人的编号。例如：N = 3，K = 2。2号先出列，然后是

桃扇骨/ 2022年06月11日 06:26/ 0 赞/ 208 阅读

相关约瑟夫环

【问题描述】编号为 1,2,...,n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。现在给定一个随机数 m>0，从编号为 1 的人开始，按顺时针方向 1

今天药忘吃喽~/ 2022年04月22日 06:06/ 0 赞/ 254 阅读

相关约瑟夫环

> 约瑟夫环运作如下： > 1、一群人围在一起坐成 \[2\] 环状（如：N） > 2、从某个编号开始报数（如：K） > 3、数到某个数（如：M）的时候，此人出列，

阳光穿透心脏的1/2处/ 2022年03月22日 16:38/ 0 赞/ 302 阅读

相关约瑟夫环

约瑟夫环：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规

曾经终败给现在/ 2022年02月28日 00:54/ 0 赞/ 236 阅读

相关约瑟夫环

编号为1，2，…，n的n个人按顺时针方向围坐在一张圆桌周围，每人持有一个密码（正整数）。一开始任选一个正整数m作为报数上限值，从第一个人开始按顺时针方向自1开始报数，报到m时

r囧r小猫/ 2021年12月20日 04:29/ 0 赞/ 320 阅读

相关约瑟夫环

int cir(int n,int m) { int p=0; for(int i=2;i<=n;i++) {

我会带着你远行/ 2021年12月16日 15:13/ 0 赞/ 330 阅读