SORU: Düzlemde atlayarak gezinme

Pozitif düzlemde ( 0, 0 ) koordinatındasınız ve yapabileceğiniz atlamalar:
( +1, 0 ), ( +2, 0 ), ( +3, 0 ),
( 0, +1 ), ( 0, +2 ), ( 0, +3 ),
( +1, +1 ), ( +2, +2 ),
( +1, +2 ), ( +2, +1 )
olarak verilmiş olsun.

Düzlemde atlayarak gezinme

( +20, +20 ) koordinatına kaç farklı şekilde gidebilirsiniz?

Özyinelemeli bir çözüm aşağıdaki gibi verilebilir.

int r(int x, int y) {
   if(x == 0 && y == 0)
     return 1;
   else if(x < 0 || y < 0)
     return 0;
   return r(x-1, y) + r(x-2, y) + r(x-3, y) + r(x, y-1) + r(x, y-2) + r(x, y-3) + r(x-1, y-1) + r(x-2, y-2) + r(x-1, y-2) + r(x-2, y-1);
}

Algoritmayı dikkatle incelerseniz, problemi oldukça başarılı bir şekilde çözebildiğini göreceksiniz. Yalnız ufak bir problem var: aynı ifadeler tekrar tekrar hesaplandığından r(10, 10)'un çözümünü bulmak bile oldukça uzun sürüyor. Bu durumda, aynı ifadelerin yeniden hesaplanmasını önlemek için kodu aşağıdaki gibi değiştirelim.

__int64 d[50][50] = {0};

__int64 r(int x, int y)
{
   if(x == 0 && y == 0)
     return 1;
   else if(x < 0 || y < 0)
     return 0;
   if(d[x][y] > 0)
     return d[x][y];
       d[x][y] = r(x-1, y) + r(x-2, y) + r(x-3, y) + r(x, y-1) + r(x, y-2) + r(x, y-3) + r(x-1, y-1) + r(x-2, y-2) + r(x-1, y-2) + r(x-2, y-1);
   return d[x][y];
}

Evet, işte şimdi algoritma çok daha hızlı bir şekilde sonuca ulaşabiliyor. Lakin, halen r(20, 20) için çözümü elde edemedik. Çünkü farklı yolların sayısını ifade etmekte _int64 yetersiz kalıyor.

Eğer daha büyük sayılarla çalışırsanız, ekteki değerleri elde edebilirsiniz.


11 yıl 9 ay önce eklendi

İffetli Olun Ki İffet Bulasınız! Nasrettin Hoca'nın En Kısa Fıkraları Altı arkadaşın derenin karşısına geçmeye çalıştığı zeka sorusu Horoz ve Tilki Hikayesi Woodoo (Voodoo) Büyüleri Apocalypse II. Dünya Savaşı Belgeseli, Bölüm 4: Dönüm Noktası Osmanlı Devleti'nde erkekler bayanlara nasıl çıkma teklif ederdi? En çok karıştırılan deyimler ve anlamları Komik Baykuş Resimleri, Funny Owl Pictures Zeki Müren ve Türk Sanat Müziği Akasya Durağı Oyuncuları Şen Yuva Oyuncuları DJ BoBo ve Eski Dans Müzikleri En çok sevilen ve en çok aranan Melodika Notaları SORU: Düzlemde atlayarak gezinme Devlet Bahçeli, Püskevit: Reklamın İyisi Kötüsü Olmaz =) İdeal kadın nasıl olur, ideal kadının tarifi Çocuk eğitimi ve emeklilik İkramiyesi Bulgaristan Hatıraları ve Videolarım
1
2
3
4
5
6