Ilość kombinacji - funkcja rekurencyjna

Witam!
Mam następujący problem - muszę napisać program wyświetlający ilość możliwych dróg pionka w warcabach (ruch tylko o po ukosie) z podanego pola (np. wiersz 1,kolumna 3) na ostatnie dolne pole (z ostatniego wiersza) kwadratowej planszy o wymiarze n. Program musi się opierać na funkcji rekurencyjnej. Nie proszę o cały kod programu, ale o pomysł jak to można obliczać i jakieś sugestie. Myślałem nad tym wczoraj kilka godzin i nic [glowa] Kiedy już myślałem, że na coś wpadłem, okazywało się, że nie pasuje [???] ...

Twoj algorytm w ogolnym zarysie powinien wygladac tak:

1. jestes na jakims polu
2. analizujesz (np w petli) pola, ktore sa o i=1, 2, 3, 4... oddalone od Ciebie na ukos (pamietaj, ze "do gory" masz dwa ukosy) - np. (jesli gora to y=0): [x-1, y-1], [x-2, y-2]...
3. w momencie, gdy dojdziesz do brzegu planszy lub do pola zajetego przez inny pionek, to wywolujesz swoja procedure ponownie a jako parametry przekazujesz wspolrzedne nowego pola

No i oczywiscie musisz sprawdzac, czy juz nie doszedles do "gory", ale to jeden w warunkow sprawdzajacych, czy mozesz "isc dalej po skosie".

Albo ja cię źle zrozumiałem, albo ty mnie. Funkcja ma zwracać ilość możliwych dróg dojścia "do góry". Mam jeden pionek i całą kwadratową planszę o wymiarach n*n pól. Podaję funkcji współrzędne pola, z którego ma wyliczyć ilość różnych dróg jakimi może dojść "na górę".

czypoprawnepole(x,y) ... [test czy podane pole lezy na planszy czy wychodzi poza jej granice]
czygora(x,y) ... [czy pole jest jednym z tych docelowych]
wGoraLewoOd(x,y) ... [oblicza xy pola o 1 oczko od podanego w zadanym kierunku]
wGoraPrawoOd(x,y) ... [oblicza xy pola o 1 oczko od podanego w zadanym kierunku]

policz(x,y)
if( ! czypoprawnepole(x,y))
return 0
if(czygora(x,y))
return 1
return policz( wGoraLewoOd(x,y) ) + policz( wGoraPrawo(x,y) )

• moze jakas banalna optymalizacja korzystajaca z cacheowania wartosci na poszczegolnych juz odwiedzonych polach..

Funkcje wGoraLewoOd(x,y) i wGoraPrawoOd(x,y) mają zwracać dwie wartości (return x,y;)? Podczas kompilacji mam błąd "too few arguments to function `int policz(int, int)'" w miejscu początku funkcji policz.

p o m y ś l

//edit: odpowiedz brzmi: to jest algorytm, nie kod w C++. nie musisz tego tlumaczyc na zywca, bo sie nawet nie da, jak juz zauwazyles. wiec - pomyśl.

Wyszło mi coś takiego (po zmianie drogi pionka z góry na dół) :

int n=5;

bool czypoprawnepole(int x, int y)
{
   if(x<0 || y<0 || x>=n || y>=n)
   {return false;}
   else return true;
}

bool czydol(int x,int y)
{
     if(y=(n-1)) return true;
     else return false;
}

int wDolLewoOd(int x,int y)
{
               x=x-1;
               y=y+1;
               return x,y;
}

int wDolPrawoOd(int x, int y)
{
    x=x+1;
    y=y+1;
    return x,y;
}

int policz(int x,int y)
{
    if(!czypoprawnepole(x,y))
        return 0;
    if(czydol(x,y))
        return 1;
    return policz(wDolLewoOd(x,y)) + policz(wDolPrawoOd(x,y));
}

Jezu, widziałeś kiedyś C++ na oczy?

Widziałem, o co ci chodzi? To są tylko deklaracje funkcji, przecież nie będę zamieszczał całego kodu z nagłówkami i ciałem funkcji, kiedy chodzi mi o sprawdzenie tego... No i nie wiem do kogo się zwracałeś pisząc tego posta...

Widziałeś, widziałeś... uwierzymy na słowo. To bardziej Lisp niż C++ (poważnie) [glowa]

Pawlox napisał(a)

bool czydol(int x,int y)
{
     if(y=(n-1)) return true;
     else return false;
}

'=' to operator przypisania, w efekcie ten kod sprawdza czy n jest równe 1.

Pawlox napisał(a)

int wDolLewoOd(int x,int y)
{
               x=x-1;
               y=y+1;
               return x,y;
}

O, a to już Lisp w czystej postaci. Wyrażenia połączone ',' ewaluowane są od lewej do prawej, wynikiem za jest ostatnia wartość. Funkcja zwraca po prostu y+1. Tego zbędnego przypisania nie komentuję. W C++ nie ma równoległego, wielokrotnego zwracania...

O reszcie słowa nie powiem, uwierzę, że wiedziałeś jak C++ wygląda pisząc to.

Pawlox napisał(a)

No i nie wiem do kogo się zwracałeś pisząc tego posta...

Do Niewidzialnego Różowego Jednorożca...

Ekhm... * od sprawdza czy n nie jest równe 1.

sorry.

Jeśli chodzi o '=' to przyznaję się, że często popełniam ten błąd, ale wiem, że '==' służy do porównania - to tylko pomyłka. return x,y; napisałem właśnie dlatego żeby ktoś mnie poprawił i powiedział jak ma być, bo funkcja policz pobiera 2 argumenty, a wcześniej kolega napisał "policz( wGoraLewoOd(x,y) )" więc funkcja wGoraLewoOd(x,y) powinna zwracać te argumenty, a ja nie wiem jak to uzyskać. Jeśli chodzi o to "No i nie wiem do kogo się zwracałeś pisząc tego posta..." to chodziło mi o "Jezu,(...)" - zdanie wyglądało jakbyś zwracał się do niego ;P

Problem rozwiązany i to tylko jedną funkcją ;P :

int policz(int x,int y)
{
if(x<0 || x>=n || y>=n) return 0;
if (y==(n-1)) w++;
return (policz(x-1,y+1)+policz(x+1,y+1));
}

Mimo to dziękuję za pomoc, zainteresowanie i konstruktywną krytykę.

hmm to zawsze zwroci 0.

Nie chodzi o to co ta funkcja zwraca, tylko o zmienną w. Ale dla ścisłości:

int policz(int x,int y)
{
  if(x<0 || x>=n || y>=n) return 0;
  if (y==(n-1)) w++;
  policz(x-1,y+1)+policz(x+1,y+1);
  return w;
}

Mhm, tylko teraz liczy zupełnie co innego...

Pawlox napisał(a)

Problem rozwiązany i to tylko jedną funkcją ;P

nie wspominajac o tym, ze liczba funkcji jest totalnie nieistotna i bezznaczenia.. to co napisalem, tez moglem zapisac w jednej funkcji, tylko bys wtedy IMHO tego nie zrozumial..