Project Euler 9: Özel Pisagor Üçlüsü

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ı

Ögetay Kayalı

Astronom. Özel ilgi alanı teorik kozmoloji, özellikle Einstein'ın görelilik kuramının modifiye edilmesi (modified gravity) üzerine uğraşıyor. Bunların yanında ender bulduğu zaman aralıklarında kafasına esince programlama, 3B modelleme, makineler, tasarım, fotoğrafçılık, resim ve satranç ile de ilgileniyor.

Ögetay Kayalı 120 makale yazdıÖgetay Kayalı tarafından yazılan tüm makaleleri gör