Как найти алгоритм для решения задачи на определение вероятности выпадения определённо суммы случайных величин?

237

28 января 2018, 02:59

С++ .Ребят подскажите как решать это,не могу найти решение\алгоритм\мат. аппарат. В интернетах нашёл вот что. Собственно ресурсы где я что то похожее нашёл

http://www.cyberforum.ru/pascal/thread1591818.html
https://acmp.ru/index.asp?main=task&id_task=619
https://acmp.ru/asp/gb.asp?id=619 (комментарии)
http://opennotes.ru/knowledge/vba-knowledge/algoritm-poiska-vsex-kombinacij-chisel-dayushhix-zadannuyu-summu-na-vba/
похожие задачи в англ учебнике в "разделе 2" http://www.madandmoonly.com/doctormatt/mathematics/dice1.pdf
https://www.intuit.ru/studies/courses/648/504/lecture/17184?page=11&keyword_content=SMS

Сама задача: Кубик, грани которого помечены цифрами от 1 до 6, бросают N раз. Найти вероятность того, что сумма выпавших чисел будет равна Q. Ограничения: 1 <= N <= 500, 1 <= Q <= 3000. Входные данные В первой строке находятся числа N и Q через пробел. Выходные данные

Вероятность того, что сумма выпавших чисел будет равна Q.

Примеры

Входные данные 1 1 Выходные данные 1.66666666666667E-0001 Входные данные 2 2 Выходные данные 2.77777777777778E-0002

Пробовал решить рекурсивно, но выдаёт неправильные результаты. Проверял правильность расчётов вот по этому источнику https://acmp.ru/index.asp?main=task&id_task=619

Моя попытка решить рекурсивно:

#include <stdio.h>
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
#include <iomanip>
double funct(int n, int q) {
    if (q < n) return 0;
    if ((6 * n) < q) return 0;
    if (q == n){
        return (1.0 / pow(6.0, n));
    }
    double chance = 0.0;
    for (int i = 1;i <= 6;i++) {
        chance = funct(n - 1, q - i) / 6.0;
    }
    return chance;

};
//using namespace std;
int main()
{
    std::cout << "\n 1<=N<=500; 1<=Q<=3000\n\n\n";
    int a, b;
    std::cin >> a >> b;
    std::cout <<  std::setprecision(40)<< std::scientific << funct(a, b);
    getchar();
    getchar();
    return 0;
}

Answer 1

Попробуйте такой вариант:

unsigned long long m[3001][501]; // В глобальной области видимости - зануленный
unsigned long long count(int Q, int N)
{
    if (Q < N)    return 0;
    if (Q > 6*N)  return 0;
    if (N == 1)   return (Q >= 1 && Q <= 6) ? 1 : 0;
    if (Q <= 0)   return 0;
    if (N == 0)   return 0;
    if (m[Q][N] != 0) return m[Q][N];
    for(int j = 1; j <= 6; ++j)
        m[Q][N] += count(Q-j,N-1);
    return m[Q][N];
}

Вроде бы unsigned long long впритирку должно хватать...

Ну, и выводить count(Q,N)/pow(6,N).

Update
Нет, unsigned long long не проходит. Надо попробовать такой вариант - с double. Если пройдет - ура, если не пройдет - значит, либо использовать длинную арифметику, либо искать другие пути...

struct { double d; bool b; } m[3001][501];
double count(int Q, int N)
{
    if (Q < N)    return 0;
    if (Q > 6*N)  return 0;
    if (N == 1)   return (Q >= 1 && Q <= 6) ? 1 : 0;
    if (Q <= 0)   return 0;
    if (N == 0)   return 0;
    if (m[Q][N].b) return m[Q][N].d;
    double r = 0;
    for(int j = 1; j <= 6; ++j)
        r += count(Q-j,N-1);
    m[Q][N].d = r;
    m[Q][N].b = true;
    return m[Q][N].d;
}
cout << count(Q,N)/pow(6,N) << endl;