约瑟夫环（Joseph problem）

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

n n n个人标号 0 , 1 , ⋯   , n − 1 0,1,\cdots, n -1 0,1,⋯,n−1逆时针站一圈从 0 0 0号开始每一次从当前的人逆时针数 k k k个然后这个人出局问最后剩下的人是谁

静态链表

洛谷P1996

#include<cstdio>

int main() {
	const int N = 105;
	int nxt[N], n, m;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; ++i) {
		nxt[i] = (i + 1) % n;
	}
	int pre = n - 1, cur = 0, cnt = 0;
	while (nxt[cur] != cur) {
		++cnt;
		if (cnt == m) {
			printf("%d ", cur + 1);
			cnt = 0;
			nxt[pre] = nxt[cur];
			//nxt[cur] = -1;
			cur = nxt[pre];
		}
		else {
			pre = cur;
			cur = nxt[cur];
		}
	}
	printf("%d\n", cur + 1);
    
	return 0;
}

递推

第一个出局的人为 ( k − 1 ) m o d n (k-1) \mathop{mod} n (k−1)modn
将 k , k + 1 , ⋯   , n − 1 , 0 , 1 , 2 ⋯   , k − 1 k,k+1,\cdots, n-1, 0 ,1,2\cdots, k-1 k,k+1,⋯,n−1,0,1,2⋯,k−1从新编号为 0 , 1 , ⋯   , n − 2 0,1,\cdots, n-2 0,1,⋯,n−2
那么问题转化为这 n − 1 n-1 n−1个人里找到第 k k k个人
设重新编号后出局的人为 x x x则这个人原来的编号为 ( x + k ) m o d n \left(x + k\right) \mathop{mod} n (x+k)modn

设 F ( n ) F\left(n\right) F(n)为 n n n个人第 k k k个人出局的编号
则 F ( n ) = ( F ( n − 1 ) + k ) m o d n F\left(n\right) = \left(F\left(n -1 \right) + k\right) \mathop{mod} n F(n)=(F(n−1)+k)modn
并且 F ( 0 ) = 0 F\left(0\right) = 0 F(0)=0
这样就可以O ( n ) \left(n\right) (n)求出最后一个人的编号

洛谷P8671

#include<cstdio>

int main() {
	int n, k;
	scanf("%d%d", &n, &k);
	int res = 0;
	for (int i = 2; i <= n; ++i) {
		res = (res + k) % i;
	}
	printf("%d\n", res + 1);
	return 0;
}

递推加速

当 n n n比较大 k k k比较小的时候
可能好几轮才产生余数即
f ( i ) = f ( i − 1 ) + k < i f ( i + 1 ) = f ( i − 1 ) + k + k < i + 1 ⋮ f ( i + t − 2 ) = f ( i − 1 ) + ( t − 1 ) k < i + t − 2 f ( i + t − 1 ) = f ( i − 1 ) + t k ≥ i + t − 1 \begin{aligned} f\left(i\right) = f\left(i - 1\right) + k &< i\\ f\left(i + 1\right) = f\left(i - 1\right) + k + k &< i + 1\\ \vdots\\ f\left(i + t -2\right) = f\left(i - 1\right) + \left(t-1\right)k &< i+t -2\\ f\left(i + t -1\right) = f\left(i - 1\right) + tk &\ge i+t -1 \end{aligned} f(i)=f(i−1)+kf(i+1)=f(i−1)+k+k⋮f(i+t−2)=f(i−1)+(t−1)kf(i+t−1)=f(i−1)+tk​<i<i+1<i+t−2≥i+t−1​
于是
f ( i + t − 1 ) = f ( i − 1 ) + t k ≥ i + t − 1 ⇒ t ≥ i − 1 − f ( i − 1 ) k − 1 ⇒ t m i n = ⌈ i − 1 − f ( i − 1 ) k − 1 ⌉ f\left(i + t -1\right) = f\left(i - 1\right) + tk \ge i+t -1\Rightarrow t \ge \frac{i - 1-f\left(i-1\right)}{k-1} \Rightarrow t_{min}=\left\lceil \frac{i - 1-f\left(i-1\right)}{k-1}\right\rceil f(i+t−1)=f(i−1)+tk≥i+t−1⇒t≥k−1i−1−f(i−1)​⇒tmin​=⌈k−1i−1−f(i−1)​⌉
换句话说
⌈ i − 1 − f ( i − 1 ) k − 1 ⌉ \left\lceil \frac{i - 1-f\left(i-1\right)}{k-1}\right\rceil ⌈k−1i−1−f(i−1)​⌉轮才产生余数
之后要注意
如果 i + t − 1 > n i + t -1>n i+t−1>n就不用这么算了直接返回 f ( i − 1 ) + ( n − i + 1 ) k f\left(i-1\right) + \left( n - i + 1\right) k f(i−1)+(n−i+1)k

数学

https://godweiyang.com/2018/04/16/concrete-math-8/

杀人游戏

编号 1 , ⋯   , n 1,\cdots, n 1,⋯,n,每次杀 k k k的倍数直到遍历完一轮( k > 1 k>1 k>1)
重新编号杀 k k k的倍数,直到之只有 k − 1 k-1 k−1个人问最后杀的人的编号
举个例子 n = 10 , k = 3 n=10,k=3 n=10,k=3
第一轮杀 3 , 6 , 9 3,6,9 3,6,9
杀完了剩下 1 , 2 , 4 , 5 , 7 , 8 , 10 1,2,4,5,7,8,10 1,2,4,5,7,8,10
重新编号 1 , 2 , 3 , 4 , 5 , 6 , 7 1,2,3,4,5,6,7 1,2,3,4,5,6,7

第二轮杀 3 , 6 3,6 3,6
原编号 4 , 8 4,8 4,8

假设一个幸存人在第 r r r的编号为 y y y,而重新编号在第 r + 1 r+1 r+1为 x x x
显然 y = ⌊ y k ⌋ + x y = \left\lfloor\frac{y}{k}\right\rfloor + x y=⌊ky​⌋+x
设 m = ⌊ y k ⌋ m = \left\lfloor\frac{y}{k}\right\rfloor m=⌊ky​⌋
注意到 y ≢ 0 ( m o d k ) y \not\equiv 0\left(\mathop{mod} k\right) y≡0(modk),
k m + 1 ≤ y ≤ k m + k − 1 k m + 1 ≤ m + x ≤ k m + k − 1 ( k − 1 ) m ≤ x − 1 ≤ ( k − 1 ) m + k − 2 m ≤ ⌊ x − 1 k − 1 ⌋ ≤ m + ⌊ k − 2 k − 1 ⌋ = m \begin{aligned} km + 1 &\le & y &\le&km+k-1\\ km + 1 &\le & m+x &\le&km+k-1\\ \left(k-1\right)m &\le & x -1 &\le&\left(k-1\right)m+k-2\\ m &\le & \left\lfloor\frac{x-1}{k-1}\right\rfloor &\le&m+\left\lfloor\frac{k-2}{k-1}\right\rfloor = m\\ \end{aligned} km+1km+1(k−1)mm​≤≤≤≤​ym+xx−1⌊k−1x−1​⌋​≤≤≤≤​km+k−1km+k−1(k−1)m+k−2m+⌊k−1k−2​⌋=m​
所以 m = ⌊ x − 1 k − 1 ⌋ m = \left\lfloor\frac{x-1}{k-1}\right\rfloor m=⌊k−1x−1​⌋
则 y = ⌊ x − 1 k − 1 ⌋ + x y = \left\lfloor\frac{x-1}{k-1}\right\rfloor + x y=⌊k−1x−1​⌋+x
设 f ( n , k ) f\left(n,k\right) f(n,k)为幸存的人的编号
令 x = f ( n − ⌊ n k ⌋ , k ) x = f\left(n - \left\lfloor \frac{n}{k}\right\rfloor,k\right) x=f(n−⌊kn​⌋,k)
f ( n , k ) = ⌊ x − 1 k − 1 ⌋ + x f\left(n,k\right) = \left\lfloor\frac{x-1}{k-1}\right\rfloor + x f(n,k)=⌊k−1x−1​⌋+x
边界 f ( k , k ) = k f\left(k,k\right) = k f(k,k)=k

hdu2211

国王游戏

有 n n n个人从0依次报数
第一轮报到 0 0 0的人出局
第二轮从下一个人开始从0开始开始报数报到1的人出局以此类推
问最后一个人编号

推导方式与递推类似
第一轮 0 , 1 , 2 , ⋯   , n − 1 0,1,2,\cdots,n-1 0,1,2,⋯,n−1
淘汰 0 0 0

第二轮 1 , 2 , ⋯   , n − 1 1,2,\cdots, n-1 1,2,⋯,n−1
重新编号 0 , 1 , 2 , ⋯   , n − 2 0,1,2,\cdots, n-2 0,1,2,⋯,n−2
淘汰重新编号后的 1 1 1即原编号的 ( 1 + 1 ) m o d n \left(1+1\right)\mathop{mod} n (1+1)modn

第三轮 2 , 3 , ⋯   , n − 2 , 0 2,3,\cdots,n-2,0 2,3,⋯,n−2,0
重新编号 0 , 1 , ⋯   , n − 3 0,1,\cdots,n-3 0,1,⋯,n−3
淘汰重新编号后的 2 2 2,即第二轮编号中的 ( 2 + 2 ) m o d ( n − 1 ) \left(2 + 2\right) \mathop{mod}\left(n-1\right) (2+2)mod(n−1)

容易得到递推公式
f ( i ) = ( f ( i − 1 ) + n − i + 1 ) m o d i f\left(i\right) = \left(f\left(i -1\right) +n - i + 1\right)\mathop{mod} i f(i)=(f(i−1)+n−i+1)modi
其中 f ( 1 ) = 0 f\left(1\right) = 0 f(1)=0

acwing1455
原理是一样的只是这里淘汰第 A i A_i Ai​

#include<cstdio>
int main() {
	const int N = 1005;
	int a[N], n, m, T;
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &m);
		for (int i = 0; i < m; ++i) {
			scanf("%d", &a[i]);
		}
		int res = 0;
		for (int i = 2; i <= n; ++i) {
			res = (res + a[((n - i) % m + m) % m]) % i;
		}
		printf("%d\n", res);
	}
	return 0;
}

k = 2

编号 1 , 2 , ⋯   , n 1,2,\cdots,n 1,2,⋯,n报到2的时候自杀问最后幸存的人的编号

1 , 2 , ⋯   , 2 n − 1 , 2 n 1,2,\cdots, 2n-1,2n 1,2,⋯,2n−1,2n
第一轮之后剩下 1 , 3 , 5 , ⋯   , 2 n − 1 1,3,5,\cdots, 2n - 1 1,3,5,⋯,2n−1
重新编号 1 , 2 , 3 , ⋯   , n 1,2,3,\cdots, n 1,2,3,⋯,n
容易得出 f ( 2 n ) = 2 f ( n ) − 1 f\left(2n\right) = 2f\left(n\right) -1 f(2n)=2f(n)−1

1 , 2 , ⋯   , 2 n − 1 , 2 n , 2 n + 1 1,2,\cdots, 2n-1,2n,2n +1 1,2,⋯,2n−1,2n,2n+1
第一轮之后剩下 1 , 3 , 5 , ⋯   , 2 n − 1 , 2 n + 1 1,3,5,\cdots, 2n - 1, 2n +1 1,3,5,⋯,2n−1,2n+1
接着再把1删了剩下 3 , 5 , ⋯   , 2 n − 1 , 2 n + 1 3,5,\cdots, 2n - 1, 2n +1 3,5,⋯,2n−1,2n+1
重新编号 1 , 2 , 3 , ⋯   , n 1,2,3,\cdots, n 1,2,3,⋯,n
容易得出 f ( 2 n + 1 ) = 2 f ( n ) + 1 f\left(2n +1\right) = 2f\left(n\right) +1 f(2n+1)=2f(n)+1

但是这样还太慢了
打个表

n12345678910111213141516
f ( n ) f\left(n\right) f(n)1131357135791113151

观察： f ( 2 x ) = 1 f\left(2^x\right) =1 f(2x)=1
1 1 , 3 1 , 3 , 5 , 7 ⋯ 1\\ 1,3\\ 1,3,5,7\\ \cdots 11,31,3,5,7⋯
可以发现 2 x 2^x 2x到 2 x + 1 2^{x+1} 2x+1之间的数是一个1为首项公差为2的等差数列
设 n = 2 m + l n = 2^m +l n=2m+l
则
f ( n ) = f ( 2 m + l ) = 2 l + 1 f\left(n\right) = f\left(2^m +l\right) = 2l+1 f(n)=f(2m+l)=2l+1

poj1781

#include<iostream>
#include<string>
using namespace std;
int main() {
	string s;
	while (cin >> s) {
		if (s == "00e0")
			break;
		int a = s[0] - '0', b = s[1] - '0', c = s[3] - '0', n;
		n = a * 10 + b;
		while (c--)
			n *= 10;
		int r = 1;
		while (r <= n)
			r <<= 1;
		int l = n - (r >> 1);//r>>1=r/2,就是不超过n的最大的2的幂2^m+l=n,l=n-2^m;
		cout << (l << 1) + 1 << endl;//f(n)=2*l+1
	}
	return 0;
}
阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
返回列表

上一篇：4年Java开发，阿里被裁两个月，想要26K的工作都找不到！投200份简历，只有4个面试邀请，准备去外包了！...

下一篇：国产linux操作系统——麒麟操作系统的来龙去脉(有下载地址，亲测可用)

“约瑟夫环（Joseph problem）” 的相关文章

MyBatis（三）使用MyBatis完成CRUD（增删改查）1年前 (2023-02-02)
maxcomputer的分区表相关操作1年前 (2023-02-02)
中值滤波算法--C 语言实现1年前 (2023-02-02)
[Computer Networks]一个http请求的完成的全过程1年前 (2023-02-02)
记录create-react-app使用craco-fast-refresh热更新插件，报错Uncaught TypeError: Cannot read properties of undefined (reading 'signature')1年前 (2023-02-02)
光速上手k8s(2023)(containerd)(未完待续)1年前 (2023-02-02)
Go语言学习笔记-11年前 (2023-02-02)
Downie V4.6.4 for Mac 视频下载工具1年前 (2023-02-02)
【linux】linux实操篇之进程管理1年前 (2023-02-02)
【毕业季|进击的技术er】作为一名职场人，精心总结的嵌入式学习路线图1年前 (2023-02-02)

阿里云国际版