Wie schreibe ich einen Algorithmus, um die Gesamtzahl der Muster der Summe zweier Zahlen zu finden?

Question

Angenommen n = 3 Unter Verwendung der Zahlen 1 und 2 wären die Kombinationen, um die Summe n zu erhalten, [1,2], [2,1], [1,1,1]. 3 Kombinationen.

Wenn n = 2 , dann wären die Kombinationen, um die Summe n zu erhalten, [1,1] und [2]. 2 Kombinationen.

Wie schreibe ich einen Algorithmus, um die Anzahl der Kombinationen von 1 und 2 zu berechnen, um die Summe auf n zu bekommen?

Answer 1

Was Sie beschreiben, scheint die Coin-Change Problem in der dynamic-programming Kategorie zu sein. Sie können diese Links überprüfen unten, um ein besseres Verständnis davon zu gewinnen -

Coin Change Problem - GeeksForGeeks
Coin Change Problem - Algorithmist

Da nur einen Link nicht akzeptabel ist, ich hier einige des Link Inhalts bin Entsendung Ihnen eine Idee zu geben, -

ein Wert N gegeben, wenn wir für N Cent machen ändern wollen, und wir haben unendlich Versorgung von jedem
S = {S1, S2, .., Sm} bewertet Münzen,
, wie viele Möglichkeiten können wir die Veränderung vornehmen?

Die Reihenfolge der Münzen spielt keine Rolle. B. für N = 4 und S = {1,2,3},
gibt es vier Lösungen: {1,1,1,1}, {1,1,2}, {2, 2}, {1,3}. Also Ausgabe sollte 4.

Für N = 10 und S = {2, 5, 3, 6}, gibt es fünf Lösungen: {2,2,2,2,2}, {2,2 , 3,3}, {2,2,6}, {2,3,5} und {5,5}.
So sollte die Ausgabe 5.

Optimal Unterbau

zählen Gesamtzahl Lösungen, wir alle gesetzten Lösungen in zwei Gruppen aufteilen.
1) Lösungen, die keine mth Münze (oder Sm) enthalten. 2) Lösungen, die mindestens ein Sm enthalten.
Let count (S [], m, n) die Funktion die Anzahl von Lösungen zu zählen,
dann kann es als Summe der count (S [], m-1, n) und Zahl geschrieben werden (S [], m, n-Sm).

Daher hat das Problem eine optimale Unterstruktureigenschaft, da das Problem mit Lösungen zu Teilproblemen gelöst werden kann.

Overlapping Subprobleme

Es folgt eine einfache rekursive Implementierung der Münze ändern Problem. Die Implementierung folgt einfach der oben erwähnten rekursiven Struktur.

// Returns the count of ways we can sum S[0...m-1] coins to get sum n 
int count(int S[], int m, int n) 
{ 
    // If n is 0 then there is 1 solution (do not include any coin) 
    if (n == 0) 
     return 1; 

    // If n is less than 0 then no solution exists 
    if (n < 0) 
     return 0; 

    // If there are no coins and n is greater than 0, then no solution exist 
    if (m <=0 && n >= 1) 
     return 0; 

    // count is sum of solutions (i) including S[m-1] (ii) excluding S[m-1] 
    return count(S, m - 1, n) + count(S, m, n-S[m-1]); 
} 

Wenn Sie denken und trocken den obigen Code ausführen, sollten Sie in der Lage sein, die Grundidee zu verstehen. Ich hoffe, das löst dein Problem.

Die obige Erklärung:
Höflichkeit - GeeksforGeeks

Answer 2

Dieses Problem kann in der Mathematik gelöst werden. Die Gleichung ist eine Summe von (nr) Cr mit r = 0,1,2, ..., n/2 für alle n> 0

Beachten Sie, dass diese Gleichung weiter verallgemeinert werden kann für n> 0 und setzen Sie {1 , nur x}. Andere als diese, sollten Sie bei der von @RahulNori bereitgestellt Idee aussehen

---

n = 4

[1,1,1,1] - 1 combination (4C0) 
[2,1,1], [1,2,1], [1,1,2] - 3 combination (3C1) 
[2,2] - 1 combination (2C2) 

---

n = 5

[1,1,1,1,1] - 1 combination (5C0) 
[2,1,1,1], [1,2,1,1], [1,1,2,1], [1,1,1,2] - 4 combination (4C1) 
[2,2,1], [2,1,2], [1,2,2] - 3 combination (3C2) 

---

n = 6

[1,1,1,1,1,1] - 1 combination (6C0) 
[2,1,1,1,1], [1,2,1,1,1], [1,1,2,1,1], [1,1,1,2,1], [1,1,1,1,2] - 5 combination (5C1) 
[2,2,1,1], [2,1,2,1], [1,2,2,1], [2,1,1,2], [1,2,1,2], [1,1,2,2] - 6 combination (4C2) 
[2,2,2] - 1 combination (3C3)