'검지offer'면접문제 60:n 주사위 점수

제목: n개의 주사위 포인트

n개의 주사위를 바닥에 놓고 모든 주사위가 위쪽으로 향하는 점수의 합은 s이다.n을 입력하여 s의 모든 가능한 값의 출현 확률을 출력합니다.

사고방식1: 귀속을 바탕으로 시간 효율이 높지 않다

돌아가는 사상은 일반적으로 나누어 다스린다. n개의 주사위를 첫 번째와 나머지 n-1개로 나눈다.먼저 첫 번째 주사위의 각 포인트가 나타나는 횟수를 계산한 다음에 나머지 n-1개의 주사위가 나타나는 포인트의 합을 계산한다.n-1개의 주사위의 점수를 구하는 방법은 앞에서 말한 것과 같다. 즉, n-1개의 주사위를 다시 두 무더기로 나누는 것이다. 첫 번째와 나머지 n-2개.n개의 주사위, 각 주사위 6개의 면, 총 6n개의 조합이 있다.이 6n개의 조합 중에는 틀림없이 중복된 것이 있을 것이다. 우리는 그 범위가 n~6n이라는 것을 알고 있다. 모든 상황에 대해 우리는 캐시 메커니즘으로 기록할 수 있다. 매번 발생할 때마다 우리가 대응하는 단원에 1을 더한다.
우리는 길이가 6n-n+1인 수조를 정의하고, s의 점수가 나타나는 횟수를 수조의 s-n 요소에 저장합니다.왜 6n-n+1인가요?n개의 주사위와 최소 n, 최대 6n이 있기 때문에 이 둘 사이의 모든 상황이 발생할 수 있다. 모두 6n-n+1의 상황이다.
사고방식 1을 바탕으로 자바 참조 코드는 다음과 같다.

private static final int g_maxValue = 6;
    // ， 
    public static void PrintProbability(int number){
        if(number<1) return;
        int maxSum = number*g_maxValue;
        int[] pProbabilities = new int[maxSum-number+1];
        // ， 0 
        for(int i=number;i<=maxSum;i++){
            pProbabilities[i-number] = 0;
        }
        double total = Math.pow(g_maxValue,number);
        //probability(number,pProbabilities); n~6n 
        probability(number,pProbabilities);
        for(int i=number;i<=maxSum;i++){
            double ratio = pProbabilities[i-number]/total;
            System.out.println("i: "+i+" ratio: "+ratio);
        }
    }
    public static void probability(int number,int[] pProbabilities){
        for(int i=1;i<=g_maxValue;i++){// 
            probability(number,number,i,pProbabilities);
        }
    }
    // original ，  current ， ， 
    public static void probability(int original,int current,int sum,int[] pProbabilities){
        if(current==1){
            pProbabilities[sum-original]++;
        }else{
            for(int i=1;i<=g_maxValue;i++){
                probability(original,current-1,sum+i,pProbabilities);
            }
        }
    }

이런 방법은 사고방식이 매우 간결하지만 귀속 실현은 서브문제가 존재하고 반복적으로 해답을 구하는 상황이 발생하기 때문에number가 매우 크면 그 성능이 느려서 받아들일 수 없다.

사고방식2: 순환을 바탕으로 시간 성능이 좋다

귀속은 일반적으로 위에서 아래로 분석하고 해답을 구하지만 순환을 바탕으로 하는 방법은 밑에서 위로 올라간다.순환을 바탕으로 하는 것은 일반적으로 더 적은 공간과 더 적은 시간을 필요로 하고 성능은 비교적 좋지만 일반 코드는 비교적 이해하기 어렵다.
상기 사고방식 2를 바탕으로 자바 참고 코드는 다음과 같다.

// 
    public static void PrintProbability_1(int number){
        if(number<1){
            return;
        }
        int[][] pProbabilities = new int[2][g_maxValue*number +1];
        for(int i=0;i

테스트 용례:

a. 기능 테스트(1,2,3,4개의 주사위의 각 포인트의 확률).b. 특수 입력 테스트(입력 0).c. 성능 테스트(예: 11)

참조:

http://www.cnblogs.com/xuanxufeng/p/6896569.html