Merhabalar değerli e-bergi okurları! Bu sayıda sizlere başlıktan da görebildiğiniz üzere Project Euler'den bahsedeceğim.
Project Euler, 2001 yılında Colin Hughes tarafından yaratılmış bir web sitesi. Adını Leonhard Euler'den alan bu site, 500'den fazla (bu yazının yazıldığı tarihte 518) bilgisayarla çözülebilecek matematiksel problem içermekte. Yazlar hariç her hafta sonu siteye yeni bir problem eklenmekte.
“Bilgisayarla çözülebilecek matematiksel problem” terimini biraz açalım. Matematikle ilişkili, genellikle matematiksel terim kullanılan, bazen bazı teoremlere (kosinüs teoremi vb.) ihtiyaç duyulan (soruda genellikle veriliyor) problemler bunlar. Ama genellikle elle de çözülemiyorlar, çözülse bile ciddi vakit alıyorlar. Bu yüzden bir bilgisayara programlama vasıtasıyla çözdürülmesi gerekiyorlar. “4 milyonu geçmeyen çift Fibonacci sayılarının toplamı kaçtır?”, “600851475143 sayısının en büyük asal çarpanı kaçtır?”, “3 basamaklı iki sayının çarpımının sonucu olan en çok basamaklı palindrom sayı kaçtır?” gibi sorular bu problemlere hızlıca verilebilecek bir kaç örnek.
Bir problemi beraber inceleyelim: “3'ün veya 5'in 1000'den küçük tüm katlarının toplamı kaçtır?” Evet, tahmin edebileceğiniz üzere bu sitedeki ilk problem.
Problemi kendiniz çözmek istiyorsanız burdan sonrasını çözmeyi denedikten sonra okuyun.
Problemin çözümü için akla gelecek ilk yöntem çok basit, 1'den başlayarak 1000'den küçük her sayıyı kontrol etmek, eğer sayı 3'ün veya 5'in katıysa onu genel toplama eklemek, yani kaba kuvvet (brute force) kullanmak. Bu çözümü çok az daha verimli hale getirmek için kaba kuvvete 3'ten de başlanabilir, sonuçta 1 ve 2'nin 3'ün de 5'in de katı olmadığı çok açık. Bu algoritmayı Python'da koda dökelim:
toplam = 0 for sayi in range(3,1000): if sayi % 3 == 0 or sayi % 5 == 0: toplam += sayi print toplam
Daha iyi bir çözüm bulunabilir miydi? Matematikle arası biraz olsun iyi olan okurlarımız, muhtemelen basit çözümü en başından beri fark ettiler. Düşünelim, 1000'e kadar 3'ün veya 5'in katı olan sayıların toplamını nasıl buluruz? Önce 3'ün katlarının toplamıyla başlayalım. 3'ten 999'a kadar olan 3'ün katlarının toplamı şu: 3 + 6 + …... + 999. Bu da şuna eşit: 3(1 + 2 ….... + 333). Yani 1'den 333'e kadar olan sayıların toplamının 3 katı. 1'den n'e kadar olan sayıların formülü matematik derslerinden hatırlarsanız n(n+1)/2'ydi. 1'den 333'e kadar olan sayıların toplamı ise 333x334/2. 3'ün katlarının toplamı ise 3x333x334/2. Aynı mantığı 5'in katları için kurarsak (5'ten 995'e kadar) 5'in katlarının toplamının 5x199x200/2 olduğunu görürüz. Bunları toplayınca çıkan sonuç ilk çözümün sonucundan fazla çıkıyor. Bunun sebebi ise 15'in katlarının hem 3'ün hem 5'in katları olması sebebiyle iki toplamda da yer alması. O yüzden bu iki toplamın toplamından 15'in katlarını çıkarmamız gerekiyor, 15'in katlarının toplamı da (15'ten 990'a) 15x66x67/2 yapıyor. Esas sonucumuz da böylece ortaya çıkıyor: 3x333x334/2 + 5x199x200/2 – 15x66x67/2.
Sitede bulunan problemlerin tarzı genel olarak böyle. Sitenin genel yapısına bakacak olursak, site olması gerektiği gibi, sade. Archives bölümünde tüm sorular, Recent bölümünde son sorular, News'ta siteyle ilgili haberler bulunuyor. Eğer üye olmazsanız soruları sadece görebiliyorsunuz. Üye olduğunuzda ise soruları çözdükten sonra cevapları girerek soruları çözülmüş olarak işaretleyebilir, soruyla ilgili forumda insanların paylaştığı çözümleri görebilir, siz de çözümünüzü paylaşabilirsiniz. Bunların dışında Progress sayfasında gelişiminizi çözdüğünüz sorular ve kazandığınız rozetler vasıtasıyla görebilirsiniz. Friends bölümünden arkadaşlarınızı görebilir, arkadaşlarınızla Friend Key'inizi paylaşabilir, siz de onların Friend Key'lerini ekleyerek onların gelişimlerini takip edebilirsiniz.
Benim Friend Key'im : 662352_3de027b902dc8520d23e1c317a3c07ec
Project Euler kullanın, kullandırın. Başka bir sayıda görüşmek üzere, hoşca kalın!