Tag Archives: öklid algoritması

Öklid Algoritması ile En Büyük Ortak Bölen Nasıl Bulunur?

Öklid Algoritması ile en büyük ortak bölenin (ebob) nasıl bulunabileceğini hem iteratif, hem de rekürsif yolla anlatmaya çalıştım bu videoda.

► Öklid Algoritması: https://tr.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm

İki A ve B tam sayısının Ortak Bölenlerinin En Büyüğünün (OBEB), A ve B’yi bölen en büyük tam sayı olduğunu hatırlayalım.

Öklid Algoritması, iki tam sayının OBEB’ini hızlıca bulmak için kullanılan bir yöntemdir.

OBEB(A,B)’nin bulunması için Öklid Algoritması şu şekildedir:

► Eğer A=0 ise, OBEB(0,B)=B olacağı için OBEB(A,B)=B olur ve bu noktada durabiliriz.

► Eğer B=0 ise, OBEB(A,0)=A olacağı için OBEB(A,B)=A olur ve bu noktada durabiliriz.

► A sayısını bölüm ve kalan formunda yazın (A=B⋅Q+R)

►OBEB(A,B)=OBEB(B,R) olduğu için, OBEB(B,R)’yi Öklid Algoritmasını kullanarak bulun

► Ortak bölen nedir? https://tr.wikipedia.org/wiki/Ortak_b%C3%B6len

Matematikte, sıfır olmayan iki veya daha fazla pozitif tam sayının en büyük ortak böleni, tam sayıların hepsini de bölen en büyük pozitif tam sayıdır. Örneğin; 8 ve 12’nin ebob’u 4’tür.

En büyük ortak bölen aynı zaman da en büyük ortak faktör (ebof), en yüksek ortak faktör (eyof) ile de isimlendirilir.

        /// <summary>
        /// En büyük ortak böleni bulmak
        /// </summary>
        static int GreatestCommonDivisor(int a, int b)
        {
            while(a != 0 || b != 0)
            {
                if(a > b)
                {
                    a %= b;
                }
                else
                {
                    b %= a;
                }
            }

            return a | b;
        }

        /// <summary>
        /// En büyük ortak bölüne rekürsif yolla bulmak
        /// </summary>
        static int GcdRecursive(int a, int b)
        {
            if(b == 0)
            {
                return a;
            }
            else
            {
                return GcdRecursive(b, a % b);
            }
        }