Bilangan jabat tangan, setiap orang hanya berjabat tangan sekali

Andaikan anda berada di perhimpunan sosial. Jika anda hanya berjabat tangan sekali, bolehkah anda mengira berapa banyak jabat tangan yang anda boleh lakukan? Soalan ini mungkin menghiburkan anda. Masalah ini boleh diselesaikan dengan menggunakan kaedah matematik pilihatur dan gabungan. Walau bagaimanapun, operasi matematik boleh memakan masa.

Dalam artikel ini, kita akan membincangkan cara menyelesaikan masalah ini menggunakan C++. Kami akan meneroka pendekatan yang berbeza, termasuk formula matematik, rekursi dan teknik gabungan lain.

Senario input dan output

Andaikan anda mempunyai N bilangan orang dalam perhimpunan Anda ingin mengira bilangan jabat tangan yang mungkin supaya seseorang berjabat tangan sekali sahaja.

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

Menggunakan Formula untuk Berjabat Tangan

Formula untuk mencari bilangan jabat tangan dalam perhimpunan N orang ialah −

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

Setiap orang N akan berjabat tangan dengan (N-1) individu (tidak termasuk orang itu sendiri) dan jabat tangan antara dua individu tidak dikira dua kali.

Sebagai contoh, jika bilangan individu ialah 14. Maka, bilangan jabat tangan ialah

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

Contoh

Dalam contoh di bawah, kami menggunakan formula untuk mengira bilangan jabat tangan. Di sini kami hanya menggunakan pengendali matematik, mengambil sebagai input bilangan orang di parti.

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

Output

Number of handshakes: 45

Gunakan gelung untuk

Di sini, kami mengira bilangan jabat tangan dengan mengulangi daripada 1 kepada ‘N-1’ dan menambah semua nilai.

Contoh

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

Output

Number of handshakes: 45

Gunakan rekursi

Kita boleh menggunakan rekursi untuk mengira bilangan jabat tangan Dengan berbuat demikian, kita membahagikan masalah kepada masalah yang lebih kecil dengan mempertimbangkan satu orang pada satu masa.

Contoh

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

Output

Number of handshakes: 190

Gunakan While Loop

Di sini, kami telah menggunakan gelung sementara dengan kaunter penyusutan untuk mengira bilangan jabat tangan. Gelung bermula dengan jumlah bilangan orang dan kemudian mengurangkan pembilang satu demi satu selepas setiap lelaran.

Contoh

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

Output

Number of handshakes: 120

Gunakan pengaturcaraan dinamik

Di sini, kami telah menggunakan pengaturcaraan dinamik untuk pengiraan

• Inisialisasikan vektor ‘dp’ untuk menyimpan bilangan jabat tangan.

• Lelaran dari 1 hingga N. Dalam setiap lelaran, ia mengisytiharkan bilangan jabat tangan sebagai jumlah jabat tangan sebelumnya dan bilangan individu tolak 1 sekarang.

Contoh

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

Output

Number of handshakes: 210

Nota − Kaedah ini membantu mengelakkan pengiraan berlebihan. Di sini kami menyimpan nilai yang dikira sebelum ini dalam vektor "dp", yang boleh anda akses dan gunakan semula pada bila-bila masa. Ini menjadikan algoritma cekap dan mengurangkan masa pengiraan keseluruhan.

Kesimpulan

Kami telah membincangkan pelbagai cara untuk mengira bilangan jabat tangan yang perlu dilakukan oleh seseorang hanya sekali. Kaedah ini termasuk menggunakan operator matematik untuk pengiraan formula, menggunakan untuk gelung, rekursi, gelung sementara dan pengaturcaraan dinamik. Setiap kaedah ada kelebihannya. Pengaturcaraan dinamik ialah pendekatan yang lebih sistematik dan teratur untuk menyelesaikan masalah. Bergantung pada keperluan khusus anda, anda boleh menggunakan salah satu kaedah.

Atas ialah kandungan terperinci Bilangan jabat tangan, setiap orang hanya berjabat tangan sekali. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!