一道高中计算机算法题，求解

Question

有n 只猴子选大王，先从头至尾1 ... p 报数，报到p 的猴子退出；
报至尾后，再从尾至头继续报数（注意：如果报到尾时不是p，则反过来
报数仍然从尾开始，即尾部的这个猴子将连续被报2 个数），仍然是报到p
的猴子退出；报到头后，再从头继续，......；直至剩下最后1 个猴子，即
为选出的大王。

Answer 1

如果n>p，那猴子没报完，数字就没了，怎么办？

Answer 2

VB里面就用Collection吧，要模拟链表的话也可以，不过要用类

Answer 3

Private Sub Form_Load()
    Dim C As New Collection, i As Integer, p As Integer, n As Integer, forward As Boolean
    p = Val(InputBox("请输入p值", , "9"))
    n = Val(InputBox("请输入n值", , "10"))
    
    If p < 1 Or n < 1 Then MsgBox "数据错误": Exit Sub
    
    For i = 1 To n
        C.Add i
    Next i
    
    i = 1: forward = True: n = C.Count
    Do Until n = 1
        i = i + IIf(forward, 1, -1) * (p Mod (n * 2) - 1)
Retry:
        If i > n Then i = 2 * n - i + 1: forward = False: GoTo Retry
        If i < 1 Then i = -i + 1: forward = True: GoTo Retry
        C.Remove i
        n = C.Count
        i = i + IIf(forward, 0, -1)
        If i > n Then i = n: forward = False
        If i < 1 Then i = 1: forward = True
    Loop
    
    MsgBox "大王诞生:" & CStr(C.Item(1))
End Sub

Answer 4

Private Sub Command1_Click()
    Dim n As Integer
    Dim p As Integer
    Dim cm() As Integer
    Dim cp As Integer
    Dim bf As Boolean
    Dim i As Integer
    n = Val(Text1)
    p = Val(Text2)
    ReDim cm(n)
    For i = 1 To n
        cm(i) = i
    Next i
    cp = 0
    bf = True
    Do While n > 1
        For i = 1 To p
            If bf Then
                cp = cp + 1
            Else
                cp = cp - 1
            End If
            If cp = n + 1 Then
                bf = False
                cp = n
            ElseIf cp = 0 Then
                bf = True
                cp = 1
            End If
        Next i
        For i = cp To n - 1
            cm(i) = cm(i + 1)
        Next i
        n = n - 1
        If bf = True Then cp = cp - 1
        If cp = n And bf = True Then
            cp = n + 1
            bf = False
        ElseIf cp = 1 And bf = False Then
            cp = 0
            bf = True
        End If
        
    Loop
    Print cm(1)
End Sub

Answer 5

不过投机取巧了，QB和Pascal里面都没有集合对象的。用链表替换，总的来说思路不变。只是我觉得我的很混乱，不太好

Answer 6

这个是对象吗？呵呵，我记得是数据类型而已
也有add方法，count属性吗？不会吧……呵呵

Answer 7

PROGRAM ex1_2_10(input,output);
TYPE
arr=array[ 1..100] of 0..1;
VAR
h :arr;{猴子是否在列的记录数组，1 为在列，0 为已出列}
i,m,n,p,f,s:byte;
PROCEDURE num(var n:byte);
begin
if n>1 then {递归终止条件为只剩1 个猴子}
begin
case i mod 2 of {判断是正方向还是反方向报数}
1:for f:=1 to m do {正方向报数处理}
if h[ f] <>0 then {只对在列的猴子进行处理}
begin
inc(s);{报数变量递增}
if s=p then begin {报到p 作以下处理}
s:=0;{报数计数重新开始}
dec(n);{猴子数减1}
h[ f] :=0 {该猴子清除出数组}
end
end;
0:for f:=m downto 1 do {反方向报数处理与正方向类似}
if h[ f] <>0 then
begin
inc(s);
if s=p then
begin s:=0;dec(n);h[ f] :=0 end
end
end;
inc(i);{i 是报数方向计数器，奇数为正向，偶数为反向}
num(n){用新的在列猴子数进入新的递归}
end
end;
BEGIN
write('Input n,p:');readln(n,p);
for i:=1 to n do h[ i] :=1;{猴子是否在列的记录数组置初值}
i:=1;{报数方向计数器置初值，表示正方向开始报数}
m:=n;{m 记录猴子总数，用于正反方向对全数组扫描，因为ｎ 将变小}
s:=0;{报数计数器置初值}
num(n);{开始以猴子总数进入递归}
i:=1;while h[ i] =0 do inc(i);{找出在列的唯一一个猴子}
writeln('The leader is:',i){即选出的大王}
END.Pascal参考答案，这个递归也太...

Answer 8

没有缩进，好乱阿@_@PROGRAM ex1_2_10(input,output);TYPE
  arr=array[ 1..100] of 0..1;VAR
  h :arr;{猴子是否在列的记录数组，1 为在列，0 为已出列}
  i,m,n,p,f,s:byte;PROCEDURE num(var n:byte);
begin
  if n>1 then {递归终止条件为只剩1 个猴子}
  begin
    case i mod 2 of {判断是正方向还是反方向报数}
    1:
      for f:=1 to m do {正方向报数处理}
        if h[ f] <>0 then {只对在列的猴子进行处理}
        begin
          inc(s);{报数变量递增}
          if s=p then begin {报到p 作以下处理}
            s:=0;{报数计数重新开始}
            dec(n);{猴子数减1}
            h[ f] :=0 {该猴子清除出数组}
          end
        end;
    0:
      for f:=m downto 1 do {反方向报数处理与正方向类似}
        if h[ f] <>0 then
        begin
          inc(s);
          if s=p then
          begin
            s:=0;
            dec(n);
            h[ f] :=0
          end
        end
    end;
    inc(i);{i 是报数方向计数器，奇数为正向，偶数为反向}
    num(n){用新的在列猴子数进入新的递归}
  end
end;BEGIN
  write('Input n,p:');readln(n,p);
  for i:=1 to n do h[ i] :=1;{猴子是否在列的记录数组置初值}
  i:=1;{报数方向计数器置初值，表示正方向开始报数}
  m:=n;{m 记录猴子总数，用于正反方向对全数组扫描，因为ｎ 将变小}
  s:=0;{报数计数器置初值}
  num(n);{开始以猴子总数进入递归}
  i:=1;while h[ i] =0 do inc(i);{找出在列的唯一一个猴子}
  writeln('The leader is:',i){即选出的大王}
END.看了一下，真是白x……这种递归……浪费堆栈~！