若干名小孩围成一个圆圈，从第一个小孩开始数......

Question

这就是有名的Josephus问题
该算法用数组循环实现，但数组是线性排列的，而小孩是围成圈的，使用"加1求模"的方法解决循环！ 
代码如下：
import java.io.*; 
class Josephus 
{ 
public static void main(String[] args) 
{ 
int num=10; 
int interval=2; 
int[] a=new int[num]; 
for(int i=0;i<num;i++) 
a[i]=i+1; 
System.out.println("please input the interval: "); 
try 
{InputStreamReader isr=new InputStreamReader(System.in); 
BufferedReader br=new BufferedReader(isr); 
String s=br.readLine(); 
interval=Integer.parseInt(s); 
} 
catch(Exception e) 
{System.out.println(e); 
} for(int i=0;i<num;i++) 
System.out.print(a[i]+" "); 
System.out.print("\n"); int k=1; 
int i=-1; while(true) 
{ 
for(int j=0;j<interval;) 
{i=(i+1)%num; 
if(a[i]!=0) 
j++; 
} if(k==num) break; 
System.out.print(a[i]+" "); 
a[i]=0; 
k++; 
} System.out.print("\nNo. "+a[i]+" boy&acute;ve won.\n"); 
} } 
这是我在一个网站上摘抄下来的代码。

Answer 1

俺自己写了一个。public class Link
{
    public static final int LENGTH = 1000;
    public static final int STEP = 12;
    public static final int START_POS = 0;
    public static Node[] node = new Node[LENGTH];
    public static int counter = 0;    public static void deleteNode(Node node)
    {
        String kickedInfo = "第".concat(String.valueOf(++counter)).concat(
            "个被踢出的是").concat(String.valueOf(node.key)).concat("号！");
        System.out.println(kickedInfo);
        node.prev.next = node.prev.next.next;
        node.next.prev = node.next.prev.prev;
    }    public static void createLink()
    {
        for (int i = 0;i < node.length;i++)
        {
            node[i] = new Node();
            node[i].key = i;
        }        for (int i = 0;i < node.length;i++)
        {
            node[i].next = node[(i + 1) % node.length];
            node[i].prev = node[(i - 1 + 1000) % node.length];
            /**
             * System.out.println("setNext prev: " + node[i].prev.key);
             * System.out.println("setNext self: " + node[i].key);
             * System.out.println("setNext next: " + node[i].next.key);
             */
        }
    }    public static void kickNode()
    {
        Node tempNode = new Node();        tempNode = node[START_POS];
        while (true)
        {
            Node memory = tempNode;
            for (int i = 0;i < STEP;i++)
            {
                tempNode = tempNode.next;
            }            if (tempNode.key == memory.key)
            {
                for (int i = 0;i < STEP;i++)
                {
                    tempNode = tempNode.next;
                    String remainedInfo = "剩下的第".concat(String.valueOf(i)).
                        concat("个是").concat(String.valueOf(tempNode.key)).
                        concat("号！");
                    System.out.println(remainedInfo);
                }
                break;
            }
            else
            {
                deleteNode(tempNode);
                tempNode = tempNode.next;
            }
        }
    }    public static void main(String[] args)
    {
        createLink();
        kickNode();
    }
}class Node
{
    public int key;
    public Node next;
    public Node prev;
}

Answer 2

作了修改。public static void kickNode()
{
    Node tempNode = new Node();    tempNode = node[START_POS];
    while (true)
    {
        Node memory = tempNode;
        for (int i = 0;i < STEP;i++)
        {
            tempNode = tempNode.next;
        }        if ((tempNode.key == memory.key) && (tempNode.next == tempNode))
        {
            String winnerInfo = "胜利者是".concat(String.valueOf(tempNode.key)).
                concat("号！");
            System.out.println(winnerInfo);
            break;
        }
        else
        {
            deleteNode(tempNode);
            tempNode = tempNode.next;
        }
    }
}

Answer 3

凑凑热闹!
   public static void child(int n) {
      boolean[] num= new boolean[n];      for(int index = 0,counter = 0, leftChild = num.length;
          leftChild > 0;
          index = (index+1) % num.length) {
         if(num[index])
            continue;
         counter++;
         if(counter % n != 0)
            continue;
         System.out.println((num.length-leftChild+1)+":kick out:"+(index+1));
         num[index]= !num[index];
         leftChild--;
      }
   }

Answer 4

还记得上个学期的时候用汇编写的Josephus，贴来凑热闹^_^
;//////////////////////////////////////
;       Josephu  Puzzle
;/////////////////////////////////////
; N saved in DI
; M saved in SI
; S saved in CX,then dispose
;/////////////////////////////////////
.model small
.data
msg1 db 'Plz input N:','$'
msg2 db 'Plz input M:','$'
msg3 db 'Plz input S:','$'
msg4 db 'The sequence is :',13,10,'$'
msg5 db 'Continue(Y/N)?','$'
err_msg db 'Input illegal...Try again...',13,10,'$'
queue db 100 dup(0) .code
;****************************************************
;----------------------------------------------------
main proc far
start:
mov ax,@data
mov ds,ax
rpt:
call init
call process
call output

lea dx,msg5
mov ah,1
int 21h
cmp al,'y
jz rpt
cmp al,'Y'
jz rpt
;return to DOS
mov ah,4ch
int 21h
main endp
;------------------------------------------------------
process proc near

process endp
;------------------------------------------------------
init proc near
in_N:
lea dx,msg1
call show_msg
sub dx,dx
call decibin
cmp dx,0fffh
jz err_N
cmp bx,0
jz err_N
cmp bx,101
ja err_N
mov di,bx
call crlf
jmp in_M
err_N:
lea dx,err_msg
call show_msg
jmp in_N
in_M:
lea dx,msg2
call show_msg
sub dx,dx
call decibin
cmp dx,0fffh
jz err_M
cmp bx,0
jz err_M
cmp bx,11
ja err_M
mov si,bx
call crlf
jmp in_S
err_M:
lea dx,err_msg
call show_msg
jmp in_M
in_S:
lea dx,msg3
call show_msg
sub dx,dx
call decibin
cmp dx,0fffh
jz err_S
cmp bx,0
jz err_S
cmp bx,di
ja err_S
mov cx,bx
call crlf
jmp  exit_init
err_S:
lea dx,err_msg
call show_msg
jmp in_S
exit_init:
ret
init endp
;------------------------------------------------------
show_msg proc near
push ax
mov ah,9
int 21h
pop ax
ret
show_msg endp
;-------------------------------------------------------
crlf proc near
push dx
push ax
mov dl,13
mov ah,2
int 21h
mov dl,10
mov ah,2
int 21h
pop ax
pop dx
ret
crlf endp
;---------------------------------------------------------

Answer 5

贴错了:-P
;//////////////////////////////////////
;/    Josephu Problem            /
;//////////////////////////////////////
;  S saved in SI
;//////////////////////////////////////
.model small
.data
queue db 101 dup(?)
M dw 0
N dw 0
msg1 db 'Plz input N(1<=N<=100):','$'
msg2 db 'Plz input M(1<=M<=10):','$'
msg3 db 'Plz input S(1<=S<=N):','$'
msg4 db 'The sequence is :',13,10,'$'
msg5 db 'Continue(Y/N)?','$'
err_msg db 'Input illegal...Try again...',13,10,'$'
1 db  '/////////// Josephu Puzzle /////////// ',13,10,'$'
2 db '//         by    silentfish         // ',13,10,'$'          
3 db '////////////////////////////////////// ',13,10,'$'
.code
main proc far
start:
mov ax,@data
mov ds,ax
lea dx,1
call show_msg
lea dx,2
call show_msg
lea dx,3
call show_msg
call crlf
main_rpt:
call init
call process
call crlf
lea dx,msg5
call show_msg
mov ah,1
int 21h
call crlf
cmp al,'y'
jz main_rpt
cmp al,'Y'
jz main_rpt
; terminate
mov ah,4ch
int 21h
main endp
;----------------------------------------------
show_msg proc near
push ax
mov ah,9
int 21h
pop ax
ret
show_msg endp
;-----------------------------------------------
crlf proc near
push dx
push ax
mov dl,13
mov ah,2
int 21h
mov dl,10
mov ah,2
int 21h
pop ax
pop dx
ret
crlf endp
;-----------------------------------------------
; src-- bx
binidec proc near
push ax
push bx
push dx
cmp bx,0
jnz  non_zero
mov dl,30h
mov ah,2
int 21h
jmp return
non_zero:
push cx
mov di,0
mov cx,10000d
call dec_div
mov cx,1000d
call dec_div
mov cx,100d
call dec_div
mov cx,10d
call dec_div
mov cx,1d
call dec_div
pop cx
return:
pop dx
pop bx
pop ax
ret
dec_div proc near
mov ax,bx
mov dx,0
div cx
mov bx,dx
cmp al,0
jnz display
cmp di,0
jz skip
display:
mov dl,al
add dl,30h
mov ah,2
int 21h
cmp di,0
jnz skip
inc di
skip:
  ret
dec_div endp
binidec endp
;-------------------------------------------------
decibin proc near
mov bx,0
mov dx,0
;Get digit from keyboard,convert to binary
newchar:
mov ah,1
int 21h
sub al,30h
jl check
cmp al,9d
jg check
cbw
xchg ax,bx
mov cx,10d
mul cx
xchg ax,bx
; add digit in AX to number in BX
add bx,ax
inc dx
jmp newchar
check:
add al,30h
cmp al,13
jnz error
cmp dx,0
jz error
jmp exit
error:
mov dx,0fffh
exit:
ret
decibin endp
;------------------------------------------
init proc near
mov bx,0
r:
mov queue[bx],0
inc bx
cmp bx,102
jnz r
in_N:
lea dx,msg1
call show_msg
sub dx,dx
call decibin
cmp dx,0fffh
jz err_N
cmp bx,0
jz err_N
cmp bx,100
ja err_N
mov N,bx
call crlf
jmp in_M
err_N:
call crlf
lea dx,err_msg
call show_msg
jmp in_N
in_M:
lea dx,msg2
call show_msg
sub dx,dx
call decibin
cmp dx,0fffh
jz err_M
cmp bx,0
jz err_M
cmp bx,10
ja err_M
mov M,bx
call crlf
jmp in_S
err_M:
call crlf
lea dx,err_msg
call show_msg
jmp in_M
in_S:
lea dx,msg3
call show_msg
sub dx,dx
call decibin
cmp dx,0fffh
jz err_S
cmp bx,0
jz err_S
cmp bx,N
ja err_S
mov si,bx
call crlf
jmp  exit_init
err_S:
call crlf
lea dx,err_msg
call show_msg
jmp in_S
exit_init:
ret
init endp
;------------------------------------
process proc near
mov cx,0
mov ax,0
rotate:
cmp queue[si],0
jnz nxt
inc ax
cmp ax,M
jnz nxt
 ; Display
inc queue[si]
inc cx
mov bx,si
call binidec
mov dl,' '
mov ah,2
int 21h
mov dl,' '
mov ah,2
int 21h
mov ax,cx
mov bx,10d
div bl
cmp ah,0
jnz eod
call crlf
eod:
 ; end of display
cmp cx,N
jz ok
sub ax,ax ;clear ax
nxt:
cmp si,N
jz front
inc si
jmp rotate
front:
mov si,1
jmp rotate
ok:
ret
process endp
;---------------------------------------
end