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.

( +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.