Implementacja algorytmu z robotem w C

robot.c

#include <stdio.h>
#include <stdlib.h>

// Mamy robota, który ma przejść daną odległość, możliwe są ruchy o 1, 2 lub 3. Chcemy się dowiedzieć, ile jest kombinacji, w jakich nasz robot może przejść tą odległość.

struct wyniki { // Struktura przechowuje liczbę możliwości dla następnego kroku o
int o; // 1
int t; // 2
int th; // 3
};
typedef struct wyniki wyniki; // Dla ułatwienia pozbędziemy się słowa struct i będziemy używać strukturki jak w C++

int robot(wyniki **A, int i, int n, int k) { // Funkcja rekurencyjna - zwraca liczbę kombinacji dla danego kroku, przyjmuje wskaźnik do tablicy z wynikami, numer kroku i, odległość n i liczbę kroków (1, 2 lub 3) - k
static wyniki *At; // Tutaj włożymy tablicę, żeby się za bardzo nie bawić ze wskaźnikami
At = *A; // Tutaj wyłuskujemy tablicę ze wskaźnika - teraz At staje się naszą przekazaną tablicą A
if(i+k>n) { // Tutaj następny krok wykroczyłby poza odległość, więc następnych możliwości jest 0
return 0;
} else if(i+k==n) { // Tutaj następny krok trafia dokładnie w odległość n - mamy więc jedną możliwość
return 1;
} else { // Jeżeli nie doszliśmy do końca odległości
	if(i+2 <= n) { // Jeżeli istnieje następny element w tablicy tzn. nie szukamy wyniku dla kroku poza odległością
if((At[i+1].o != 0) || (At[i+1].t != 0) || (At[i+1].th != 0)) { // Sprawdzamy, czy nie policzyliśmy wyniku dla tego kroku wcześniej (prog. dynamiczne)
At[i].o += At[i+1].o + At[i+1].t + At[i+1].th; // Jeżeli tak, wstawiamy już wyliczone wartosci do równania i oszczędzamy na wywołaniach rekurencyjnych (prog. dynamiczne)
} else { // Jeżeli nie policzyliśmy jeszcze wyniku
A = &At; // Aktualizujemy międzyfunkcyjny wskaźnik do tablicy z wynikami do aktualnej tablicy
At[i].o += robot(A, i+k, n, 1); // Rekurencyjnie wywołujemy funkcję sprawdzającą dla kolejnego kroku wyniki dla ruchu o 1
}
	}
if(i+3 <= n) { // Analogicznie dla elementu o 2 w przód w tablicy
if(At[i+2].o != 0 || At[i+2].t != 0 || At[i+2].th != 0) { // Analogicznie
At[i].t += At[i+2].o + At[i+2].t + At[i+2].th; // Analogicznie
} else {
A = &At; // Analogicznie	
At[i].t += robot(A, i+k, n, 2); // Analogicznie dla ruchu o 2
}
}
if(i+4 <= n) { // Analogicznie dla elementu o 3 w przód w tablicy
if(At[i+3].o != 0 || At[i+3].t != 0 || At[i+3].th != 0) { // Analogicznie
At[i].th += At[i+3].o + At[i+3].t + At[i+3].th; // Analogicznie
} else {
A = &At; // Analogicznie
At[i].th += robot(A, i+k, n, 3); // Analogicznie dla ruchu o 3
}
}
return At[i].o + At[i].t + At[i].th; // Zwracamy sumę przypadków dla wszystkich możliwości ruchu - o 1, 2 i 3.
}
}

int main(void) {
int n, o, t, th, i; // n - odległość, o, t, th - wyniki dla ruchu początkowego o 1/2/3, i - iterator
wyniki *A; // Tablica wyników
printf("Podaj odleglosc, jaka ma przebyc robot: \n"); // Ładnie prosimy użytkownika, aby wymyślił nam odległość
scanf("%d", &n);
A = (wyniki*)malloc(n*sizeof(wyniki)); // Alokujemy tablicę wyników (dla każdego kroku, a ponieważ kroków może być w najgorszym wypadku n, to tablica musi mieć n elementów, aby zbadać każdy krok i wszystkie możliwości)
if(A == NULL) { // Sprawdzenie poprawności alokacji
	fprintf(stderr, "Błąd alokacji!\n");
	return EXIT_FAILURE;	
}
for(i=0; i<n; i++) { // Inicjalizacja tablicy - wszystkie wartości muszą być zerami, ponieważ później mamy warunki i dodawanie uwzględniające to założenie
A[i].o = 0;
A[i].t = 0;
A[i].th = 0;
}
o = robot(&A, 0, n, 1); // Wywołanie funkcji - dostajemy wynik dla pierwszego kroku o 1
t = robot(&A, 0, n, 2); // Wywołanie funkcji - dostajemy wynik dla pierwszego kroku o 2
th = robot(&A, 0, n, 3); // Wywołanie funkcji - dostajemy wynik dla pierwszego kroku o 3
// Co do powyższych wywołań - A przekazujemy przez wskaźnik, gdyż zmienia się ona w trakcie rekurencji. i jest 0, bo chcemy, aby robot szedł nam od początku. Odległość to n. Ostatnia liczba to liczba kroków (1, 2, 3).
printf("Robot moze pokonac ta odleglosc na %d sposobow\n", o+t+th); // Wypisujemy wynik - sumę wyników dla wszystkich 3 przypadków.
free(A); // Zwolnienie pamięci, a jakże!
return EXIT_SUCCESS; // Koniec roboty!
}