约瑟夫问题

传闻那位著名的犹太塔西佗。 约瑟夫斯有以下情节:罗马占据贾塔帕特后来地,39 东西犹太人,约瑟夫斯和他的同伴藏在东西岩洞里。,39个犹太人决定死,而过失被敌人的诱惹。,因而决定他杀的方式,41私人的在戒指里,高音的人开端计数,报纸上每第三私人的就必然的他杀。,当时的又是下东西,直到每私人的他杀身亡。。还,约瑟夫斯 而他的同伴们不情愿尾随。先从一人,超越K-2私人的(因第东西人曾经被穿插),使笑死了K。经营,再次共轭K-1私人的,使笑死了K。即将到来的行动方向沿着边缘地带举行。,直到经受住只剩东西人,这私人的可以继续活受到。问题是,认真说总额,一开端要站在到哪里才干使无效被处决?Josephus要他的同伴先假装的发生兴趣,他把同伴和本身修理在第十六和第三十东西安置。,当时的逃避亡故游玩。

十七世纪,法国算学家蟑螂副歌在《纽子开关》中详细叙述了这样地东西情节。:15信徒15 非新教教徒的在公海中成为危险物在位的。,部分地人必然的入海,支持物的人挺过决定并宣布。,因而我想出了东西大大地:30人被东西打电话给所为敌对势力包围,从高音的人以次动身,每第九私人的把他扔进海里。,即将到来的革命继续到除非15人。。讯问到何种地步修理法度,让任何时分非天主教徒走向大洋。

问题剖析与算法设计

约瑟夫问题并不难,更很多方式可以处置它;主部的电视节目的总安排也有大多数人找头。。在这若干上举办了一种意识到方式。。

用头顶中有30私人的被东西打电话给所为敌对势力包围。,相应地,它引起敝运用迂回地链来表现。,作文装饰可用于整队环链。。作文中有两个盟员。,东西是落到下东西人的有指导意义的事物,一环;次要的个问题是这私人的条件被标到了大洋。,1岁,它还在船上。从第东西人,计数那些的心外出焉扔过大洋的人。,每号码字到9,将作文达到目的标志更代替0,这刻薄的这私人的曾经被扔到海里去了。。数到15人被扔进海里。。

约瑟夫环的操纵如次:

1、排围坐肩并肩的。:N)

2、从数字中计数(如:K)

3、计数到一定当(如:当m),这私人的在名单上。,下东西人背

4、一直社交活动,直到独家制造的产品都外出名单中,约瑟夫环的末了

约瑟夫问题是个知名的问题:n个人品被东西打电话给所为敌对势力包围,高音的次报道,M将被使笑死了,经受住东西分开,支持物的将被使笑死了。譬如,n=6。,M=5,倒霉的按次是:5,4,6,2,3,1。

剖析:

(1)因每私人的除非两种房地产才干落下和寿命。,因而你可以运用棕色的的阻塞来标志每私人的的房地产。,真的可以用来表现亡故,虚伪代表寿命。

(2)每私人的在开端时都是活着的,因而阻塞的开胃小吃都是不公正的。

(3)模仿毙伤行动方向,直到持相当人都倒霉。

C 法典:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

#include

usingnamespacestd;

main ()

{

BoLA〔101〕={ 0 }

intn,m,i,f=0,t=0,s=0;

cin >>n>>m;

do

{

数圆达到目的每个定位

if(t>n)

t=1;//装饰模仿环,经受住东西连接到第东西。

if(![t]

s++;//第t个定位上重要的人物则报数

免得(s=m)/介绍报纸的当是m

{

S=0;/对齐0

cout <

[t]=1;/此人已亡故。,设置为空

f ;////亡故数 1

}

} while (f!=n);//直到持相当人都倒霉

}

它是由链表还要阻塞意识到的东西公共点。:模仿统统游玩行动方向,不光顺序写得越来越烦人。,时期错综复杂的状态可达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收复表是右手的吗?!!换背的表示很复杂。,我置信每私人的都能把它喷出:x”=(x+k) mod n

你到何种地步察觉(N-1)私人的计数问题的处置方式?,只察觉(N-2)人品的处置节目。(N-2)人品的处置节目?自然,这是n-3的影响。 —- 这显然是东西倾倒的问题。!好了,意向出现了,以下复回表示:

让F表明i玩家玩游玩M和经受住的数字。,经受住的水果是f[n]

递推表示

f=0;

f=(f+m) mod i; (i>1)

用即将到来的表示,敝要做的是从1-n阶中找出f的值。,经受住的水果是f[n]。因在现实寿命中,数字不变的从1开端。,敝出口f[n 1

因它是浸的再发作,你不喜欢拘押每东西F,顺序也非常复杂。:

c++

pascal

var n,m,i,S:概数

begin

写(n) M =”);

读取(n),m);

for i:=2 to n do

s:=(s+m) mod i;

写的 winner is ”,s+1);

end.

该算法的时期错综复杂的状态为O(n)。,模拟算法曾经受胎很大的改善。。算n,M当宏大的,一从事过失问题。。可见,算学战略的恰当运用,它不光能使设计发生复杂,而且它常常乘以算法的生产力。。

约瑟夫问题10e100版(from vijios)

象征 Description

n个人品邀集东西圈。。从重要的人物开始做某事,正转地编号。从数字1开端正转的121开端。,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…

这是东西精致的的方式!!

总体思绪如次:

读(a)

②b:=1,C:= 1 {b是组中元素的数量,C是加在一起数的}

③while c

6。C:= C-B{归属到前一组}

X:= Ac{计算目的组的元素。

⑧ans:=x*2-1{求出该元素}

⑨write(ans)

有一种有理性的方式,准确度很高,不成问题。。我写的法典更不雅观,因这是高音的次敲门,重写行动方向,一点点复杂的行动方向与主顺序相结合。,因而稍微乱,稍微淫秽。供一种商讨方式是右手的。

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

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

vara,b,c:array[1..105]ofinteger;

la, lb ,lc,I:概数

S:字母串

procedureincc;

varI:概数

begin

fori:=1to105doc:=c+b;

fori:=1to104doifc>9then

begin

c:=c+cdiv10;

c:=cmod10;

end;

end;

functioncxiaoa:boolean;

varI:概数

begin

cxiaoa:=false;

fori:=105downto1do

ifc 完毕;完毕

elseifc>athenbreak;

end;

proceduredoubleb;

varI:概数

begin

fori:=1to105dob:=b*2;

fori:=1to104doifb>9then

begin

b:=b+bdiv10;

b:=bmod10;

end;

end;

procedure decc ;

vari,J:概数

begin

fori:=1to104do

ifc>=bthenc:=c-belse

begin

j:=i+1;

whilec[j]=0doinc(j);

whilej> ido

begin

c[j]:=c[j]-1;

C[J-1 ]=C[J-1]+10

DEC(J)

end;

C=C-B

end;

end;

procedurefua;

varI:概数

begin

fori:=1to104do

ifa>cthena:=a-celse

begin

A:=A-1

a:=a+10;

答:

end;

end;

procedure奥蒂特

vari,J:概数

begin

fori:=1to105doa:=a*2;

fori:=1to104doifa>9then

begin

a:=a+adiv10;

a:=amod10;

end;

IFA〔1〕>0TeNENA〔1〕:=A〔1〕-1

begin

j:=2;

whilea[j]=0doinc(j);

whilej>1do

begin

a[j]:= a[j] – 1

a[j-1 ]=a[j-1 ]+10

DEC(J)

end;

A〔1〕:=A〔1〕- 1

end;

fori:=105downto1doifa>0thenbeginj:=i;完毕;完毕;

弗里:= Jordto1dWrRITE(a)

end;

begin

readln(s);

L:=音长(s)

fori:=ladownto1doa:= ord (S[La 1-i])-ORD(′0)

b[1]:=1;

c[1]:=1;

whilecxiaoado

begin

doubleb;

incc;

end;

decc;

fua;

奥蒂特

end.

问题表述

一. 问题象征:

一包小淘气被编号了。,号码是1,2,3 …m,小淘气组(m)以1-m的按次排列。,从高音的开端,数到n,小淘气要分开即将到来的戒指,这样地以次决定并宣布,直到经受住一只小淘气留在戒指里,小淘气是大王的巨型的。

约瑟夫

“密电码问题”

问题象征:编号1、2、3、…、n的人品正转的正转地旋转,每私人的考虑密电码(正概数)。从约定

编号1的人开端,正转的按次从1开端,当约定的M号码被民族语言文字时,中止音讯的当,民族语言文字M的人被列出,并将

他的密电码是东西新的M值,从他到下东西人正转地,叫进来1号,余可类推,直到持有

持相当名单。请设计东西顺序来查找列表的按次,n没有30,M和密电码值是从键盘输出的。

二. 基本想要:

(1) 输出信息:输出M,n m,n 作为概数,n

(2)国文提示符如m个小淘气,数n 进展法,猴王的当是多少? ,安排东西职务来意识到即将到来的职务

设计处置

顺序

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

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

#include

#include

#defineLENsizeof(structmonkey)//精确地解释structmonkey即将到来的典型的音长

structmonkey

{

int num ;

structmonkey*next;

};

structmonkey*create(intm)

{

structmonkey* head ,*p1,*p2;

inti;

p1=p2=(structmonkey*)malloc(LEN);

head=p1;

head->num=1;

for(i=1,p1->num=1;i

{

p1=(structmonkey*)malloc(LEN);

p1->num=i+1;

p2->next=p1;

p2=p1;

}

p2->next=head;

returnhead;

}

structmonkey*findout(structmonkey*start,国际交通联合

{

inti;

structmonkey*p;

i=n;

p=start;

(I=1;I)

p=p->next;

returnp;

}

structmonkey*letout(structmonkey*last)

{

structmonkey*out,*next;

out=last->next;

last->next=out->next;

next=out->next;

free (出)

returnnext;

}

intmain()

{

intm,n,i, king ;

structmonkey*p1,*p2;

Printf(请输出小淘气的当m:\n)

scanf (“%d”,&m);

Printf(小淘气的当每回N:\n)

SCANF(%D),&n);

if(n==1)

{

king=m;

}

else

{

p1=p2=create(m);

(I=1;I)

{

p2=findout(p1,n);

p1=p2;

p2=letout(p1);

p1=p2;

}

king=p2->num;

自在(P2)

}

Printf:孙悟空的号码是:%d\n”,巨型的)

return0;

}

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

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

孙悟空问题(约瑟夫环)

#include

#include

#include

intfre( char mok[],英特克)

{

inti;

Printf(小淘气号:\n”);

(i=0;莫克[i])!=”\0”;i++)

printf(“%d\t”,出口是开球前的数字。,测量法用

当作(i=k;MK〔i〕!=”\0”;i++)

{

莫克[i]=莫克〔I+1〕

}//东西迂回地,K后革囊元素

putchar(”\n”);

(i=0;莫克[i])!=”\0”;i++)

printf(“%d\t”,MOK[I]);/ / /出口踢出数,测量法用

Printf(n继续下朝反方向:\n)

getch();//暂时的停顿,测量法用

return0;

}

intmain()

{

charmok[50];

inti;

intn,s,b;//n代表小淘气的总额。;S代表走近;B表现元素的当和Kings的号码。

intj,k;//j,K是对齐

MOK〔0〕=1;///设定初值MOK〔0〕,使反面编号更复杂

Printf:请输出小淘气总额:\n”);

SCANF(%D),n);/ / /输出小淘气总额

(I=1;I)

{

莫克[i]=i+1

给小淘气编号

MOK [n]=‘0’;/// 0表现阻塞的末了

Printf(请进入 迂回地单位 :\n”);

SCANF(%D),s);/单位音长

B= N;///人口财产调查猴数

for(j=1,k=0;; j++ ,k++)

{

if(b==1)

{

b=mok[0];

break ;

免得元素只剩东西,当时的自在的迂回地

if(j==s)

{

Printf(外出名单除非:%d\n”,莫克[K]

FRE(MOK),k)/ /元素提前地移位的职务

b–;

j=1;

把小淘气踢外出外,重新安置对齐J。

免得(MK〔K 1〕==‘0’’)

K=- 1;///恢复对齐K,因后面有K ,K是在重新安置的按照,-1。

决定条件是阻塞的经受住东西元素,恢复对齐K。

system(“colorc”);//无赖,更改CMD外界的色。

Printf(经受住巨型的是他:%d\n”,b);

return0;

}

C语言文字顺序3 运用阻塞模仿链表

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

#include

#include

intmain()

{

int*person,i,node,n,m;

scanf(“%d%d”,&n,&m);

person=(int*)malloc(sizeof(int)*(n+1));

(I=1;I)<=n;i++)//设定初值圈

{

人[i]=i+1;/i代表东西编号为i的人。,人[i]的值表现下东西数字的号码。

}

person[n]=1;//编号为n的下东西人的号码是1

node=1;

while (杂种)!免得东西人的下东西人过失他本身。,它刻薄的超越1人。

{

(I=1;I)

{

杂种=人[杂种];/ / /下东西人的号码是杂种。,杂种的值源自前东西杂种的人[杂种]。

}

Prtf(%d),人[杂种];;/ / / /出口数

person[node]=person[person[node]];//修正倒霉的人的前东西人的person[node]为倒霉的人的后东西人的编号

node=person[node];//这句话达到目的node是倒霉的人后东西人

}

Prtf(%d),杂种);/出口 经受住挺过者 的编号

return0;

}

pascal顺序:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

var

a:array[1..10000]ofinteger;

n,s,i,J:概数

begin

read (m,n);

FII:= Tododo[i]:=1

j:=0;

fori:=1tomdo

begin

s:=0;

whiles

begin

ifj

elsej:=1;

s:=s+a[j];

end;

write (j);

a[j]:=0;

end;

end.

C 顺序

1

2

3

4

5

6

7

8

9

#include

intmain()

{

intn,m,i,s=0;

printf(“NM=”);scanf(“%d%d”,&n,&m);

(I=2;I)<=n;i++)s=(s+m)%i;

printf(“Thewinneris%d\n”,s+1);

return0;

}

约瑟夫算学算法

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

#include

#include

intmain( void )

{

intn,i=0,m,p;

scanf(“%d%d”,&n,m)//n的总额,m步长

而( i)<=n)

{

p=i*m;

while(p>n)

p=p-n+(p-n-1)/(m-1);

printf(“%d\n”,p);

}

getch();

return0;

}

约瑟夫复回算法

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

#include

usingnamespacestd;

intking(intM,国际交通联合

{

intk=0;

当作(iTi=2;I)<=M;i++)

k=(k+N)%i;

return++k;}i

ntmain()

{

intn,m;

(SnF)(%D%d),&n,&m)&&n&&m)

{

cout <

}

return0;

}

2、PHP模拟算法

PHP有东西高度地正确的的信息作文模拟节目,能很简约地处置这样地的问题!

1

2

3

4

5

6

7

8

9

10

11

12

13

functionking($n,$m){

$monkey=range(1,n);/ /模仿延续装饰

$i=0;

(计数(小淘气)>1)

I =1;/开端反省

$head=array_shift($monkey);//直线东西东西出列最后面的小淘气

if($i%$m!=0){

array_push($monkey,;)/ / / /免得心外出焉M或M并联的并联,当时的把小淘气放回附属物里。

要不然,就保持了。

}

return$monkey[0];

}

回响廉价出售,巨型的(3),4),小淘气

笔算处置

笔算处置约瑟夫问题

当m较小时 ,用书写技巧方式处置问题,

M=2

即n个人品被东西打电话给所为敌对势力包围,1,2,1,2的数字,亡故民族语言文字2,直到除非东西人分开。

当N=2^k的时分,第东西计数是经受住东西亡故。,

在流行中的恣意当的自然数n 持有可以表现为n=2 ^ k t。,在位的,T

因而当重要的人物死的时分,剩的除非2人 ,2 K组达到目的第东西人是经受住东西落下的。。即将到来的2 ^ k人达到目的第东西人是2T 1。

这样就求出了当M=2时约瑟夫问题的解:

2的最大2靠动力行进,不大于S的最大靠动力行进。,记为2^k,经受住东西亡故的人是2(n-2 ^ k) 1。

M=3

即n个人品被东西打电话给所为敌对势力包围,1,2,3,1,2,3的数字,亡故民族语言文字3,直到除非东西人分开。

这比M=2更复杂。

以n=2009为例

N=2009,在M=3倒霉的经受住东西人被记为F(2009)。,3),或答应以容易的地不恝于怀F(2009)

假定即将到来的文件分类中有N个人品,下朝反方向将使笑死了[ N/3 ]。,[]表现取整,更N – [ N/3 ]人分开了

将即将到来的n人设为A1,a2,…,A(n-1),an

从A1开端,打电话给后来地,剩的是A1,a2,a4,a5,…a(n-n mod 3-1),a(n-n mod 3+1),..,an

因而你可以欢迎它:

1、在这朝反方向中经受住东西亡故是 mod 3),下朝反方向达到目的第东西数是(n n) mod 3+1)

2、若3|n,经受住的亡故是新的F(N-[N/3 ])人品。

若n mod 3≠0 F(n-(n/3)]<=n mod 3则经受住死的人为新朝反方向的第n-[n/3]+F(n-[n/3])-(n mod 3)人

若n mod 3≠0 F(n-(n/3)]>n mod 3个上东西已故的是新的F(n-(n/3))-(n)的新朝反方向。 mod 3)人

3、东西新的K人品对应的原始人品 3×[(k-1)/2 ] (k-1)mod 2+1私人的

综合性中学1,2,可获得3:

F(1)=1,F(2)=2,F(3)=2,F(4)=1,F(5)=4,F(6)=1,

当f(n-〔n/3〕〕<=n mod 3时 k=n-[n/3]+F(n-[n/3])-(n mod 3),F(n)=3×[(k-1)/2 ] (k-1)mod 2+1

当f(n-〔n/3〕〕>n mod 3时 k=F(n-[n/3])-(n mod 3) ,F(n)=3×[(k-1)/2 ] (k-1)mod 2+1

该算法需求计算 [log(3/2)2009]次 即将到来的数字不超越22,可以经过书写技巧来计算

这样:

高音的圈,669人将倒霉,经受住东西在即将到来的戒指里倒霉的人是2007,更1340私人的分开了。,

次要的圈,使笑死了446人,更894私人的分开了。

第三圈,使笑死了298人,更596私人的分开了。

月的第四日圈,使笑死了198人,更398私人的分开了。

第五圈,使笑死了132人,更266私人的分开了。

六年级圈,使笑死了88人,更178私人的分开了。

第七圈,使笑死了59人,更119私人的分开了。

第八圈,使笑死了39人,更80私人的分开了。

第九圈,使笑死了26人,更54私人的分开了。

第十圈,使笑死了18人,还剩36私人的

十一发,使笑死了12人,还剩24私人的

十二圈,使笑死了8人,还剩16私人的

十三个的圈,使笑死了5人,还剩11私人的

十四岁圈,使笑死了3人,还剩8私人的

十五个人组成的橄榄球队圈,使笑死了2人,还剩6私人的

F(1)=1,F(2)=2,F(3)=2,F(4)=1,F(5)=4,F(6)=1,

当时的推回

F(8)=7 F(11)=7 F(16)=8 f(24)=11 f(36)=16 f(54)=23 f(80)=31 f(119)=43 f(178)=62 f(266)=89 f(398)=130

F(596)=191 F(894)=286 F(1340)=425 F(2009)=634

交互式视频设备百科全书登记(附图片)由N上载,免得涉嫌民事侵权行为,请亲属您的客户保养,敝将基准有关规定即时处置这些问题。。不是答应,制止商业网站和支持物重复、抢占车站满意的;有理用户,请选出出处。

发表评论

电子邮件地址不会被公开。 必填项已用*标注