OBEB (GCD , ebob )

Yazan : Şadi Evren ŞEKER

Matematiksel olarak iki tam sayının çarpanlarına ayrıldığında, iki tam sayıyı da tam olarak bölen en büyük sayıya verilen isimdir.

Sayılar üzerinden anlatmak gerekirse 60 ve 72 sayıları için 12 hem 60 hem de 72’yi kalansız bölen (tam bölen) en büyük sayıdır.

Bu sayıyı bulmak için iki tam sayı da öncelikle çarpanlarına ayrılır (factorize)

60 = 5 x 3 x 2 x 2

72 = 3 x 3 x 2 x 2 x2

Olarak yazılabilir.

Bu sayılardan ortak olan küme alınırsa iki tane 2 ve bir tane 3 ortaktır:

2 x2 x 3 = 12

Sayısı ortak bölenlerin en büyüğüdür (greatest common divisor).

Yukarıdaki bu yaklaşımı biraz daha iyileştirirsek (bilgisayarlar açısından daha hızlı işlenebilir bir hale sokmaya çalışırsak) Öklit algoritmasını kullanabiliriz.

Öklit, obeb bulurken aşağıdaki yaklaşımla daha kısa adımda bulunabileceğini keşfetmiştir.

Buna göre iki sayı birbirine bölünür ve kalan sayı diğer sayıyı tam bölene kadar bölme işlemi devam eder.

Örneğin yukarıdaki sayılar için ( 60 ve 72) bu işlemi yapacak olursak:

72 % 60 = 12 (72’nin 60’a bölümünden kalan 12’dir)

60%12 = 0 (tam bölünür)

Dolayısıyla sayımızı 12 olarak bulduk.

Bu işlemi bir programlama dili ile kodlamak da aşağıdaki şekilde mümkün olabilir :

#include <stdio.h>

int obeb(int a,int b)

{

   if(b==0)

        return a;

   else

        return obeb(b,a%b);

}

int main()

{

  int n1,n2;

  printf("OBEB bulmak istediginiz iki sayiyi giriniz:");

  scanf("%d %d",&n1,&n2);

  printf(" %d ve %d sayilarinin obeb'i %d 'dir",n1,n2,obeb(n1,n2));

  return 0;

}

Yukarıdaki kodda, özyineli (recursive) bir yaklaşım izlenmiş ve sayıların bölümünden kalan sayının bir sonraki adımda bölen olması sağlanmıştır.