AlgoritmalarMatematik

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ı

Rasyonalist kurucu, editör ve kıdemli yazar. NASA'nın APOD platformunda görevli olmak üzere, Michigan Tech. Üniversitesinde araştırma görevlisi olarak Astrofizik üzerine doktora yapmaktadır. Ege Üni. Astronomi ve Uzay Bilimleri Bölümünden birincilikle mezun olduktan sonra bir yıl kozmoloji üzerine yüksek lisans, ardından bir yıl da İzmir Uluslararası Biyotıp ve Genom Merkezinde Moleküler Biyoloji ve Genetik üzerine yüksek lisans yapmıştır.

Leave a Reply

Your email address will not be published.

Back to top button