Pisagor üçlüsü; a<b<c için, üç doğal sayıdan oluşur ve a2+b2=c2 eşitliğini sağlar. Örneğin 32+42=52‘dir. a+b+c=1000 koşulunu sağlayan, yalnızca bir Pisagor üçlüsü bulunmaktadır. Bu durumda, abc çarpımı nedir?
Project Euler 9 problemine ilk bakışta, akla gelen kaba yaklaşım, üç adet döngüyü iç içe kullanarak, değerin uygunluğunu kontrol etmektir. Fakat her biri için kabaca 1000 tekrar demek, 1 milyar kontrol işlemi yapmak demek. Bu sebeple iç içe döngülerden olabildiğince kaçınıyoruz.
Analitik Yaklaşım
Eğer elde bir denklem varsa, bununla ilgili analitik çözümleri araştırmak mantıklı olacaktır. Şanslıyız ki, elimizdeki denklem en çok bilinen denklemlerden biri olmasının yanısıra, oldukça da kolay bir denklem. Basit bir yaklaşım uygulayarak, problemi iki bilinmeyene indirgemek mümkün. Bildiklerimiz;
a+b+c=1000 a2+b2=c2
olduğuna göre, c için c=1000-a-b yazabiliriz. İkinci denklemde bunu yerine yazarsak, (1000-a-b)2 gibi bir ifade gelir. Bunları birbirine eşitleyip çözdüğümüzde;
a2+b2=(1000-a-b)2 a2+b2=a2+2ab-2000a+b2-2000b+1000000 500000+ab-1000a-1000b=0
denklemini elde ediyoruz. Problem oldukça basite indirgendi, en azından bir döngüden kurtardık. Basit bir sadeleştirme işlemiyle, ifadeyi 1000’e bölersek 500+(ab/1000)-a-b=0 eşitliğini elde ediyoruz. Aradığımız sayılar tam sayılar olduğu için, burada ab/1000 ifadesi hoş bir mesaj veriyor. Buradaki ab çarpımı, sonda en az üç sıfır barındırmalı. Bu da olası olarak basit bir bakış açısıyla, a’nın (veya b’nin) 100, 200, 300… gibi bir sayı olma ihtimalini kuvvetlendiriyor. Yine de bu değerlendirmeyi çözümün dışarısında tutacağım.
C# Çözümü
Sayının bulunup bulunmadığını denetlemek için, basit bir bool değişken tanımladım. 500 değerini ise içgüdüsel bir şekilde işlem kolaylığı tanımak adına seçtim. Sorular şu anda basit olduğu için, bu tipte ufak kaçamaklar yapmak, eğer başlangıç aşamasındaysanız sizi sıkılmaktan kurtaracaktır. O yüzden detaylara, zamanla zaten gireceğimiz için, şimdiden fazla boğulmama taraftarıyım.
// 1000a + 1000b - ab = 500000 bool bulunma = false; int a = 0, b = 0; for (a = 0; a < 500; a++) { for (b = 0; b < 500; b++) { if (1000 * a + 1000 * b - a * b == 500000) { bulunma = true; break; } } if (bulunma) break; }
Böylelikle sezgilerimizle uyumlu olarak a=200, b=375 ve c=425 olarak bulunur. Dolayısıyla abc çarpımı 31875000 eder.
Ögetay Kayalı