자바 버 전 - 고전 알고리즘 '조세 프 링 문제' (기업 고주파 필기시험 알고리즘 문제)

고전 알고리즘 - 조세 프 링 문제 (초급 판) 는 전형 적 인 예제 에 직접 올 랐 다. 사례 1: n 개인 (번호 1, 2, 3. n 으로 각각 표시) 이 원탁 주위 에 둘 러 앉 았 다.번호 가 1 인 사람 부터 번 호 를 매기 고 m 까지 센 사람 이 나열 한다.그의 다음 사람 은 또 1 부터 숫자 를 매기 기 시 작 했 고 m 까지 센 그 사람 이 또 나 왔 다.이 규칙 에 따라 원탁 주위 사람들 이 모두 나 올 때 까지 반복 된다.일반적으로 이런 문 제 를 해결 할 때 우 리 는 번 호 를 0 ~ n - 1 에서 마지막 결과 + 1 은 바로 원래 의 문제 의 해 이다.마지막 열 거 된 사람의 번호 문 제 를 구하 다.
흔히 볼 수 있 는 해법 은 세 가지 가 있다. 배열, 링크 와 재 귀 이다.
기업 필기시험 을 이해 하고 준비 하기 위해 본 고 는 이 알고리즘 의 자바 문제 풀이 템 플 릿 을 제시 하고 목록 (Array List) 데이터 구 조 를 사용한다.

package yuesefuhuan;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	int n=sc.nextInt();//           
    	int m=sc.nextInt();//   m    
        List<Integer> circleQueque = new ArrayList<Integer>();
        //       ，       
        for (int i = 0; i < n; i++) { 
            circleQueque.add(i + 1);
        }
        int start = 0; //         
        //           1 ，    
        while (circleQueque.size() >1) {  
        	//                   
            int curPopIndex = (start + m - 1) % circleQueque.size();    
            //              ，           
            circleQueque.remove(curPopIndex);    
            start = curPopIndex;
        }
		System.out.print("        ："+circleQueque.get(0));
    }
}

고전 알고리즘 - 조세 프 링 (변종 판) 사례 2: 이미 알 고 있 는 n 개인 (번호 1, 2, 3... n 으로 각각 표시) 이 원탁 주위 에 둘 러 앉 았 다.번호 가 1 인 사람 부터 번 호 를 매기 고 m = 1, 2, 3.
조심해!!!이곳 의 m 는 더 이상 고정 값 이 아니 라 등차 수열 이다.

package yuesefuhuan;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int start = 0;
        int m = 1;
        List<Integer> circleQueque = new ArrayList<>();
        //       
        for(int i = 1 ;i <n; i++){
            circleQueque.add(i+1);
        }
        while(circleQueque.size()>1){
            //         ，     ，  (start+m)   1
            int curPopIndex = (start+m)%circleQueque.size();
            circleQueque.remove(curPopIndex);
            //m      
            m++;
            //                 
            start = curPopIndex;
        }
        System.out.println("        ："+circleQueque.get(0));
    }
}