WDI – zajęcia 3

    1. Co robi funkcja f?
      		def f(a, b):
      			if b == 0:
      				return 0
      			return a + f(a, b - 1)
    2. Co się stanie jeśli w powyższym przykładzie zmienimi znak + na *?
    3. Co zwracają funkcje e i o zdefiniowane poniżej?
      		def e(n):
      		      if n == 0:
      			        return True
      	  	      else:
      				return o(n - 1)
      
      		def o(n):
      			if n == 0:
      				return False
      			else:
      				return e(n - 1)
    4. Co zwracają funkcje take i skip zdefiniowane poniżej?
      		def take(l):
      			if l == []:
      				return []
      			else:
      				return [l[0]] + skip(l[1:])
      		def skip(l):
      			if l == []:
      				return []
      			else:
      				return take(l[1:])
    5. Napisz rekurencyjną funkcję rec_rev(s), która dla zadanego napisu s zwróci odwrócony napis s.
      Hint: Wykorzystaj dodawanie napisów s1+s2 oraz to, że napisy można indeksować podobnie jak listy.
    6. Napisz rekurencyjną funkcję rec_pal(s) zwracającą True, gdy s jest palindromem. W przeciwnym przypadku funkcja zwraca wartość False.
    7. Napisz rekurencyjną funkcję rec_find(v, x), która dla zadanej posortowanej rosnąco listy liczb v zwróci wartość True, gdy element x występuje na liście v. W przeciwnym przypadku funkcja zwraca wartość False. Zakładamy, że lista v jest posortowana rosnąco — nie trzeba tego sprawdzać.
    8. Napisać funkcję merge z wykładu w wersji iteracyjnej.
    9. (★) Zdefinujmy ciąg Fibonacciego w następujący sposób:

      • f(0) = 0, f(1) = f(2) = 1 gdy n <= 2
      • f(n) = f(n-1) + f(n-2) w p.p.

      Wypisz drzewo wywołań rekurencyjnych f(n). Za pomocą znaków | (pipe) połącz wywołania rekurencyjne z wywołującą funkcją (f(n-1) oraz f(n-2) z f(n)), a odgałęzienia do sumowanych wyników zaznacz znakiem + (plus). Przykłady pokazują jak wygląda wyjście dla różnych wartości n.

    10. (★) Podziałem liczby naturalnej n na k części nazywamy ciąg k liczb naturalnych sumujących się do n. Napisz funkcję p(n,k), która dla danej liczby naturalnej n znajdzie liczbę podziałów liczby n na k części.

Leave a Reply

Your email address will not be published. Required fields are marked *