トリッキーコードネット トップへ戻る   C/C++, Java, Perl, PHP, JavaScript, アルゴリズム, ショートコーディング, IOCCCコードの解説, 等々

サイト情報

トリッキーなコード

7行プログラミング

物凄いコード集

アルゴリズム

データ構造

C/C++な話題

コードサンプル

ツール/環境構築

開発ノウハウ 等

ネタ/ジョーク集

おススメ書籍/サイト

サイトTOP >> アルゴリズム >> 最大公約数計算アルゴリズム (C言語)

最大公約数を計算するプログラミング(C言語)

最大公約数を計算するには、「ユークリッドの互除法」というのが有名です。

-----------------------------------------------------------------------------

ex) 280と220の最大公約数を、ユークリッドの互除法を元に計算してみます^^;)

280 ÷ 220 = 1 ... 60  (※ 大きい数(280) ÷ 小さい数(220) = 1 余り 60)
220 ÷  60 = 3 ... 40  (※「前回の割る数」 ÷ 「前回の余り」)
60  ÷  40 = 1 ... 20  (                〃                  )
40  ÷  20 = 2 ...  0  (※ 余りが0になったときの割る数(20)が、最大公約数)

ということで、280と220の最大公約数は20♪

-----------------------------------------------------------------------------



上記のユークリッド互除法をプログラミングしたコードが、こちら↓↓
// ユークリッドの互除法を利用した、最大公約数を求める関数
int gcd(int a, int b)
{
    int c;

    if (a < b) {
        a+=b; b=a-b; a-=b;
    }

    while (b != 0) {
        c = a % b;
        a = b;
        b = c;
    }

    return a;
}
使い方)
 1 : #include <stdio.h>
 2 : #include <stdlib.h>
 3 :
 4 : // ユークリッドの互除法を利用した、最大公約数を求める関数
 5 : int gcd(int a, int b)
 6 : {
 7 :     int c;
 8 :
 9 :     if (a < b) {
10 :         a+=b; b=a-b; a-=b;
11 :     }
12 :
13 :     while (b != 0) {
14 :         c = a % b;
15 :         a = b;
16 :         b = c;
17 :     }
18 :
19 :     return a;
20 : }
21 :
22 : int main(void)
23 : {
24 :     int a, b;
25 :
26 :     puts("2つの自然数を入力して下さい。");
27 :     scanf("%d %d", &a, &b);
28 :
29 :     if (a <= 0 || b <= 0) {
30 :         puts("自然数以外が入力されました。");
31 :         exit(EXIT_FAILURE );
32 :     }
33 :
34 :     printf("%d\n", gcd(a, b));
35 :
36 :     return EXIT_SUCCESS;
37 : }
結果) 最大公約数計算プログラミングの結果 9~11行目では、こちらで紹介した技を使用し、値を入れ替えています。 2行目の stdlib.hは、exit()を使用する為にインクルードしています。 31行目と36行目の EXIT_SUCCESS, EXIST_FAILUREは、stdlib.hの中で定義されている値です。
         このエントリーをはてなブックマークに追加   


作業効率化・ライフハックのオススメ記事




コンピュータ・テクノロジーのオススメ記事





恋愛・人間関係のオススメ記事




※ 当サイトは、トップページからリンクで辿る事の出来るページに限り、リンクフリーです。
※ 当サイトの閲覧/利用によって生じた如何なる損害も、当サイト管理人は責任を負いません。
※ 当サイトの内容を転載される場合は、当サイトへのリンクをお願い致します。