算法：约瑟夫问题：01 来源：百度百科
2021-02-04 01:16
阅读：723
算法：约瑟夫问题：01 来源：百度百科
时间：2020-04-29 00:38:09
阅读：76
评论：0
收藏：0
[点我收藏+]
标签：程序 res last lse order pac procedure 要求 因此
https://baike.baidu.com/item/约瑟夫问题/3857719?fr=aladdin
约瑟夫问题问题来历
据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
[1]
17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。
问题分析与算法设计
约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。这里给出一种实现方法。
题目中30个人围成一圈，因而启发我们用一个循环的链来表示，可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人是否被扔下海的标记，为1表示还在船上。从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0，表示该人已被扔下海了。这样循环计数直到有15个人被扔下海为止。
约瑟夫问题一般形式
编辑约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3，1。
分析：
（1）由于对于每个人只有死和活两种状态，因此可以用布尔型数组标记每个人的状态，可用true表示死，false表示活。
（2）开始时每个人都是活的，所以数组初值全部赋为false。
（3）模拟杀人过程，直到所有人都被杀死为止。
约瑟夫问题pascal代码1
?
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
var a:array [1..20] of integer;
n,m,i,j,k,n1,m1:integer;
beginreadln(m,n);for i:=1 to m do
a[i]:=i;
m1:=m;n1:=1;
while m1>0 do
begin j:=(n+n1-1-1) mod m1 +1;
n1:=j;
m1:=m1-1;
writeln(a[j]);
for k:=j to m1 do
a[k]:=a[k+1];
end;
end.
|
约瑟夫问题C++代码：
?
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#includeusing namespace std;
main(){ bool a[101]={0};
int n,m,i,f=0,t=0,s=0;
cin>>n>>m;
do
{
++t;//逐个枚举圈中的所有位置
if(t>n)
t=1;//数组模拟环状，最后一个与第一个相连
if(!a[t])
s++;//第t个位置上有人则报数
if(s==m)//当前报的数是m
{
s=0;//计数器清零
cout
a[t]=1;//此处人已死，设置为空
f++;//死亡人数+1
}
}while(f!=n);//直到所有人都被杀死为止
} |
c++代码2
?
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include #include #include using namespace std;
int main()
{ int a[8],i,t,k;
for(i=1;i
{
a[i]=1;
}
t=8;
k=0;
while(t>0)
{
for(i=1;i
{
if(a[i]==1)
{
k++;
if(k==5)
{
k=0;
a[i]=0;
cout
t--;
if(t==0)
{
break;
}
}
}
}
}
return 0;
} |
无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm），当n，m非常大（例如上百万，上千万）的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。
为了讨论方便，先把问题稍微改变一下，并不影响原意：
问题描述：n个人（编号0~(n-1）），从0开始报数，报到（m-1）的退出，剩下的人继续从0开始报数。求胜利者的编号。
我们知道第一个人（编号一定是（m-1）mod n) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m mod n的人开始）：
k k+1 k+2 ... n-2,n-1,0,1,2,... k-2
并且从k开始报0。
我们把他们的编号做一下转换：
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
变换后就完完全全成为了（n-1）个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x‘=(x+k) mod n
如何知道（n-1）个人报数的问题的解？对，只要知道（n-2）个人的解就行了。（n-2）个人的解呢？当然是先求（n-3）的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：
令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]
递推公式
f[1]=0;
f[i]=(f[i-1]+m) mod i; (i>1）
有了这个公式，我们要做的就是从1-n顺序算出f的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1
由于是逐级递推，不需要保存每个f，程序也是异常简单：
约瑟夫问题pascal代码2
?
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
var n,m,i,s,p:integer;
a:array[1..10000] of integer;
begin read(n,m);//这步不用说了吧？
for i:=1 to n do
a[i]:=1;//先全部赋值1
p:=0;s:=0;//统计人数和报数字用的
repeat
for i:=1 to n do
begin
if a[i]=0
then continue; //用于等会排除出圈者
s:=s+a[i];//不断累加(报数字)
if s=m then//出圈者
begin
write(i,‘ ‘);打印出圈者;
a[i]:=0;//明白刚才continue的意思了吧
p:=p+1;//人数减少一个;
s:=0;//重头报起.
end;
end;
until p=n;//直到人数到了
end.
|
约瑟夫问题pascal代码3
?
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
Var a:array[1..100] of integer;
n,m,i,j,p:integer;
Begin write(‘Input n,m:‘);
readln(n,m);
for i:=1 to n do
a[i]:=i;
p:=1; {p用于记录报数的位置}
for i:=1 to n do
begin
j:=0; {j用于记录报到的人数}
while j
begin
if a[p]0 then j:=j+1;
if p=n then p:=1 else p:=p+1; {处理边界情况}
end;
if p1
then begin write(a[p-1],‘ ‘);a[p-1]:=0;end {处理边界情况}
else begin write(a[n],‘ ‘);a[n]:=0;end;
end;
end.
|
约瑟夫问题pascal代码4
?
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
Var a:array[1..100] of integer;
n,m,p,i,j:integer;
Begin readln(n,m);
for i:=1 to n-1 do
a[i]:=i+1;
a[n]:=1;
p:=n;
for i:=1 to n do
begin
for j:=1 to m-1 do
p:=a[p];
write(a[p],‘ ‘);
a[p]:=a[a[p]];
end;
End.
|
约瑟夫问题c++
?
|
1
2
3
4
5
6
7
8
9
10
|
#include using namespace std;
const int m = 3;
int main()
{ int n, f = 0;
cin >> n;
for (int i = 1; i
cout
} |
约瑟夫问题pascal代码5
?
|
1
2
3
4
5
6
7
8
|
var n,m,i,s:integer;
beginwrite(‘N M =‘);
read(n,m);for i:=2 to n do
s:=(s+m) mod i;
writeln(‘The winner is ‘,s+1）;
end.
|
这个算法的时间复杂度为O(n），相对于模拟算法已经有了很大的提高。算n，m等于一百万，一千万的情况不是问题了。可见，适当地运用数学策略，不仅可以让编程变得简单，而且往往会成倍地提高算法执行效率。
约瑟夫问题python代码
该程序基于python3.x实现
?
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#控制参数：nums = 41
call = 3
#参数定义：peoples = []
for _ in range(nums):
peoples.append(True)
result = []
num =1
#主逻辑while(any(peoples)):
for index,people in enumerate(peoples):
if people:
if num == call:
peoples[index] = False
result.append(index+1)
# print(index+1)#每轮的出局者 # print(peoples)#每次的队列状态 num = 1 else:
num += 1
print(‘-‘* 25)
print(‘\n总数为%d,报数为%d‘ % (nums,call))
print(‘约瑟夫序列为：\n%s\n‘ % result)
print(‘-‘* 25)
|
约瑟夫问题约瑟夫问题10e100版（from vijios)
描述 Description
n个人排成一圈。从某个人开始，按顺时针方向依次编号。从编号为1的人开始顺时针“一二一”报数，报到2的人退出圈子。这样不断循环下去，圈子里的人将不断减少。由于人的个数是有限的，因此最终会剩下一个人。试问最后剩下的人最开始的编号。
输入格式 Input Format
一个正整数n，表示人的个数。输入数据保证数字n不超过100位。
输出格式 Output Format
一个正整数。它表示经过“一二一”报数后最后剩下的人的编号。
样例输入 Sample Input
9
样例输出 Sample Output
3
时间限制 Time Limitation
各个测试点1s
注释 Hint
样例说明
当n=9时，退出圈子的人的编号依次为：
2 4 6 8 1 5 9 7
最后剩下的人编号为3
初见这道题，可能会想到模拟。可是数据实在太大啦！！
我们先拿手来算，可知n分别为1，2，3，4，5，6，7，8...时的结果是1，1，3，1，3，5，7，1...
有如下规律：从1到下一个1为一组，每一组中都是从1开始递增的奇数，且每组元素的个数分别为1，2，4...
这样就好弄了！！
大体思路如下：
①read(a)
②b:=1,c:=1{b为某一组的元素个数，c为累计所加到的数}
文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：算法：约瑟夫问题：01 来源：百度百科
文章链接：http://soscw.com/index.php/essay/50671.html
文章标题：算法：约瑟夫问题：01 来源：百度百科
文章链接：http://soscw.com/index.php/essay/50671.html
评论
亲，登录后才可以留言！