约瑟夫问题递归求解
2026-04-01 16:35:03
发布于：北京
定义状态：设 f(n, k) 表示：n个人、报数到 k 时出圈，最后的幸存者编号（为了后边好计算，从0开始编号，最后结果加1即可）。
显然，当n为1时，幸存者编号为0。
当n>1时，考虑淘汰一人
n个人编号为：0~(n-1)，报k（编号k-1）出圈，下个人（编号k）从0开始继续报数。
问题规模缩减到 f(n-1,k)，n-1个人，报数到 k 出圈的约瑟夫环问题
新环和原环编号对应：
新环编号：0、1、2、...、(n-2)
原环编号：k%n、(k+1)%n、(k+2)%n、....、(k+(n-2))%n
问题 f(n-1,k)求解结果为新环编号，对应原环编号为(f(n-1,k)+k)%n
#include<bits/stdc++.h>
using namespace std;
//返回幸存者编号，从0开始计数
int f(int n, int k){
if(n==1) return 0; //只有1人，返回编号0
return (f(n-1, k)+k)%n;
}
int main(){
int n, k;
cin>>n>>k;
cout<<f(n, k)+1;
return 0;
}
全部评论 6
ACGO_疑问ACGO_疑问ACGO_疑问
ACGO_大佬ACGO_大佬ACGO_大佬
ACGO_赞ACGO_赞ACGO_赞
ACGO_顶呱呱ACGO_顶呱呱ACGO_顶呱呱
ACGO_gif_激动ACGO_gif_激动ACGO_gif_激动
ACGO_gif_发送爱心ACGO_gif_发送爱心ACGO_gif_发送爱心
ACGO_gif_崇拜ACGO_gif_崇拜ACGO_gif_崇拜
ACGO_ACACGO_ACACGO_AC
ACGO_OKACGO_OKACGO_OK1周前 来自 陕西
2假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑假笑
1周前 来自 陕西
0
纯享版：
#include<bits/stdc++.h>
using namespace std;
int f(int n, int k){
if(n==1) return 0;
return (f(n-1, k)+k)%n;
}
int main(){
int n, k;
cin>>n>>k;
cout<<f(n, k)+1;
return 0;
}1周前 来自 陕西
0
有帮助，赞一个