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.