Verschiedene Möglichkeiten, N als K ganze Zahlen ungleich Null darzustellen

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 von

Erklärung

lautet:

Erklärung

Jetzt 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.

Rekursive Methode

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.

Beispiel

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;
}

Ausgabe

Number of ways to represent 5 as the sum of 2 non-zero integers: 4

Komplexität

Zeitliche Komplexität: O(N ^ K).

Raumkomplexität: O(K)

Binomialkoeffizientenformel

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: −

• Subtrahieren Sie 1 von N, um N-1 zu erhalten.

• Teilen Sie N-1 in K-1 nicht negative ganze Zahlen.

• Fügen Sie 1 zu allen in Schritt 2 erhaltenen K-1 nicht negativen ganzen Zahlen hinzu, um K ganze Zahlen ungleich Null zu erhalten, und ihre Summe ist N.

Der Grund, warum diese Methode funktioniert, besteht darin, dass der kleinstmögliche Wert jedes Summanden 1 ist (da wir möchten, dass es sich um eine Ganzzahl ungleich Null handelt). Deshalb subtrahieren wir 1 von N, um sicherzustellen, dass genügend Einheiten vorhanden sind, die den K Summanden zugewiesen werden können.

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) = 10

Das sagt uns, dass es 10 Möglichkeiten gibt, 6 in 4 ganze Zahlen ungleich Null zu dividieren.

Sie sind −

• 1 + 1 + 1 + 3

• 1 + 1 + 2 + 2

• 1 + 1 + 3 + 1

• 1 + 2 + 1 + 2

• 1 + 2 + 2 + 1

• 1 + 3 + 1 + 1

• 2 + 1 + 1 + 2

• 2 + 1 + 2 + 1

• 2 + 2 + 1 + 1

• 3 + 1 + 1 + 1

Methode

Lassen Sie uns den Schritt-für-Schritt-Algorithmus zur Implementierung der oben genannten Methode besprechen -

• Geben Sie die Werte von N und K in die Hauptfunktion ein.

• Berechnen Sie die Anzahl der Methoden mithilfe der obigen Formel.

• Drucken Sie den Wert variabler Wege aus.

Jetzt schreiben wir etwas Code.

Beispiel

Code-Implementierung mithilfe der Binomialkoeffizientenmethode

#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;
}

Ausgabe

Number of ways to represent 7 as the sum of 2 non-zero integers: 6

Komplexität

Zeitliche Komplexität: O( K).

Raumkomplexität: O(1)

Fazit

In diesem Artikel haben wir versucht, eine Möglichkeit zu erklären, wie man N als Summe von K ganzen Zahlen ungleich Null ausdrücken kann. Ich hoffe, dieser Artikel hat Ihnen geholfen, dieses Konzept besser zu verstehen.

Das 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!