Month: October 2012

Powtórka przed kolokwium

Zadania na rekurencję:

1. Napisz rekurencyjną funkcję triangle(n), generującą dla zadanego n wzory postaci:

   ****
   ***
   **
   *
   

   o n liniach.

2. Weźmy funkcję f zdefiniowaną następująco:

   def f(n):
       if n % 2 == 0:
           return n / 2
       else:
           return 3*n + 1
   

   Napisz rekurencyjną funkcję collatz_steps(n), która zwróci dla zadanego n liczbę elementów ciągu n, f(n), f(f(n)), …, potrzebnych do osiągnięcia 1. Np.

   collatz_steps(1) == 0
   collatz_steps(4) == 2
   

3. Napisz rekurencyjną funkcję binary(n), która dla zadanej liczby n znajdzie jej zapis binarny.
   Wskazówka: ostatnią cyfrą w tym zapisie będzie n % 2.
4. Napisz rekurencyjną funkcję newton(n, k), która dla zadanych liczb n i k wylicza współczynnik dwumianowy (“n po k”, wzór rekurencyjny na stronie http://pl.wikipedia.org/wiki/Symbol_Newtona).
5. Załóżmy, że mamy daną funkcję rosnącą w przedziale <0;n>. Napisz rekurencyjną funkcję bisection(f), która znajdzie przybliżenie miejsca zerowego funkcji f.

   Wskazówka 1: funkcję f można zdefiniować np. tak:

   def f(x):
   	import math
   	return math.tan(x - math.pi)
   

   i dalej wywołać funkcję bisect na funkcji f: bisect(f)
   
   Wskazówka 2: zastosuj metodę “połowienia” przedziału <0;n> – podobnie jak to miało miejsce w przypadku wyszukiwania binarnego.

6. Napisz rekurencyjną funkcję rec_count(v, x), która dla listy v i liczby x zwróci liczbę wystąpień liczby x w liście v.
7. Napisz rekurencyjną funkcję find_sum(v, x), która sprawdzi, czy na liście v występują dwie kolejne liczby o sumie x.
8. Napisz rekurencyjną funkcję check_sort(v), która sprawdzi, czy lista v jest posortowana.
9. Napisz rekurencyjną funkcję rev_number(n), która dla danej liczby całkowitej n zwróci liczbę powstałą z n poprzez odwócenie porządku cyfr (np. rev_number(123)=321). Uwaga: chodzi o rozwiązanie używające wyłącznie operacji na liczbach całkowitych.
10. Napisz rekurencyjną funkcję strange_sum(n), która zwróci sumę kwadratów liczb parzystych mniejszych lub równych niż n i sześcianów liczb nieparzystych mniejszych lub równych niż n (np. strange_sum(3) = 1 + 4 + 27 = 32.

Zadania wg. P. Bednarza

1. używając funkcji randint modułu random wygenerować 10 losowych list długości 10000, posortować i wypisać (Tutaj przyda się iteracyjna wersja merge)
2. Co robi funkcja f?

   			def f(a, b):
   				if b == 0:
   					return 0
   				return a + f(a, b - 1)
   			

3. Co się stanie jeśli w powyższym przykładzie zmienimi znak + na *?
4. 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)
   			

5. 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:])
   			

6. Napisz rekurencyjną funkcję rec_rev(s), która dla zadanego napisu s zwróci odwrócony napis s.
7. Napisz rekurencyjną funkcję rec_find(v, x), która zadanego posortowanej listy v zwróci wartość True, gdy element x występuje na liście v. W przeciwnym przypadku funkcja zwraca wartość False.
8. Napisz rekurencyjną funkcję rec_pal(s) zwracającą True, gdy s jest palindromem. W przeciwnym przypadku funkcja zwraca wartość False.
9. Podziałem liczby naturalnej n nazwiemy ciąg liczb naturalnych sumujących się do n. Napisz rekurencyjną funkcję partition(n), która znajdzie wszystkie podziały liczby n.

Dziś będzie o rekurencji. Slajdy tu, kod z wykładu tam