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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
(Hetmany)
(Hetmany)
Linia 435: Linia 435:
 
==Zadanie 6 (Suma składników)==
 
==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:
+
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:<br>
3 = 3
+
3 = 3<br>
3 = 2+1
+
3 = 2+1<br>
 
3 = 1+1+1
 
3 = 1+1+1
Można założyć, że n jest mniejsza lub równa pewnej stałej maxN.
 
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Linia 457: Linia 456:
 
'''Rozwiązanie 1'''  
 
'''Rozwiązanie 1'''  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
 
+
  '''procedure''' Suma(n:integer);
  procedure Suma(n:integer);
 
 
  // 1 <= n
 
  // 1 <= n
 
   
 
   
   procedure rozklad(var T:array[1..n] of integer; ti,k,m:integer)
+
   '''procedure''' rozklad('''var''' T:'''array'''[1..n] '''of''' integer; ti,k,m:integer)
 
   // 0 <= ti <= n
 
   // 0 <= ti <= n
 
   // ti > 0 --> k=T[ti]
 
   // ti > 0 --> k=T[ti]
 
   // 0 <= m
 
   // 0 <= m
 
   // m=0 --> ti > 0
 
   // m=0 --> ti > 0
   var i:integer
+
   '''var''' i:integer
   begin
+
   '''begin'''
     if m=0 then begin
+
     '''if''' m=0 '''then''' '''begin'''
 
       writeln(n,' = ');
 
       writeln(n,' = ');
       for i=1 to ti-1 do write(T[i],'+');
+
       '''for''' i=1 '''to''' ti-1 '''do''' write(T[i],'+');
 
       writeln(T[ti])
 
       writeln(T[ti])
     end         
+
     '''end'''          
     else begin
+
     '''else''' '''begin'''
 
       ti:=ti+1;
 
       ti:=ti+1;
       for i=min(k,m) downto 1 do begin
+
       '''for''' i=min(k,m) '''downto''' 1 '''do''' '''begin'''
 
         T[ti]:=i;
 
         T[ti]:=i;
 
         rozklad(T,ti,i,m-i);
 
         rozklad(T,ti,i,m-i);
       end
+
       '''end'''
     end
+
     '''end'''
   end //rozklad
+
   '''end''' //rozklad
 
   
 
   
  var T:array[1..n] of integer;
+
  '''var''' T:'''array'''[1..n] '''of''' integer;
  begin  
+
  '''begin'''   
 
   rozklad(T,0,n,n);
 
   rozklad(T,0,n,n);
  end // Suma
+
  '''end''' // Suma
  
 
''Koszt czasowy:'' wykładniczy względem n
 
''Koszt czasowy:'' wykładniczy względem n

Wersja z 19:44, 20 lip 2006

To są ćwiczenia z rekurencji.

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

Rozwiązanie 1

Pytanko 1:

Pytanko 2:

Pytanko 3: (trudniejsze)

Odpowiedź:

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ść). Sprawdzić, 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

Rozwiązanie 1

Rozwiązanie 2

Zadanie 3 (Wieże Hanoi z ograniczeniami)

Na wykładzie 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

Rozwiązanie 1

Pytanko 1

Odpowiedź

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

Rozwiązanie 1

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

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

Wskazówka 2

Rozwiązanie 1