Całkowite prawdopodobieństwo danej odpowiedzi danej liczby dodatków [zamknięte] - algorytm, kombinatoryka

Robię C ++ i chcę znaleźć najprostszy sposób na znalezienie całkowitego prawdopodobieństwa danej odpowiedzi danej liczby dodatków.

Na przykład podana odpowiedź to 5, a podana liczba dodatków to 4 (x + x + x + x). Całkowite prawdopodobieństwo, które chcę znaleźć, wynosi 4:

1) 1 + 1 + 1 + 2 = 5
2) 1 + 1 + 2 + 1 = 5
3) 1 + 2 + 1 + 1 = 5
4) 2 + 1 + 1 + 1 = 5

Inny przykład, podana odpowiedź to 6, a podana liczba dodatków to 4 (x + x + x + x). Całkowite prawdopodobieństwo wynosi 10:

1) 1 + 1 + 1 + 3 = 6
2) 1 + 1 + 3 + 1 = 6
3) 1 + 3 + 1 + 1 = 6
4) 3 + 1 + 1 + 1 = 6
5) 1 + 1 + 2 + 2 = 6
6) 1 + 2 + 2 + 1 = 6
7) 2 + 2 + 1 + 1 = 6
8) 2 + 1 + 1 + 2 = 6
9) 2 + 1 + 2 + 1 = 6
10) 1 + 2 + 1 + 2 = 6

Nie mam absolutnie pojęcia, od czego zacząć

Odpowiedzi:

4 dla odpowiedzi № 1

Oto początek dla ciebie.

Spójrz na ten stół

        1   2   3   4   5
+------------------
1     | 1   0   0   0   0
2     | 1   1   0   0   0
3     | 1   2   1   0   0
4     | 1   3   3   1   0
5     | 1   4   6   4   1

Liczba szczytów wzrasta od lewej do prawej, całkowity wzrost w rzędach, np. istnieją 3 sposoby sumowania 3 liczb całkowitych (większych niż 0) w sumie 4 (mianowicie 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1).

---

0 dla odpowiedzi nr 2

Z 4 dodatkami i wynikiem Y, jeśli wszystkie liczbybędzie dodatni i niezerowy oraz wystarczająco mały (<100), możesz to łatwo przynajmniej brutalnie wymusić ... po prostu cykluj wszystkie liczby z 4x dla cykli i jeśli sumują się do przyrostu Y liczby permutacji. Wadą jest złożoność O (N ^ 4), która będzie bardzo powolna.

#include <iostream>
using namespace std;

int main()
{
int y = 6;
int perm = 0;

for(int a = 1; a < y; a++)
for(int b = 1; b < y; b++)
for(int c = 1; c < y; c++)
for(int d = 1; d < y; d++)
{
if((a+b+c+d)==y)
{
cout << a << " + " << b << " + " << c << " + " << d << " = " << y  << endl;
perm++;
}
}
cout << "number of permutations: " << perm << endl;
}

---

0 dla odpowiedzi № 3

To nie jest prawdopodobieństwo co próbujesz znaleźć, to jest number of comibnations.

Patrząc na twoje przykłady, zakładam, że liczba liczb dodajesz jest naprawiony (tj. 4), więc każda liczba jest większa lub równa 1. Możemy tutaj zrobić prostą matematykę - niech odejmą tę liczbę z obu stron równania:

Oryginał: 1) 1 + 1 + 1 + 2 = 5 Wynik odjęcia: 1) 0 + 0 + 0 + 1 = 1

Po zakończeniu odejmowania, twoim problemem jest połączenie z powtórzeniem problem.

Formuły, które można znaleźć w podanym przeze mnie linku, są dość proste. Problem można rozwiązać za pomocą następującego kodu:

#include <iostream>

unsigned factorial(int n)
{
if (n == 1) return 1;
return n * factorial(n-1);
}

unsigned combinationsWithRepetition(int n, int k)
{
return factorial(n + k - 1) / (factorial(k) * factorial(n - 1));
}

unsigned yourProblem(unsigned numberOfNumbers, unsigned result)
{
return combinationsWithRepetition(numberOfNumbers, result - numberOfNumbers);
}

int main()
{
std::cout << yourProblem(4, 5) << std::endl;
std::cout << yourProblem(4, 6) << std::endl;
return 0;
}

Możesz także sprawdzić ten kod w kompilator online.

Pamiętaj, że ten kod obejmuje tylko rozwiązywanie problemów i może zostać ulepszony, jeśli zdecydujesz się go użyć (tzn. Nie jest chroniony przed nieprawidłowymi wartościami).

---