C Programlama Dili ile Öklid(Euclidean) Algoritması

Gazi Merkez Kütüphanesinde rafların arasında rast geldiğim "ALGORİTMALAR ve OTOMATİK HESAP MAKİNALARI" kitabında karşılaştığım bu algoritmayı c programlama diline dökmek istedim. Türk Matematik Derneğinin yayınladığı bu kitabın içeriği algoritmalar ve lojik problemlerden oluşuyor... 

Bu gönderide başlıktan da belli olduğu gibi kitapta birinci bölümde yer alan Öklid algoritmasını inceleyeceğiz: bu algoritma verilen pozitif iki a ve b tam sayılarının en büyük ortak bölenini bulmak için kullanılır.

EBOB bulmak için ortaokullarda öğretilen hepimizin bildiği bir yöntem var: asal çarpanlara ayırma yöntemi.

Öklid Algoritmasının bu yöntemden farkı iki büyük sayıyla işlem yaparken sonucu daha az işlemle ve daha hızlı verebilmesidir.

Kitaptaki lojik ihtarlar şöyledir:

                İhtar 1. a, b sayı çiftini gözönüne alınız. Bundan sonraki ihtara geçiniz.

                İhtar 2. Gözönündeki iki sayıyı karşılaştırınız(yani birincinin ikinciye eşit, budan büyük veya                        bundan küçük olup olmadığını tayin ediniz). Bundan sonraki ihtara geçiniz.

                İhtar 3. Sayılar eşitse, o takdirde bunların her biri aranan sonuçtur, hesaplama son bulur. Eğer                         eşit değilse bundan sonraki ihtara geçiniz.

                İhtar 4. Birinci sayı ikincisinden küçükse bunları birbiri ile değiştiriniz ve budan sonraki                                 ihtara geçiniz.

                İhtar 5. İkinci sayıyı birinciden çıkarınız ve gözönündeki iki sayı yerine sırayla çıkarmadan                             elde edileni ve kalanı koyunuz. İhtar 2 ye geçiniz

   İhtarlar tekrar iki sayı eşit oluncaya kadar devam eder ve eşit olunca problem çözülür.

 Bu lojik adımları koda dökersek bazı hatalar alacağımı fark ettim (İhtarlar programlama maksadıyla  yazılmadığı için. "kitap 1964 çıkışlı" ) mesela: 36 ve 12 sayısını gözönüne alırsak 36-12=24 ,36%12=0 ihtarları takip ettiğimizde birinci ile ikinci sayılarımız 24 ve 0 oluyor. 24%0 kontrolü yapamayacağımız için başka kontroller de yapmamız gerekiyordu. Bunun  için bu algoritmayı sadece bu kitaptan değil de başka kaynaklardan araştırmaya başladım. Ve algoritmanın çalışma mantığını şöyle olduğunu öğrendim:

tekrar a ve b tam sayılarını ele alalım verilen sayılardan büyüğü küçüğüne bölünür ve kalan hesaplanır.

Eğer kalan sıfır ise küçük olan sayı EBOB'dur ve işlem biter değilse bölüm yerine küçük sayı bölen yerine de  kalan sayı alınır ve işlemler tekrarlanır.

Sözde Programlama kodunu yazarsak: karsılaştırma kolaylığı için ilk büyük sayıyı girdireceğim.

İhtar 1. a ve b tam sayılarını a>b olacak şekilde giriniz

İhtar 2. a yı b ye böl kalana k de

İhtar 3. Eğer k==0 a ve b nin ebobu k yaz ve dur. Değilse devam et 

İhtar 4. a=bölen b=kalan yap 2. ihtara dön

şeklindedir.

Bunu C' programlama dilinde yazarsak:Koda Git(GİT HUB)