RSS

Perfect (Golden) Numbers

Mart 04

Mükemmel (Altın) sayılar dün gittiğim bir iş görüşmesinde karşıma çıkan bir mülakat sorusuydu. Görüşmede, verilen sayı mükemmel sayı ise true, değilse false döndüren bir fonksiyon yazmam istenmişti.

Öncelikle mükemmel sayıların ne olduğundan bahsetmek gerekiyor sanırım. Altın sayılar kendisi haricindeki pozitif bölenlerinin toplamı kendisine eşit olan sayılara denir. Örnek vermek gerekirse 6’nın pozitif bölenlerinin (1,2,3) toplamı yine 6 olduğu için 6 bir altın sayıdır. Aynı şekilde 28’in bölenleri (1,2,4,7,14) toplamı da kendisine eşit olduğundan 28’de bir altın sayıdır. Daha detaylı bilgi için Wikipedia: Perfect Number konusunu inceleyebilirsiniz.

Birçok kişi “çok kolay” 1’den o sayıya kadar döner, tam bölenlerin toplamına bakarız diyecektir. Fakat bu method 999.999 gibi bir sayıyı kontrol ediyorsanız fonksiyona 1 milyon döngü yaptırmanız anlamına geliyor. Ben görüşme esnasında 250.000 döngü ile bu sayıyı doğrulayabilecek bir çözüm sundum.

Aşağıda mülakat sırasında aklıma gelmeyen fakat eve giderken “neden daha önce düşünemedim” dediğim bir altın sayı doğrulama yöntemini sizlerle paylaşmak istiyorum.

function is_perfect_number( $sayi )
{
  if ( ( $sayi % 2 ) == 0 )
  {
    $toplam = 3 + ( $sayi / 2 );
    $artis = 1;
  }
  else
  {
    $toplam = 1;
    $artis = 2;
  }

  $karekok = sqrt( $sayi );
  if ( is_int( $karekok ) ) $toplam += $karekok;

  for( $i = 3; $i < $karekok; $i += $artis )
  {
    if ( ( $sayi % $i ) == 0 )
    {
      $toplam += $i + ( $sayi / $i );
      if ( $toplam > $sayi )
        return false;
    }
  } 

  return ( $toplam == $sayi );
}

Yukarıdaki fonksiyon 999.999 için ~500 döngü ile sonucu doğruluyor. Umarım işinize yarar.

 

Posted by on 04 Mart 2010 in PHP, Programlama

3 Comments

3 responses to “Perfect (Golden) Numbers

  1. Mustafa KIRIMLI

    04 Ocak 2011 at 10:01

    Anadolu yakasında bir firma ile yaptığım iş görüşmesinde karşılaştığım bir soruydu 🙂
    Teşekkürler paylaşım için.

     

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir