n 개의 주사 위 를 바닥 에 던 지고 모든 주사 위 를 위로 향 하 는 포인트 의 합 은 S 이다.n 을 입력 하면 S 의 모든 가능 한 값 이 나타 날 확률 을 출력 합 니 다.

분석: 본 문 제 는 '궁 거 법' 과 '동태 기획' 두 가지 사고방식 으로 해결 할 수 있다.
1. 궁 거 법의 기본 사상 은 문제 의 일부 조건 에 따라 답안 의 대체적인 범 위 를 확정 하고 이 범위 에서 모든 가능 한 상황 을 하나하나 검증 하여 모든 상황 이 검 증 될 때 까지 하 는 것 이다.여기 서 우 리 는 n 개의 주사위 가 위로 향 하 는 포인트 와 s 의 개수 f (s) 를 통계 할 수 있 으 며, 그 확률 r (s) = f (s) / pow (6, n):

/*           */
void SumOfCount(int n, int left, int sum, int *arr)
{
    if (left== 0)//   n   
    {
        ++(arr[sum]);//        1
        return ;
    }
    for (int i = 1; i <= 6; ++i)//        1~6
    {
        SumOfCount(n, left - 1, sum + i, arr);
    }
}

/*   S            */
void PrintProbability(int n)
{
    int length = 6 * n + 1;
    int *arr = new int[length];
    memset(arr, 0, length * sizeof(int));

    SumOfCount(n, n, 0, arr);

    for (int j = n; j < length; ++j)
    {
        printf("sum = %d, rate = %d 
", j, arr[j]);
    }

    delete[] arr;
    arr = NULL;
}

2. 동적 계획: n 개의 주사위 꼭대기 포인트 와 s 의 조합 수 f (n, s) 를 설정 하면 마지막 주사위 의 포인트 1 ~ 6, 6 가지 상황 만 고려 합 니 다. f (n - 1, s - 1) 마지막 주사위 포 인 트 는 1 입 니 다.f (n - 1, s - 2) 마지막 주사위 포 인 트 는 2 이다.f (n - 1, s - 3) 마지막 주사위 포 인 트 는 3 이다.f (n - 1, s - 4) 마지막 주사위 포 인 트 는 4 이다.f (n - 1, s - 5) 마지막 주사위 포 인 트 는 5 입 니 다.f (n - 1, s - 6) 마지막 주사위 포 인 트 는 6 이다.그래서 f (n, s) = f (n - 1, s - 1) + f (n - 1, s - 2) + f (n - 1, s - 3) + f (n - 1, s - 4) + f (n - 1, s - 5) + f (n - 1, s - 6) 가 있다.i. 재 귀 방법 (비교적 직접적인) 을 사용한다.

//     n     s    
int GetSum(int n, int s)
{
    if (n == 1)//    1，      
    {
        return (s > 0 && s <= 6) ? 1 : 0;
    }
    if (n == s)//    2，n     s=n
    {
        return 1;
    }
    if (n > s)//    
    {
        return 0;
    }
    int sum = 0;
    for (int i = 1; i <= 6; ++i)
    {
        sum += GetSum(n - 1, s - i);
    }

    return sum;
}

void PrintProbabilityA(int n)
{
    for (int j = n; j < 6 * n + 1; ++j)
    {
        printf("sum = %d, rate = %d 
", j, GetSum(n, j));
    }
}

ii. 순환 방법 사용

void PrintProbabilityB(int n)
{
    int length = 6 * n + 1;
    int *arr = new int[length];
    memset(arr, 0, length * sizeof(int));
    for (int i = 1; i <= 6; ++i)//     1   ;
    {
        arr[i] = 1;
    }
    int j, k;
    for (j = 2; j <= n; ++j)//    ;
    {
        for (k = 6 * j; k >= j; --k)//       ;
        {
            arr[k] = 0;
            for (int m = 1; m <= 6 && k > m; ++m)
            {
                arr[k] += arr[k - m];
            }
        }

        arr[j - 1] = 0;
    }
    for (int j = n; j < length; ++j)
    {
        printf("sum = %d, rate = %d 
", j, arr[j]);
    }

    delete []arr;
    arr = NULL;
}

테스트 코드:

int _tmain(int argc, _TCHAR* argv[])
{
    //     ;
    clock_t start = clock();
    PrintProbability(10);
    printf("%d
", clock() - start);
    //     ;
    start = clock();
    PrintProbabilityA(10);
    printf("%d
", clock() - start);
    //     ;
    start = clock();
    PrintProbabilityB(10);
    printf("%d
", clock() - start);

    return 0;
}

대체적으로 비교 해 보 니 궁 거 법 시간 2242, 재 귀 법 시간 10081, 순환 법 시간 37.