간단 한 조세 프 링 알고리즘

5151 단어 조세 프 링
조세 프 링 문 제 는 유 다 야 이야기 에서 기원 되 었 다.조세 프 링 문제 의 대 의 는 다음 과 같다.
로마인 들 은 다리 타 파 트 를 점령 하고 41 명 이 동굴 속 에 숨 어 큰 재난 을 피 했다.이 41 명 중 에는 역사학자 조 셉 스 (조세 프) 와 그의 친 구 를 포함한다.나머지 39 명 은 로마인 에 게 굴복 하지 않 겠 다 며 집단 자살 을 결심 했다.모두 가 자살 방안 을 세 웠 습 니 다. 이 41 명 은 모두 원 을 그 렸 습 니 다. 첫 번 째 사람 부터 시계 방향 으로 번 호 를 매기 기 시 작 했 습 니 다. 번호 가 3 인 사람 은 바로 자살 한 다음 에 다음 사람 이 다시 번 번 번 호 를 시 작 했 습 니 다. 여전히 번호 가 3 인 사람 은 바로 자살 을 했 습 니 다. 모든 사람 이 자살 로 죽 을 때 까지.
조세 프 와 그의 친 구 는 자살 하고 싶 지 않 았 다. 그래서 조세 프 는 두 사람 이 똑 같이 자살 방안 에 참 여 했 지만 결국 자살 을 피 했다.실례 지만, 그들 은 어떻게 했 습 니까?
package com.cn.datastruct;



import java.util.Scanner;



//         

public class Josephus {

    static final int Num=41;    //   

    static final int KillMan=3;        //     

    //      

    static void josephus(int alive){

        int []man = new int[Num];

        int count=1;

        int i=0,pos=-1;

        while(count<=Num){

            do{

                pos=(pos+1)%Num;   //   

                if(man[pos]==0)   //           0

                    i++;

                if(i==KillMan){   //    

                    i=0;

                    break;

                }            

            }while(true);

            man[pos]=count;

            System.out.printf(" %2d    !       %2d",pos+1,man[pos]);

            if(count%2==1){

                System.out.printf("->");

            }else{

                System.out.printf("->
"); // } count++; } System.out.println(); System.out.printf(" %d :
",alive); alive = Num - alive; for(i=0;i<Num;i++){ if(man[i]>alive) System.out.printf(" :%d, :%d
", i+1,man[i]); } System.out.println(); } public static void main(String[] args){ int alive; System.out.print(" !
"); System.out.print(" :"); Scanner input = new Scanner(System.in); alive = input.nextInt(); josephus(alive); } }

좋은 웹페이지 즐겨찾기