В вашем решении все более-менее правильно, кроме элементарной ошибки: chance
ведь надо накапливать
chance += funct(n - 1, q - i) / 6.0;
а у вас простое присваивание поставлено.
Один из вариантов математики решения может быть построен так:
Если D - количество всевозможных способов разложения числа Q на сумму N натуральных слагаемых из диапазона [1, 6] (считая перестановки слагаемых разными разложениями), то величина
P = D / 6N
и даст нам требуемую вероятность.
Как найти величину D?
Если забыть на минутку о том, что слагаемые не должны превышать 6, то количество всевозможных разложений P(Q, N) будет равно
D0 = P(Q, N) = CN-1Q-1 = (Q-1)! / (N-1)!(Q-N)!
Среди этих разложений будут и "неправильные" разложения, т.е. разложения с большими слагаемыми, превышающими 6. Их надо исключить из подсчета.
Если предположить, что есть как минимум одно большое слагаемое, то можно показать, что количество всевозможных разложений D1 с таким слагаемым равно количеству разложений величины Q-6 на N слагаемых, умноженному на N
D1 = P(Q - 6, N) * N = CN-1Q-7 * N = CN-1Q-7 * C1N
Чтобы исключить из общего количества разложения с большими слагаемыми, количество D1 нужно вычесть из количества D0.
Выполнив такое вычитание мы правильно исключили из подсчета разложения с ровно одним большим слагаемым. Однако мы тем самым два раза вычли количество разложений с ровно двумя большими слагаемыми одновременно, три раза вычли количество разложений, в которых есть ровно три больших слагаемых, четыре раза вычли количество разложений, в которых есть ровно четыре больших слагаемых, и т.д.
Это избыточное вычитание надо компенсировать.
Количество разложений с как минимум двумя большими слагаемыми равно
D2 = P(Q - 12, N) * C2N = CN-1Q-13 * C2N
Это количество нужно прибавить обратно к величине D0 - D1. Разложения с ровно двумя большими слагаемыми были вычтены дважды через D1 и прибавлены один раз через D2. Итого: мы правильно исключили из подсчета разложения с ровно двумя большими слагаемыми.
Однако выполнив такое прибавление, мы три раза прибавили разложения, в которых есть ровно три больших слагаемых, шесть раз прибавили разложения, в которых есть ровно четыре больших слагаемых и т.д.
Это тоже необходимо компенсировать.
Количество разложений с как минимум тремя большими слагаемыми равно
D3 = P(Q - 18, N) * C3N = CN-1Q-19 * C3N
Это количество нужно вычесть из величины D0 - D1 + D2. Разложения с ровно тремя большими слагаемыми были вычтены трижды через D1, прибавлены трижды через D2 и снова вычтены один раз через D3. Итого: мы правильно исключили из подсчета разложения с ровно тремя большим слагаемым.
И так далее, и так далее, и так далее: прибавляем, вычитаем, прибавляем, вычитаем величины Di
Di = P(Q - 6*i, N) * CiN = CN-1Q-6*i-1 * CiN
Этот внешне запутанный процесс - ни что иное, как подсчет через классический принцип включений-исключений. Наша искомая величина D будет равна
D = D0 - D1 + D2 -
D3 + D4...
до тех пор пока мы не дойдем либо до DN (количество разложений, в которых все слагаемые большие), либо до такого Dk, что Q-6*k < N
Вот и вся математика.
Разумеется, попытка реализации таких вычислений "в лоб" для ваших диапазонов входных значений потребует поддержки арифметики больших чисел. А для небольших значений целочисленная реализация на С или С++ может выглядеть так (даже не упрощая формулу для Di)
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef unsigned long long huge_value;
huge_value C(unsigned k, unsigned n)
{
assert(k <= n);
if (k > n / 2)
k = n - k;
assert(k <= n / 2);
huge_value num = 1, den = 1;
for (; k > 0; --k, --n)
{
num *= n;
den *= k;
}
assert(num % den == 0);
return num / den;
}
huge_value pow(unsigned a, unsigned b)
{
huge_value p = 1;
for (huge_value m = a; b > 0; b >>= 1, m *= m)
if ((b & 1) != 0)
p *= m;
return p;
}
int main()
{
const unsigned N = 100;
const unsigned Q = 100;
huge_value D = 0;
bool add = true;
for (unsigned i = 0, q = Q + 6; i < N && q >= N + 6; ++i, add = !add)
{
q -= 6;
huge_value Di = C(i, N) * C(N - 1, q - 1);
D += add ? Di : -Di;
}
printf("Q = %u, N = %u: P = %lg\n", Q, N, (double) D / pow(6, N));
}
Хотя если вас интересует только финальная вероятность, но не точные количества разложений, то простая замена unsigned long long
на double
приведет к более чем удовлетворительному по точности результату.