猴子选大王是哪一类的题目？？快！！！！

Question

编程程序！

Answer 1

实际是Josephus(约瑟夫)问题

[问题描述]

M只猴子要选大王，选举办法如下：所有猴子按1…M编号围坐一圈，从第1号开始按顺序1，2，…，N报数，凡报到N的猴子退出到圈外，如此循环报数，直到圈内只剩下一只猴子时，这只猴子就是大王。

M和N由键盘输入，打印出最后剩下的那只猴子的编号。

[问题分析]

这个例题是由古罗马著名史学家Josephus提出的问题演变而来的，所以通常称为Josephus(约瑟夫)问题。

在确定程序设计方法之前首先来考虑如何组织数据，由于要记录m只猴子的状态，可利用含m个元素的数组monkey来实现。利用元素下标代表猴子的编号，元素的值表示猴子的状态，用monkey[k]=1表示第k只猴子仍在圈中，monkey[k]=0则表示第k只猴子已经出圈。

程序采用模拟选举过程的方法，开始时将报数变量count置为1，用变量current表示当前报数的猴子的编号，初始时也置为1，变量out记录出圈猴子数。当count=n时，对当前报数的猴子作出圈处理，即monkey[current]：=0， count：=0，out：=out+1。然后继续往下报数，直到圈中只剩一只猴子为止（即out=m-1）。

[程序1-1]

const maxm=100;

var i，m，n，count，current，out:integer;

monkey:array [1..maxm] of integer;

begin

write('Input m，n:'); readln(m，n);

for i:=1 to m do monkey[i]:=1;

out:=0; count:=1; current:=1;

while out<m-1 do

begin

while count<n do

begin

repeat{寻找圈上的下一只猴子}

current:=current+1;

if current=m+1 then current:=1

until monkey[current]=1;

count:=count+1

end;

monkey[current]:=0; out:=out+1; count:=0

end;

for i:=1 to m do

if monkey[i]=1 then writeln('The monkey king is no.'，i)

end.

[运行程序]下划线表示输入

Input m，n:8 3

The monkey king is no.7

[程序1-2]

在组织数据时，也可以考虑只记录仍在圈中的猴子的情况。用一个线性表按编号由小到大依次记录圈中所有猴子的编号，每当有猴子出圈时，即从线性表中删除对应元素，表中元素减少一个。程序中用变量rest表示圈中剩余的猴子数，即线性表中元素的总数。

const maxm=100;

var i，m，n，current，rest:integer;

monkey:array [1..maxm] of integer;

begin

write('Input m，n:'); readln(m，n);

for i:=1 to m do monkey[i]:=i;

rest:=m; current:=1;

while rest>1 do

begin

current:=(current + n - 1) mod rest;

if current=0 then current:=rest;

for i:=current to rest-1 do monkey[i]:=monkey[i+1];

rest:=rest-1

end;

writeln('The monkey king is no.'，monkey[1])

end.

[程序1-3] 题目修改一下：

现在改成从第P个开始，每隔M只报数，报到的退出，直到剩下一只为止。最后剩下的为猴王。问：猴王是原来的第几只猴子？

Const maxn=1000;

Var monke:array[1..maxn] of integer; {N个猴子的标记}

N，nn，p，m，I，j:integer;

Function no(I:integer):integer;

Begin

While I>n do I:=I-n;

No:=I;

End;

Begin

Readln(n，p，m);

For I:=1 to n do monkey[i]:=I;

P:=no(p+m-1);

nn:=n;

For I:=1 to n-1 do

Begin

nn:=nn-1;

for j:=p to nn do monkey[j]:=monkey[j+1];

p:=no(p+1);

end;

writeln(‘THE KING OF MONKEY IS: ’，MONKEY[P]);

end.

[程序1-4] 用数组模拟单向循环链表

以上程序的缺点：移动很多元素，再改进如下：

Const maxn=1000;

Type node=record

No，next:integer; {N个猴子的标记和下一个邻居}

End;

Var monke:array[1..maxn] of node;

n，p，m，i:integer;

Begin

Readln(n，p，m);

For I:=1 to n do begin monkey[i].no:=I;monkey[I].next:=I+1;end;

Monkey[n].next:=1;

P:=p-1;if p=0 then p:=n;

While n>1 do

begin

for I:=1 to (m-1) mod n do

p:=monkey[p].next;

monkey[p].next:=monkey[monkey[p].next].next;

n:=n-1;

end;

writeln(p);

end.

[程序1-5] 再修改一下：

你一定听说过约瑟夫问题吧？！即从n个人中找出唯一的幸存者。现在老约瑟夫将组织一个皆大欢喜的新游戏，假设n个人站成一圈，从第1人开始交替的去掉游戏者，但只是暂时去掉（例如，首先去掉2），直到最后剩下唯一的幸存者为止。幸存者选出后，所有比幸存者号码高的人每人将得到1TK（一种货币），永久性的离开。其余剩下的人将重复以上的过程，比幸存者号码高的人每人将得到1TK后离开。一旦经过这样的过程后，人数不再减少，最后剩下的那些人将得到2TK。请你计算一下老约瑟夫一共要付出多少钱？