Anzahl der Händeschütteln, jede Person schüttelt nur einmal die Hand

Angenommen, Sie sind bei einem gesellschaftlichen Treffen. Wenn Sie nur einmal die Hand schütteln, können Sie dann berechnen, wie viele Handschläge Sie schaffen? Diese Frage könnte für Sie interessant sein. Dieses Problem kann durch den Einsatz mathematischer Permutations- und Kombinationsmethoden gelöst werden. Allerdings können mathematische Operationen zeitaufwändig sein.

In diesem Artikel besprechen wir, wie man dieses Problem mit C++ löst. Wir werden verschiedene Ansätze untersuchen, darunter mathematische Formeln, Rekursion und andere kombinatorische Techniken.

Eingabe- und Ausgabeszenarien

Angenommen, Sie haben N Personen in einer Versammlung. Sie möchten die Anzahl der möglichen Händeschütteln berechnen, sodass eine Person nur einmal die Hand schüttelt.

Input: N = 16
Output: 120
Input: N = 11
Output: 55

Verwenden der Formel für Händeschütteln

Die Formel zum Ermitteln der Anzahl der Händeschütteln in einer Versammlung von N Personen lautet −

No. of handshakes = N *(N-1) /2

Jede der N Personen schüttelt (N-1) Personen die Hand (mit Ausnahme der Person selbst) und der Händedruck zwischen zwei Personen wird nicht zweimal gezählt.

Wenn zum Beispiel die Anzahl der Personen 14 beträgt, beträgt die Anzahl der Handschläge

Handshakes = 14 * (14 - 1)/ 2
           = 14 * 13 / 2
           = 182/2
           = 91

Beispiel

Im folgenden Beispiel verwenden wir die Formel, um die Anzahl der Handshakes zu berechnen. Hier verwenden wir einfach mathematische Operatoren und nehmen als Eingabe die Anzahl der Personen auf der Party.

#include <iostream>
using namespace std;

int count(int N) {
   // Formula: N * (N-1) / 2
   return (N * (N - 1)) / 2;
}

int main() {
   int totalIndividuals= 10;
   int numHandshakes = count(totalIndividuals);
   std::cout << "Number of handshakes: " << numHandshakes << std::endl;
   return 0;
}

Ausgabe

Number of handshakes: 45

Verwenden Sie eine for-Schleife

Hier zählen wir die Anzahl der Handshakes, indem wir von 1 bis „N-1“ iterieren und alle Werte addieren.

Beispiel

#include <iostream>
using namespace std;

int count(int N) {
   int numHandshakes = 0;

   for (int x = 1; x < N; x++) {
      numHandshakes += x;
   }

   return numHandshakes;
}

int main() {
   int totalIndividuals = 10;
   int numHandshakes = count(totalIndividuals);
   std::cout << "Number of handshakes: " << numHandshakes << std::endl;
   return 0;
}

Ausgabe

Number of handshakes: 45

Rekursion verwenden

Wir können die Anzahl der Handshakes mithilfe der Rekursion berechnen, indem wir das Problem in kleinere Probleme aufteilen, indem wir jeweils eine Person berücksichtigen.

Beispiel

#include <iostream>
using namespace std;

int count(int N) {
   if (N <= 1)
      return 0;
   return (N - 1) + count(N - 1);
}

int main() {
   int totalIndividuals = 20;
   int numHandshakes = count(totalIndividuals);
   std::cout << "Number of handshakes: " << numHandshakes << std::endl;
   return 0;
}

Ausgabe

Number of handshakes: 190

Verwenden Sie While-Schleife

Hier haben wir eine While-Schleife mit einem dekrementierenden Zähler verwendet, um die Anzahl der Handshakes zu zählen. Die Schleife beginnt mit der Gesamtzahl der Personen und verringert dann nach jeder Iteration den Zähler um eins.

Beispiel

#include <iostream>
using namespace std;

int count(int N) {
   int numHandshakes = 0;

   while (N > 1) {
      numHandshakes += N - 1;
      N--;
   }

   return numHandshakes;
}

int main() {
   int totalIndividuals = 16;
   int numHandshakes = count(totalIndividuals);
   std::cout << "Number of handshakes: " << numHandshakes << std::endl;
   return 0;
}

Ausgabe

Number of handshakes: 120

Verwenden Sie dynamische Programmierung

Hier haben wir dynamische Programmierung für die Berechnung verwendet

• Initialisieren Sie einen „dp“-Vektor, um die Anzahl der Handshakes zu speichern.

• Iterieren Sie von 1 bis N. In jeder Iteration wird die Anzahl der Handshakes als Summe der vorherigen Handshakes und der aktuellen Anzahl einzelner minus 1 angegeben.

Beispiel

#include <iostream>
#include <vector>
using namespace std;

int count(int N) {
   std::vector<int> dp(N + 1);
   dp[0] = 0;

   for (int x = 1; x <= N; x++) {
      dp[x] = dp[x - 1] + (x - 1);
   }

   return dp[N];
}

int main() {
   int totalIndividuals = 21;
   int numHandshakes = count(totalIndividuals);
   std::cout << "Number of handshakes: " << numHandshakes << std::endl;
   return 0;
}

Ausgabe

Number of handshakes: 210

Hinweis − Diese Methode hilft, redundante Berechnungen zu vermeiden. Hier speichern wir den zuvor berechneten Wert im „dp“-Vektor, auf den Sie jederzeit zugreifen und ihn wiederverwenden können. Dies macht den Algorithmus effizient und reduziert die Gesamtrechenzeit.

Fazit

Wir haben verschiedene Methoden besprochen, um die Anzahl der Händeschütteln zu zählen, die eine Person nur einmal machen muss. Zu diesen Methoden gehören die Verwendung mathematischer Operatoren für Formelberechnungen, die Verwendung von For-Schleifen, Rekursionen, While-Schleifen und dynamische Programmierung. Jede Methode hat ihre Vorteile. Dynamische Programmierung ist ein systematischerer und organisierterer Ansatz zur Problemlösung. Abhängig von Ihren spezifischen Anforderungen können Sie beide Methoden verwenden.

Das obige ist der detaillierte Inhalt vonAnzahl der Händeschütteln, jede Person schüttelt nur einmal die Hand. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!