Wstęp do programowania/Rekursja/Ćwiczenia: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
Linia 277: Linia 277:
 
     '''end'''
 
     '''end'''
 
     '''else'''
 
     '''else'''
       CzyDaSie:=false
+
       CzyDaSie:=true
 
   '''end''' // CzyDaSie     
 
   '''end''' // CzyDaSie     
 
   
 
   

Wersja z 13:25, 1 wrz 2009

To są zadania na rekursję.

Oglądaj wskazówki i rozwiązania __SHOWALL__
Ukryj wskazówki i rozwiązania __HIDEALL__


Zadanie 1 (Labirynt)

Czy istnieje ścieżka miedzy wskazanymi punktami (i1,j1) i (i2,j2) w labiryncie reprezentowanym przez prostokątną tablicę liczb całkowitych o rozmiarze M×N, zawierającą zera (ściana) i jedynki (droga)? Zakładamy, że nie można przechodzić z pola na pole po skosie (np. z (2,5) na (3,6)), a tylko w czterech podstawowych kierunkach (np. z (2,5) na (3,5), (2,4) itd.)

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

Ćwiczenie 1

{{{3}}}

Ćwiczenie 2

{{{3}}}

Ćwiczenie 3

{{{3}}}

Odpowiedź

{{{2}}}

Dla ciekawskich:

Zadanie 2 (Z górki na pazurki)

W tablicy liczb całkowitych o rozmiarze M×N zapisana jest mapa gór (każdy punkt ma podaną dodatnią wysokość). Sprawdź, czy da się przejść z punktu startowego (i1,j1) do docelowego (i2,j2) idąc:

  • tylko w dół lub po płaskim
  • tylko w dół

Tak jak w poprzednim zadaniu poruszać się można tylko w czterech kierunkach podstawowych, nie po przekątnej.

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

Rozwiązanie 2

{{{3}}}

Zadanie 3 (Wieże Hanoi z ograniczeniami)

Na wykładzie omawiane były wieże Hanoi. Ciekawa modyfikacja tego zadania polega na zabronieniu ruchów pomiędzy niektórymi pałeczkami, np. z pierwszej na drugą. Zapisać procedurę realizującą to zadanie przy zabronionych niektórych ruchach.

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

Ćwiczenie 1

{{{3}}}

Odpowiedź

{{{2}}}

Zadanie 4 (Ustawianie hetmanów)

Napisz procedurę znajdująca wszystkie takie rozstawienia 8 hetmanów na szachownicy, by żadne dwa hetmany się nie atakowały.

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

Zadanie 5 (Mnożenie wielomianów)

Dane są dwie tablice (array[0..N-1] of real) reprezentujące dwa wielomiany stopnia N-1. Należy obliczyć iloczyn tych wielomianów metodą dziel-i-zwyciężaj. Zakładamy, że N jest potęgą dwójki.

Wskazówka 1

{{{3}}}

Zadanie 6 (Suma składników)

Napisz procedurę, która wypisze dla zadanej liczby n jej wszystkie rozkłady na sumy nieujemnych liczb naturalnych większych od 1 ustawionych w kolejności nierosnącej. Np. dla n = 3:
3 = 3
3 = 2+1
3 = 1+1+1

Wskazówka 1

{{{3}}}

Wskazówka 2

{{{3}}}

Rozwiązanie 1

{{{3}}}