19.5 C
İstanbul
20 Ekim 2018
Algoritmalar Matematik

Project Euler 2: Çift Fibonacci Sayıları

Soru: Fibonacci dizisindeki her yeni terim, önceki iki terimin toplamıdır. 1 ve 2’den başlanarak ilk 10 terim şu şekildedir:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
Dört milyonu aşmayacak şekilde çift Fibonacci terimlerinin toplamı nedir?

Bu soruyla birlikte algoritma sorularının vazgeçilmezi olan Fibonacci dizisiyle karşılaşıyoruz. Fibonacci dizilerini elde edebileceğiniz birçok algoritma mevcut, mutlaka bunlara göz atmanızı öneririm. Özellikle özyinelemeli (recursive) fonksiyonlar konusunun vazgeçilmez örneklerindendir. Burada oldukça basit bir metodu kullanacağım. Öncelikle Fibonacci dizisini elde edeceğimiz algoritmayı belirleyelim, ardından 4000000‘a kadar olan bu sayılardan hangileri çift onlara bakacağız ve çift olanların toplamının kaç ettiğini bulacağız.

(1)   \begin{equation*} 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ... \end{equation*}

Yapmamız gereken Fibonacci dizisinin temel kuralını uygulayarak sırayla sayı dizisinin elemanlarını elde etmek ve kaba bir yaklaşımla bu sayıların çift olup olmadığını denetlemek, eğer çiftse toplama eklemek olacak. Bunun için üç tane değişken tanımlıyoruz f_1, f_2 ve f_3. Bunlar dizinin ilk üç elemanı olsun. Bu durumda f_3 = f_1 + f_2 olacağı açıktır. Çünkü Fibonacci dizisinde sıradaki terim, önceki iki terimin toplamıdır. Buraya kadar tamam, peki bundan sonrasını nasıl elde edeceğiz?

Sıradaki terim f_2+f_3 olacak. Fakat bunu elimizdeki üç değişkeni kullanarak yapmalıyız, çünkü her seferinde yeni bir değişken tanımlayamayız. Zaten tanımlayabilseydik bile bu çok verimsiz bir yöntem olurdu. Bunun yerine değişkenleri öteleyeceğiz. Yeni sıralamamızdaki ilk terim şu an elimizde olan f_2 olacak, dolayısıyla onu f_1 yapıyoruz. Şu an elimizde bulunan f_3ü ise f_2 yapıyoruz. Böylelikle sayılarımızı birer ötelemiş olduk. Şimdi yapacağımız sıradaki sayıyı belirleme işlemi yine f_1+f_2 olacak, fakat bu değişkenler önceki değişkenler olduğundan aslında eskiye göre yaptığımız işlem f_2+f_3 oldu ki biz de tam olarak bunu istiyorduk.

long f1 = 1, f2 = 1, f3 = 0, top = 0;

while (f3 < 4000000)
    {
        if (f3 % 2 == 0)
            top += f3;

    f3 = f1 + f2;
    f1 = f2;
    f2 = f3;
    }

Böylelikle sonuç: 4613732 olarak bulunur.

Matematiksel Yaklaşım

(2)   \begin{equation*} (f_1) , (f_2) , (f_1+f_2) ,( f_1+2f_2) , (2f_1+3f_2) , (3f_1+5f_2) , (5f_1+8f_2) , (8f_1+13f_2), ... \end{equation*}

Soruda f_1 = 1 ve f_2 = 2 olarak başlamamız isteniyor. (1) no’lu diziye baktığımızda çift sayılarla ilgili bir düzen fark ediyoruz. Her üç sayıda bir çift sayıyla karşılaşıyoruz. Bu durum başlangıç koşullarını göz önüne aldığımızda gayet mantıklı görünüyor. (2) no’lu ifadeyi çiftlik teklik cinsinden tekrar yazalım.

(3)   \begin{equation*} (T), (C), (T+C), (T+2C), (2T+3C), (3T+5C), (5T+8C), (8T+13C), ... \end{equation*}

Burada çift olma durumunu belirleyen faktör T‘nin başına gelen katsayıdır. Çünkü C ne ile çarpılırsa çarpılsın sonuç C olacaktır. Ancak C+C = C olacağından, çiftlik durumunu T‘nin başındaki katsayı belirler. Bu katsayı her üç tekrarda bir çift olmaktadır.

(4)   \begin{equation*} (T), (C), (T), (T), (C), (T), (T), (C), ... \end{equation*}

Böylelikle her sayının tek tek çift olup olmadığını kontrol etmek yerine, her üç seferde bir tekrarlayan elemanlara bakmak yeterli olacaktır.

Ögetay Kayalı

Bize destek olarak daha çok içerik üretmemize katkıda bulunun!

Related posts

Hanoi Kuleleri

Ögetay Kayalı

Project Euler 6: Karelerin Toplam Farkı

Ögetay Kayalı

Project Euler 7: 10001. Asal Sayı

Ögetay Kayalı

Yorum Bırakın