WDI – lab 4

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.

Leave a Reply

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>