Witam :)
Przerabiam zadania z tego kursu i mam problem z zadaniem o Krokodylach (link).
Rozwiązałem to zadanie przez rekurencję (musiałem rozważyć 7 przypadków w zależności od położenia aktualnego i poprzedniego na przeszkodzie oraz początkowych wartości a oraz b), ale oczywiście dla 3 przypadku przez przeładowanie stosu program się liczy bardzo długo.
Widziałem rozwiązanie z pętlą (link), ale szczerze mówiąc go nie rozumiem.
Czy ktoś mógłbym mi wyjaśnić jak zliczać te drogi przez pętlę? Będę bardzo wdzięczny.
unsigned int noWays(unsigned short int act_width, unsigned int act_height, unsigned short int prev_width, unsigned int prev_height, unsigned short int a, unsigned int b){
if (act_height == b)
return 1;
if (prev_height < act_height){
if (act_width == 0)
return noWays(act_width, act_height + 1, act_width, act_height, a, b) + noWays(act_width + 1, act_height, act_width, act_height, a, b);
else if (act_width == a)
return noWays(act_width - 1, act_height, act_width, act_height, a, b) + noWays(act_width, act_height + 1, act_width, act_height, a, b);
else
return noWays(act_width - 1, act_height, act_width, act_height, a, b) + noWays(act_width, act_height + 1, act_width, act_height, a, b) + noWays(act_width + 1, act_height, act_width, act_height, a, b);
} else {
if (prev_width > act_width){
if (act_width == 0)
return noWays(act_width, act_height + 1, act_width, act_height, a, b);
else
return noWays(act_width - 1, act_height, act_width, act_height, a, b) + noWays(act_width, act_height + 1, act_width, act_height, a, b);
} else {
if (act_width == a)
return noWays(act_width, act_height + 1, act_width, act_height, a, b);
else
return noWays(act_width, act_height + 1, act_width, act_height, a, b) + noWays(act_width + 1, act_height, act_width, act_height, a, b);
}
}
}
int main(){
SetConsoleOutputCP(CP_UTF8);
// Deklaracja zmiennych
unsigned short int p, a;
unsigned int b, w;
p = giveNumberOfObstacles(1, pow(10, 4));
for (int i = 0; i < p; ++i){
a = giveWidth(1, pow(10, 4));
b = giveHeight(1, pow(10, 9));
w = noWays(0, 1, 0, 0, a, b);
cout << "Przeszkodę o wymiarach " << a << "x" << b << " - liczba sposobów na jaką można ją pokonać można pokonać na " << (a + 1) * w << endl;
}
}
(a+1)^(b+1)ale wg mnie to nadal nie poprawne!4x1wynik16