Liczba sposobów sumowania do sumy S z numerami N

Question

Powiedz S = 5 i N = 3 rozwiązania powinny wyglądać - < 0,0,5> < 0,1,4> < 0,2,3 > < 0,3,2> < 5,0,0> < 2,3,0> < 3,2,0> < 1,2,2> itp itd

W ogólnym przypadku, N zagnieżdżone pętle mogą być użyte do rozwiązania problemu. Uruchom N zagnieżdżoną pętlę, wewnątrz nich sprawdź, czy zmienne pętli dodać do S.

Jeśli nie wiemy N z wyprzedzeniem, możemy użyć rozwiązanie rekursywne. Na każdym poziomie uruchom pętlę, zaczynając od 0 do N, a następnie wywołaj samą funkcję ponownie. Kiedy osiągniemy głębokość N, zobaczmy, czy uzyskane liczby sumują się z S.

Jakieś inne rozwiązanie do programowania dynamicznego?

Answer 1

Spróbuj rekurencyjną funkcję:

f(s, n) = 1         if s = 0 
     = 0         if s != 0 and n = 0 
     = sum f(s - i, n - 1) over i in [0, s] otherwise 

Aby skorzystać z dynamicznego programowania można buforować wartość f Po oceniając go i sprawdź, czy wartość już istnieje w pamięci podręcznej przed oceniając go.

Answer 2

Jest zamknięty wzór formularz: dwumianowego (S + n - 1, n)

Te liczby są simplex numery.

Jeśli chcesz je obliczyć, użyj funkcji log gamma lub arbitralnej arytmetycznej precyzji.

Zobacz https://math.stackexchange.com/questions/2455/geometric-proof-of-the-formula-for-simplex-numbers

Answer 3

To rzeczywiście wygląda trochę jak Wieże Hanoi problemu, bez przymusu układania dysków tylko na większych dysków. Masz dyski S, które mogą być w dowolnej kombinacji na wieżach N. Więc to mnie zmusiło do myślenia o tym.

Podejrzewam, że istnieje formuła, którą możemy wydedukować, że nie wymaga programowania rekurencyjnego. Potrzebuję jednak trochę więcej czasu.

Answer 4

To może być obliczona w O(s+n)(lub O(1) jeśli nie przeszkadza to approximation) w następujący sposób:

Wyobraźmy sobie, że mamy ciąg z n-1 X w niej jest i s o tych. Tak więc dla przykładu s = 5, N = 3, jednym z przykładów ciąg będzie

oXooXoo 

Zauważ, że X. podzielić O znajduje się na trzech różnych grup: jedną o długości 1, długość 2, a długość 2. odpowiada Twojemu rozwiązaniu < 1,2,2>. Każdy możliwy ciąg daje nam inne rozwiązanie, licząc liczbę o z rzędu (0 jest możliwe: na przykład XoooooX będzie odpowiadać < 0,5,0>). Więc licząc liczbę możliwych ciągów tego formularza, otrzymujemy odpowiedź na twoje pytanie.

Istnieje s+(n-1) pozycji do wyboru dla s o, więc odpowiedź brzmi Choose(s+n-1, s).

Answer 5

Mam własną formułę do tego. Razem z moim przyjacielem Gio przygotowaliśmy raport na ten temat.Formuła, którą otrzymaliśmy, to [2 raised to (n-1) - 1], gdzie n to liczba, której szukamy.

Spróbujmy.

• Jeśli n jest 1: jego dodatkami są o. Nie ma dwóch lub więcej liczb, które możemy dodać, aby otrzymać 1 (bez 0). Spróbujmy większej liczby.
• Spróbujmy 4. 4 has addends: 1+1+1+1, 1+2+1, 1+1+2, 2+1+1, 1+3, 2+2, 3+1. Jego całkowita liczba to 7. Sprawdźmy za pomocą wzoru. 2 podniesione do (4-1) - 1 = 2 podniesione do (3) - 1 = 8-1 = 7.
• Spróbujemy 15. 2 podniesione do (15-1) - 1 = 2 podniesione do (14) - 1 = 16384 - 1 = 16383. Dlatego istnieje 16383 sposobów dodawania liczb, które będą równe 15.

(Uwaga: składników sumy są liczbami dodatnimi tylko).

(można spróbować innych numerów, by sprawdzić, czy nasza formuła jest poprawna czy nie.)

Answer 6

istnieje stała formuła, aby znaleźć odpowiedź . Jeśli chcesz znaleźć liczbę sposobów na uzyskanie N jako sumę elementów R. Odpowiedź jest zawsze: (N + R-1)!/((R-1)! * (N)!) lub innymi słowy: (N + R-1) C (R-1)