25

私は混合数詞クラスを書いているので、すばやく簡単な「最大公約数」関数が必要です。誰かが私にコードまたはコードへのリンクを教えてもらえますか？

4

5 に答える 5

57

libstdc ++アルゴリズムライブラリには隠しgcd関数があります（私はg ++ 4.6.3を使用しています）。

#include <iostream>
#include <algorithm>

int main()
{
  cout << std::__gcd(100,24);
  return 0;
}

どういたしまして ：）

更新：@ chema989が指摘したように、C++17にはヘッダーstd::gcd()付きの関数があります。<numeric>

于 2013-12-18T17:05:28.200 に答える
43

私は投票して締めくくりたいと思っています。実装を見つけるのは難しいとは信じがたいようですが、誰が確かに知っています。

template <typename Number>
Number GCD(Number u, Number v) {
    while (v != 0) {
        Number r = u % v;
        u = v;
        v = r;
    }
    return u;
}

C ++ 17以降では、ただ#include <numeric>使用することができます（gcdに関心がある場合は、追加されstd::gcdたものにも興味がある可能性がかなりあります）。std::lcm

于 2012-06-08T22:10:37.783 に答える
19

クイック再帰バージョン：

unsigned int gcd (unsigned int n1, unsigned int n2) {
    return (n2 == 0) ? n1 : gcd (n2, n1 % n2);
}

または、再帰に激しく反対している場合は、同等の反復バージョン（a）：

unsigned int gcd (unsigned int n1, unsigned int n2) {
    unsigned int tmp;
    while (n2 != 0) {
        tmp = n1;
        n1 = n2;
        n2 = tmp % n2;
    }
    return n1;
}

bignum独自のデータ型、ゼロ比較、割り当て、および係数メソッドに置き換えるだけです（たとえば、クラスなどの非基本型を使用している場合）。

この関数は、実際には画面サイズの積分アスペクト比を計算するための私の以前の回答から来ましたが、元のソースは、私がずっと前に学んだユークリッドアルゴリズムでした。その背後にある数学を知りたい場合は、ウィキペディアで詳しく説明します。

（a）いくつかの再帰的ソリューションの問題は、非常によく考えられていない（擬似コード）など、答えに近づくのが非常に遅いため、そこに到達する前にスタックスペースが不足する傾向があることです。

def sum (a:unsigned, b:unsigned):
    if b == 0: return a
    return sum (a + 1, b - 1)

あなたがsum (1, 1000000000)（しようとして）10億かそこらのスタックフレームを使い果たすようなものでは、それは非常に高価であることがわかります。再帰の理想的なユースケースは、反復ごとに解のスペースを半分に減らす二分探索のようなものです。最大公約数は、ソリューションスペースが急速に減少するため、大量のスタックの使用に対する懸念がそこにないものでもあります。

于 2012-06-08T22:13:51.273 に答える
8

C ++ 17の場合std::gcd、ヘッダーで定義されたものを使用でき<numeric>ます。

auto res = std::gcd(10, 20);
于 2017-04-28T23:54:53.117 に答える
6

ユークリッドの互除法はCで書くのはとても簡単です。

int gcd(int a, int b) {
  while (b != 0)  {
    int t = b;
    b = a % b;
    a = t;
  }
  return a;
}
于 2012-06-08T22:16:25.873 に答える