En uzun artan altdizi(LIS) - Dinamik Programlama

Bir dizi içerisinde en uzun artan altdiziyi bulmayı amaçlayan bir problemdir. Örneğin

Input:
    {10, 22, 9, 33, 21, 50, 41, 60, 80}
Output:
    6{10, 22, 33, 50, 60, 80}

LCS algoritmasına benzer bir yol izleyeceğiz. Kod anlaşılır durumda, çözüm aşağıdadır.

def lis(arr):
    lis = [1] * len(arr)

    for i …
more ...

En uzun ortak altdizi(LCS) - Dinamik Programlama

Bilgisayar bilimlerinde önemli bir yere sahip olan bu problemde, verilen iki dizgide de ortak olarak bulunan ve aynı yönde sıralanmış dizgiler bütünü elde edilmeye çalışılmaktadır.

Örneğin;

 “ABCDGH” ve “AEDFHR” için “ADH”
 “AGGTAB” ve “GXTXAYB” için “GTAB”

Dosyalar arasındaki farkları, değişiklikleri elde etmede ve özellikle bioinformatik alanında sıkça karşılaşılan bir çözümdür …

more ...

Sieve of Eratosthenes - Matematik Problemi

Verilen bir n sayısı var ve bu sayıya kadar olan tüm asal sayıların elde edilmesi için sunulmuş en efektif çözümdür (ref: Wiki).

gif

Algoritma şu şekilde çalışır.

  1. 2'den n'e kadar bir liste yaratılır. (2,3,4,5,6...n)
  2. p = 2 yapılarak ilk asal sayı 2 ilan edilir.
  3. 2p,3p,4p …
more ...

Sayının faktoriyelinde sonda bulunan 0'ların sayısı - Matematik Problemi

Verilen sayının faktoriyelinde sonda bulunan sıfırların sayısını bulmamız gerekiyor.

Örneğin;

Input: n = 5
Output: 1
5! = 20

Input: n = 20
Output: 4
20! = 2432902008176640000

Input: n = 100
Output: 24

En basit hali ile çözüm, sayının faktoriyelini hesaplamak ve sondaki sıfıların sayısını saymak. Masraflı ve büyük sayılar için çalışmayacak bir yöntem …

more ...

Hileli parayı hilesiz yapmak - Matematik Problemi

Verilen bir fonksiyon yazı tura işlemini %60 yazı %40 tura gelecek şekilde gerçekleştiriyor. Bu verilen fonksiyonu kullanarak bu işlemi nasıl hilesiz yapabiliriz?

Paranın %60 olasılıkla 0, %40 olasılık ile 1 döndürdüğünü biliyoruz. Çözüm olarak bu fonksiyonu iki kere çağıracağız. Eğer sonuçlar (1,0) veya (0,1) ise problem yok, direk …

more ...


N. basamağa kaç adımda ulaşılabilir? - Dinamik Programlama

N adet basamağa sahip bir merdivende, en alt noktadan üst noktaya her seferinde en fazla bir veya iki adım atarak kaç farklı şekilde ulaşabileceğimizi bulacağız.

basamak Örneğin yadaki resim için 3 adet çözüm vardır.

Daha fazla örnek;

Input: n = 1
Output: 1
Sadece 1 adımda ulaşılır

Input: n = 2
Output: 2 …
more ...

Fibonacci sayısı oluşturma - Matematik Problemi

Fibonacci sayılarını oluşturmanın birden fazla yöntemi vardır.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141, ……..

Fn = Fn-1 + Fn-2

F0 = 0 and F1 = 1.

Metot 1 ( recursion )

Yukarıda verilmiş olan matematik ifadesinin direkt olarak uygulanmış halidir. İşe yarar ama çok fazla maliyetlidir.

T(n) = T(n-1 …

more ...


Suffix Array - String Algoritmaları

Suffix dizisi, verilmiş olarak verilen stringe ait tüm suffixlerin alfabetik olarak sıralanmış halidir. Suffix array eğer elinizde bir suffix tree varsa, bu ağaç üzerinde DFS algoritmasını işletilmesi ile elde edilebilir.

Suffix array veri yapısının, suffix tree'den avantajları, geliştirilmiş bellek performansı ve keşleme özelliğidir.

Önreğin;

"banana" için.

0 banana                          5 a …
more ...