0 00
Farklı algoritma yöntemleri kullanarak kuvvet fonksiyonunu (x üzeri n) veren kod nasıl yazılır?

Basit döngüsel yaklaşım, özyineleme, parçala ve fethet, dinamik programlama algoritma yöntemleri ile kuvvet fonksiyonu (x üzeri n) kodu.

Problem
Verilen iki tam sayıyı kullanarak, ilk girdi taban ve ikinci girdi üst olmak üzere kuvvet fonksiyonunu veren kodu yazınız.
 
f(x,n) = xn

İteratif yöntem
İteratif yöntem döngülerin kullanıldığı tekrara dayanan en basit yaklaşımdır. while ve for döngüleriyle yazılmış kod aşağıda verilmiştir. Bu yöntemde taban değeri x, kuvvet n kadar kensidiyle (x ile x) çarpılmıştır. Artan çarpım değerleri başlangıç değeri 1 olan ve sonucun tutulduğu res değişkeninde saklanmıştır.
 
function pow(x,n)
{
    var res = 1;
    while (n--) res *= x;
return res;
}

function pow(x,n)
{
   var res = 1;
   for(var i=1; i <=n ; i++) res = res * x;
return res;
}

Özyineleme
Özyineleme (recursive) yaklaşımında pow(x,n)'nin x * pow(x,n-1) olduğu gerçeğine dayanır. Yani x çarpı x'in n-1 kere kendisiyle çarpımından elde edilen sonuç, xn'ye eşittir.
 
pow(x,n) = x*x*x..*x (n tane)
pow(x,n) = x * x*x..*x (n-1 tane)

Fonksiyonun girişinde n'nin 0 ve 1 için özel durumlarının ayrıca ele alındığına dikkat ediniz.
 
function pow(x,n)
{
    if (n == 0) return 1;
    if (n == 1) return x;
    return x * pow(x,n-1);
}

Parçala ve fethet
Parçala ve fethet yaklaşımında problemin çok dallı özyineleme yöntemiyle çözüldüğüne dikkat ediniz.
 
x10
x5*x5
x*x2*x2
x*x1*x1*x1*x1
 
function pow(x,n)
{
     if(n==0) return 1;
    
     if (n%2 ==0)
         return pow(x,(n/2))*pow(x,(n/2));
     else
          return x*pow(x,(n/2))*pow(x,(n/2));
}

Not
n bir tam sayıdır ve n/2 değerinin de bir tam sayı olması için n/2'nin ondalıklı olduğu durumlarda n/2'nin tam sayı kısmı kullanılmalıdır. Bunun için n, fonksiyonda tam sayı olarak tanımlanmalı (int n) yada tam sayıya (parseInt(n/2) gibi) yuvarlanmalıdır.

Dinamik programlama
Dinamik programlama yaklaşımında yapılan hesaplamalar bir temp değişkeninde saklanmıştır. Parçala ve fethet ile dinamik programlama arasındaki fark için tıklayınız.
 
function pow(x,n)
{
    var temp;
    if(n == 0) return 1;
    temp = pow(x, (n/2));
    
    if (n%2 == 0) return temp*temp;
    else return x*temp*temp;
}

n/2'nin tam sayı olduğuna dair yukarıda verilen nota dikkat ediniz.
Bu alana not ekleyebilirsiniz.
Başka bir sorunuz mu var?
Yorumlar (0)

Henüz yorum yapılmamış.

İlgili Konu
Algoritma Örnekleri
İlgili Kayıtlar
İlginizi Çekebilir