Pawlox Temat założony przez niniejszego użytkownika |
Ilość kombinacji/funkcja rekurencyjna » 2009-04-05 14:15:40 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. Kiedy już myślałem, że na coś wpadłem, okazywało się, że nie pasuje... |
|
WunM |
» 2009-04-05 15:45:59 Robisz pętle która się wykonuje wtedy gdy pionek nie wychodzi po za plansze a w niej inkrementacja pozycji_x i pozycji_y oraz ilości ruchów. To wcale nie jest trudne. |
|
Pawlox Temat założony przez niniejszego użytkownika |
?? » 2009-04-06 17:12:20 No tak, ale program ma ustalić ile jest możliwych dróg, a nie ile pól przeszedł pionek, np. może iść zygzakiem, lub po prostej na ukos - jest wiele możliwości, a czym większa plansza tym więcej... Gdyby to było takie proste to sam bym na to wpadł ;P |
|
DejaVu |
» 2009-04-06 18:34:48 Tak na oko wydaje mi się, że to coś co napisałem, powinno Ci liczyć to co chcesz (nie testowałem): int policz( int x, int y )
{
if( y < 0 || x < 0 || x >= N ) return 0;
return 1 + policz( x - 1, y - 1 ) + policz( x + 1, y - 1 );
} |
|
Pawlox Temat założony przez niniejszego użytkownika |
... » 2009-04-06 21:19:11 Cieplej, ale niestety ciągle nie to. Jeśli dobrze rozumiem to N oznacza długość boku kwadratu (liczona w polach), ale nie wiem co oblicza ten program, np. dla wartości x=1,y=1 wynik jest zawsze taki sam, niezależnie od N... Chyba wartość N powinna odgrywać ważniejszą rolę w kodzie tej funkcji, bo to wielkość planszy warunkuje iloma drogami pionek może dojść na dół. Nie wiem czy w ogóle napisanie takiego programu jest możliwe, a jeżeli już to chyba będzie to nie lada wyzwanie. Trzeba wpaść na pomysł jaka jest zależność pomiędzy wymiarami planszy, współrzędnymi pola i ilością różnych dróg na dół. Ja na to nie wpadłem, ale mam nadzieję, że ktoś z zacnego grona bardziej doświadczonych coś wymyśli. ;) |
|
DejaVu |
» 2009-04-06 22:00:02 wynik = policz( 5, N - 1 ); |
|
Pawlox Temat założony przez niniejszego użytkownika |
Eureka! » 2009-04-07 17:05:32 Rozwiązałem problem, dziękuję za pomoc. Oto gotowy kod funkcji (może się komuś przyda): 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 ) );
}
Zamiast tego +1 w zwracanej wartości wstawiłem warunek, że jeżeli "pionek" osiągnie dolną granicę to podniesie licznik o 1. Jeszcze raz wielkie dzięki dla Piotra bo sam nie doszedłbym do tego. |
|
| « 1 » |