Die Frage „Verschiedene Möglichkeiten, N als K ganze Zahlen ungleich Null darzustellen“ findet in vielen realen Anwendungsfällen Anwendung.
Kryptographie – In der Kryptographie werden bestimmte Verschlüsselungsmethoden entwickelt, die das Konzept nutzen, eine Zahl N als Summe von K ganzen Zahlen ungleich Null zu kodieren.
Die Darstellung einer ganzen Zahl N als Summe von K ganzen Zahlen ungleich Null kann in Teilproblemen verschiedener Optimierungsprobleme der Optimierungsmethode auftreten.
Maschinelles Lernen− Beim maschinellen Lernen können Merkmalsvektoren erstellt werden, die die Verteilung von Datenpunkten beschreiben, indem das Problem der Darstellung einer ganzen Zahl N als Summe von K ganzen Zahlen ungleich Null verwendet wird.
Die chinesische Übersetzung vonJetzt entschlüsseln wir das Problem.
Angenommen, wir haben zwei positive ganze Zahlen N und K, wir müssen K ganze Zahlen ungleich Null finden, deren Summe gleich N ist. Wenn beispielsweise N=10 und K=3, müssen wir drei ganze Zahlen ungleich Null finden, deren Summe 10 beträgt. Mögliche Lösungen sind in diesem Fall −
1 + 4 + 5 2 + 3 + 5 2 + 4 + 4
Beachten Sie, dass wir in diesen Lösungen K=3 ganze Zahlen ungleich Null haben, die sich zu N=10 addieren.
Es gibt verschiedene Möglichkeiten, dieses Problem zu lösen. Lassen Sie uns jede einzelne besprechen.
Verwenden Sie einen schrittweisen Algorithmus der rekursiven Methode, um verschiedene Möglichkeiten zur Darstellung von N mit K ganzen Zahlen ungleich Null zu finden.
Geben Sie die Werte von N und K in die Hauptfunktion ein.
Erstellen Sie die Funktion f(N, K), die die Gesamtzahl der Möglichkeiten zurückgibt, wie N als K ganze Zahlen ungleich Null ausgedrückt werden kann.
Wenn K = 1, geben Sie 1 zurück, wenn N 0 überschreitet, andernfalls geben Sie 0 zurück. (Basisfall).
Wenn N == 0 oder K > (Grundlage).
Erstellen Sie eine Variablenzählung, um die Ergebnisse zu speichern.
Setzen Sie den Wert der Variablenanzahl auf 0.
Von 1 bis min(N-K+1, N-1) für jede Ganzzahl I
Berechnen Sie f (N-i, K-1) rekursiv.
Fügen Sie das Ergebnis zur Zählung hinzu.
Anzahl der Rücksendungen.
Implementierung des oben genannten Algorithmus
#include <iostream>
using namespace std;
int f(int N, int K) {
if (K == 1) {
return (N > 0) ? 1 : 0; // base case
}
if (N <= 0 || K > N) {
return 0; // base case
}
int count = 0;
for (int i = 1; i <= min(N-K+1, N-1); i++) {
count += f(N-i, K-1);
}
return count;
}
int main() {
int N = 5, K = 2;
int ways = f(N, K);
cout << "Number of ways to represent " << N << " as the sum of " << K << " non-zero integers: " << ways << endl;
return 0;
}
Number of ways to represent 5 as the sum of 2 non-zero integers: 4
Zeitliche Komplexität: O(N ^ K).
Raumkomplexität: O(K)
Mit der Sternen- und Streifen-Kombinationsmethode kann eine Formel dafür ermittelt werden, wie eine positive ganze Zahl N als Summe von K ganzen Zahlen ungleich Null ausgedrückt werden kann.
Stellen Sie sich eine Reihe von N Sternen (*) vor, die N Partitionseinheiten einer bestimmten ganzen Zahl darstellen. Sie können K-1 vertikale Balken (|) verwenden, um die Sterne in K Segmente anzuordnen, die K ganze Zahlen ungleich Null der Partition darstellen.
Nehmen Sie als Beispiel die Division von 10 durch 3 ganze Zahlen ungleich Null. Zur Darstellung dieses Vorgangs können die folgenden Sternchen und Bindestriche verwendet werden −
* * |. * * * |
Der erste Teil dieser Abbildung zeigt die Nummer 2, der zweite Teil zeigt die Nummer 3 und der dritte Teil zeigt die Nummer 5.Die Anzahl der Möglichkeiten, K-1-Balken in einer Reihe von N Sternen anzuordnen, ist gleich der Anzahl der Möglichkeiten, N mit K ganzen Zahlen ungleich Null darzustellen. Um diese Menge zu berechnen, verwenden wir die Formel: $mathrm{C(N:+:K:-:1,:K:-:1)}$.
Gemäß der Binomialkoeffizientenformel $mathrm{C(n,k):=:n!:/(k!*(n-k)!)}$.
Aber in unserem Fall müssen wir die Möglichkeit ausschließen, 0 zu enthalten. Um Divisionen auszuschließen, die 0 als einen der Addenden enthalten, können wir die folgende Methode verwenden: −
Daher erhalten wir die Formel: Wege = C(N-1, K-1)
Angenommen, wir möchten die Anzahl der Möglichkeiten ermitteln, 6 mit 4 ganzen Zahlen ungleich Null darzustellen. Wir können die zuvor abgeleitete Formel verwenden, die −
lautet
C(N-1, K-1) = C(6-1, 4-1) = C(5, 3) = 10Das sagt uns, dass es 10 Möglichkeiten gibt, 6 in 4 ganze Zahlen ungleich Null zu dividieren.
Sie sind −
#include <iostream>
using namespace std;
int binomial(int n, int k) {
int res = 1;
if (k > n - k) {
k = n - k;
}
for (int i = 0; i < k; ++i) {
res *= (n - i);
res /= (i + 1);
}
return res;
}
int main() {
int N = 7, K = 2;
int ways = binomial(N - 1, K - 1);
cout << "Number of ways to represent " << N << " as the sum of " << K << " non-zero integers: " << ways << endl;
return 0;
}
Number of ways to represent 7 as the sum of 2 non-zero integers: 6
Zeitliche Komplexität: O( K).
Raumkomplexität: O(1)
FazitDas obige ist der detaillierte Inhalt vonVerschiedene Möglichkeiten, N als K ganze Zahlen ungleich Null darzustellen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
Was sind die Vor- und Nachteile der Dezentralisierung?
Warum meldet vue.js einen Fehler?
Aktivierungscode für den Vista-Schlüssel
Zu den Kerntechnologien des Big-Data-Analysesystems gehören:
Einführung in die Verwendung der Python-Programmierung
Offizielle Website von OuYi Exchange
drücke irgendeine Taste zum Neustart
Verbunden, aber kein Zugriff auf das Internet möglich
