Die std::gcd Funktion in C++

1. Verwenden Sie die Funktion std::gcd, um den größten gemeinsamen Teiler von zwei ganzen Zahlen in C++ zu berechnen
2. Verwenden Sie die Funktion std::lcm, um das kleinste gemeinsame Vielfache von zwei ganzen Zahlen in C++ zu berechnen
3. Verwenden Sie die Funktion std::midpoint, um den Mittelpunkt zweier Zahlen in C++ zu berechnen

Dieser Artikel erklärt, wie Sie std::gcd und andere nützliche mathematische Funktionen aus der STL-Bibliothek für Numerik in C++ verwenden.

Verwenden Sie die Funktion std::gcd, um den größten gemeinsamen Teiler von zwei ganzen Zahlen in C++ zu berechnen

STL bietet mehrere Algorithmen mit dem Header <algorithm>, aber auch leistungsstarke mathematische Funktionen, von denen einige als numerische Algorithmen betrachtet werden können. Diese Funktionen werden über die Kopfzeile - numeric bereitgestellt.

Wir werden die Funktion std::gcd untersuchen, die den größten gemeinsamen Teiler zweier Ganzzahlen berechnet. Ein größter gemeinsamer Teiler ist die größte positive ganze Zahl, die jede der gegebenen ganzen Zahlen teilt.

std::gcd nimmt zwei ganzzahlige Werte (m und n) und gibt den größten gemeinsamen Teiler von |m| und |n| zurück. Wenn sowohl m als auch n null haben, gibt die Funktion ebenfalls null zurück. Der folgende Beispielcode demonstriert die grundlegende Verwendung von std::gcd und gibt die entsprechenden Ergebnisse an die Konsole aus.

#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>

using std::cout;
using std::endl;
using std::setw;
using std::vector;

int main() {
  std::vector<std::pair<int, int>> vec = {
      {12125, 1235}, {124, 1122}, {-1235, 321}, {12, 144}};

  for (const auto &item : vec) {
    cout << "Greatest common divisor of " << setw(5) << item.first << " and "
         << setw(5) << item.second << " is "
         << std::gcd(item.first, item.second) << endl;
  }

  return EXIT_SUCCESS;
}

Ausgabe:

Greatest common divisor of 12125 and  1235 is 5
Greatest common divisor of   124 and  1122 is 2
Greatest common divisor of -1235 and   321 is 1
Greatest common divisor of    12 and   144 is 1

Verwenden Sie die Funktion std::lcm, um das kleinste gemeinsame Vielfache von zwei ganzen Zahlen in C++ zu berechnen

Eine weitere ähnliche Funktion in der Numerik-Bibliothek ist std::lcm, die das kleinste gemeinsame Vielfache von zwei ganzen Zahlen berechnet. Die Funktion akzeptiert zwei ganze Zahlen ähnlich dem std:gcd und gibt das kleinste gemeinsame Vielfache von |m| zurück. und |n| (Bezeichnung der Argumente).

Beachten Sie, dass diese beiden Funktionen den Bezeichner constexpr haben, was bedeutet, dass sie möglicherweise in konstanten Ausdrücken verwendet werden, und die Funktion erhält auch eine inline-Klassifizierung.

#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>

using std::cout;
using std::endl;
using std::setw;
using std::vector;

int main() {
  std::vector<std::pair<int, int>> vec = {
      {12125, 1235}, {124, 1122}, {-1235, 321}, {12, 144}};

  for (const auto &item : vec) {
    cout << "Least common multiple of " << setw(5) << item.first << " and "
         << setw(5) << item.second << " is "
         << std::lcm(item.first, item.second) << endl;
  }

  return EXIT_SUCCESS;
}

Ausgabe:

Least common multiple of 12125 and  1235 is 2994875
Least common multiple of   124 and  1122 is 69564
Least common multiple of -1235 and   321 is 396435
Least common multiple of    12 and   144 is 144

Verwenden Sie die Funktion std::midpoint, um den Mittelpunkt zweier Zahlen in C++ zu berechnen

std::midpoint ist eine fähige Funktion, um die Hälfte von zwei gegebenen Zahlen zu berechnen, ohne dass sich der Benutzer um Überläufe kümmern muss. Wenn wir nämlich versuchen, die Hälfte zweier großer Ganzzahlen zu berechnen, deren Summe größer als die obere Grenze der 64-Bit-Ganzzahl ist, erhalten wir den Überlauf und das Ergebnis wird falsch sein.

Als Beispiel versucht der folgende Codeausschnitt, den Mittelpunkt zweier Ganzzahlen zu finden, wobei eine gleich der maximalen Zahl ist, die in uint64_t gespeichert werden kann, und die andere um zehn kleiner ist. Beachten Sie, dass die Berechnung mit den üblichen arithmetischen Operatoren die falsche Zahl liefert, während std::midpoint das richtige Ergebnis liefert.

Beachten Sie jedoch, dass diese Funktion seit dem C++20-Standard Teil der Sprache ist und in älteren Versionen möglicherweise nicht verfügbar ist. std::midpoint funktioniert auch mit Zeigerwerten, aber die angegebenen Zeiger sollten Elemente desselben Arrays sein. Andernfalls ist das Verhalten undefiniert.

#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>

using std::cout;
using std::endl;
using std::setw;
using std::vector;

int main() {
  uint64_t a = std::numeric_limits<uint64_t>::max();
  uint64_t b = std::numeric_limits<uint64_t>::max() - 10;

  cout << "a: " << a << '\n'
       << "b: " << b << '\n'
       << "Incorrect: " << setw(20) << (a + b) / 2 << '\n'
       << "Correct  : " << setw(20) << std::midpoint(a, b) << endl;

  return EXIT_SUCCESS;
}

Ausgabe:

a: 18446744073709551615
b: 18446744073709551605
Incorrect:  9223372036854775802
Correct  : 18446744073709551610