约瑟夫环的递推公式怎么理解

约瑟夫环问题是一个经典的数学问题，描述为：n个人围成一圈，从某个人开始报数，每报数到m的那个人出圈，直到最后只剩下一个人留在圈中。递推公式可以表示为：

f(1) = 0 （表示一个人留在圈中时的情况）
f(i) = (f(i-1) + m) % i （i>1，表示i个人留在圈中时的情况）

其中f(i)表示最后留下的人在这i个人中的编号。简单来说，递推公式的含义是：在剩下i个人时，第一个被淘汰的人在圈中的编号为 m % i，接下来每一次淘汰的人在圈中的编号都是相对于当前编号为m的人的m % (i-1)。由此递归推导可以得到最后留下的人在圈中的编号。

相关问题

约瑟夫环问题 python

约瑟夫环是一个经典的问题，也被称为约瑟夫问题。假设有n个人，编号从0到n-1，他们围成一个圈坐下来。从编号为0的人开始，依次数m个人，数到第m个人时，将其从这个圈中删除。然后从下一个人开始重新计数，继续数m个人，直到圈中只剩下一个人为止。这个问题的解决方法有很多，其中比较常见的是使用递推公式来解决。

以下是一个Python实现的例子：

def josephus(n, m):
    if n == 1:
        return 0
    else:
        return (josephus(n-1, m) + m) % n

n = 10
m = 3
print("The chosen one is", josephus(n, m))

其中，`n`表示总人数，`m`表示数到第几个人需要出圈。该函数使用递归的方式求解，当只剩下一个人时，返回编号为0的人即为获胜者。

用c语言解释一下约瑟夫环问题

约瑟夫环问题是一个经典的问题，描述如下：有n个人围成一圈，从第一个人开始报数，报到m的人出圈，剩下的人继续从1开始报数，直到剩下最后一个人。现在给定n和m，求最后剩下的人的编号。

以下是两种用C语言解决约瑟夫环问题的方法：

1. 递归法

/* 用递归解决约瑟夫环问题 n指的是总人数，m指的是每次最大报到的数值，i是第i次，该函数每次可以求出第i次扔海里的人的编号 */
int Algo3(int n,int m,int i){
    if(i==1) return (n+m-1)%n;
    else return (Algo3(n-1,m,i-1)+m)%n;
}

void main(){
    int n=5; //假设5个人围坐一圈
    int m=2; //数到2的那个人出环
    printf("假设第一次从编号为1的人开始数，数到%d的那个人出环\n",m);
    for(int i=1;i<=n;i++)
        printf("第%d次出环的元素是%d\n",i,Algo3(n,m,i)+1); //因为求出的结果是数组中的下标，最终的编号还要加1
}

2. 迭代法

/* 用迭代解决约瑟夫环问题 递推公式： f(N,M)=(f(N−1,M)+M)%N f(N,M)表示，N个人报数，每报到M时杀掉那个人，最终胜利者的编号 f(N−1,M)表示，N-1个人报数，每报到M时杀掉那个人，最终胜利者的编号 */
int Algo4(int n,int m){
    int i,p=0;
    for(i=2;i<=n;i++){
        p=(p+m)%i;
    }
    return p+1; //因为求出的结果是数组中的下标，最终的编号还要加1
}

void main(){
    int n=5; //假设5个人围坐一圈
    int m=2; //数到2的那个人出环
    printf("假设第一次从编号为1的人开始数，最后出环的是：%d\n",Algo4(n,m));
}