Nombre de poignées de main, chaque personne ne serre la main qu'une seule fois

Supposons que vous soyez à une réunion sociale. Si vous ne serrez la main qu’une seule fois, pouvez-vous calculer combien de poignées de main vous pouvez faire ? Cette question pourrait vous amuser. Ce problème peut être résolu en utilisant des méthodes mathématiques de permutation et de combinaison. Cependant, les opérations mathématiques peuvent prendre du temps.

Dans cet article, nous verrons comment résoudre ce problème en utilisant C++. Nous explorerons différentes approches, notamment les formules mathématiques, la récursion et d'autres techniques combinatoires.

Scénarios d'entrée et de sortie

Supposons que vous ayez N nombre de personnes dans un rassemblement. Vous souhaitez calculer le nombre de poignées de main possibles de telle sorte qu'une personne ne serre la main qu'une seule fois.

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

Utiliser la formule pour les poignées de main

La formule pour trouver le nombre de poignées de main dans un rassemblement de N personnes est −

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

Chacune des N personnes serrera la main de (N-1) individus (à l'exclusion de la personne elle-même) et les poignées de main entre deux individus ne sont pas comptées deux fois.

Par exemple, si le nombre d'individus est de 14. Alors, le nombre de poignées de main est de

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

Exemple

Dans l'exemple ci-dessous, nous utilisons la formule pour calculer le nombre de poignées de main. Ici, nous utilisons simplement des opérateurs mathématiques, prenant en entrée le nombre de personnes présentes à la fête.

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

Sortie

Number of handshakes: 45

Utilisez une boucle for

Ici, nous comptons le nombre de poignées de main en itérant de 1 à « N-1 » et en additionnant toutes les valeurs.

Exemple

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

Sortie

Number of handshakes: 45

Utiliser la récursion

Nous pouvons utiliser la récursion pour calculer le nombre de poignées de main. Ce faisant, nous divisons le problème en problèmes plus petits en considérant une personne à la fois.

Exemple

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

Sortie

Number of handshakes: 190

Utiliser la boucle While

Ici, nous avons utilisé une boucle while avec un compteur décrémentant pour compter le nombre de poignées de main. La boucle commence par le nombre total de personnes puis décrémente le compteur une à une après chaque itération.

Exemple

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

Sortie

Number of handshakes: 120

Utilisez la programmation dynamique

Ici, nous avons utilisé la programmation dynamique pour le calcul

.

• Initialisez un vecteur « dp » pour stocker le nombre de poignées de main.

• Itérer de 1 à N. À chaque itération, il déclare le nombre de poignées de main comme la somme des poignées de main précédentes et le nombre actuel d'individus moins 1.

Exemple

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

Sortie

Number of handshakes: 210

Remarque − Cette méthode permet d'éviter les calculs redondants. Ici, nous stockons la valeur précédemment calculée dans le vecteur "dp", auquel vous pouvez accéder et réutiliser à tout moment. Cela rend l’algorithme efficace et réduit le temps de calcul global.

Conclusion

Nous avons discuté de différentes façons de compter le nombre de poignées de main qu’une personne ne doit faire qu’une seule fois. Ces méthodes incluent l'utilisation d'opérateurs mathématiques pour les calculs de formules, l'utilisation de boucles for, de récursivité, de boucles while et de programmation dynamique. Chaque méthode a ses avantages. La programmation dynamique est une approche plus systématique et organisée de la résolution de problèmes. En fonction de vos besoins spécifiques, vous pouvez utiliser l'une ou l'autre méthode.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!