Monthly Archives: October 2012

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.

WDI – lab 3

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.

WDI 2 – lab

Zadania wg (P. Bednarza)

(gwiazdka oznacza zadania trudniejsze – dodatkowe/dla chętnych)

  1. Zaimplementuj funkcję kalkulator(d, a, b), która przyjmuje jako parametr rodzaj wykonywanego działania i dwa parametry liczbowe i zwraca wynik w postaci liczbowej. Można założyć, że działanie jest pojedynczym znakiem ze zbioru {“+”, “-”, “*”, “/”}. Przykładowo kalkulator(“+”, 2, 2) ma zwrócić 4.
  2. (*) Spróbuj rozwiązać to zadanie sprytniej przy pomocy funkcji eval.
  3. Rozwiąż problem double_sum.
  4. Napisz funkcję cezar(napis, przesuniecie), która dla parametru napisowego napis i parametru całkowitego przesuniecie zwróci napis zaszyfrowany szyfrem Cezara z odpowiednim przesunięciem (użyj funkcji chr i ord do kodowania i odkodowywania liter; załóż, że napis składa się z liter alfabetu angielskiego).
  5. Napisz iteracyjną funkcję fib(n), która dla zadanej liczby całkowitej dodatniej n zwróci n-ty wyraz ciągu Fibonacciego.
  6. (*) Napisz rekurencyjną wersję funkcji fib z poprzedniego zadania.
  7. Napisz funkcję palindom(s), która dla zadanego ciągu znaków s sprawdzi, czy napis ten jest palindromem.
  8. Anagramem słowa s nazywamy słowo w powstałe przez poprzestawianie liter w słowie s. Napisz funckję anagram(s,w), zwracającą wartość True wtedy i tylko wtedy, gdy w jest anagramem s.
  9. Zaimplementuj funkcje insertion_sort(l), bubble_sort(l) i selection_sort(l), wykonujące odpowiednio sortowanie przez wstawianie, sortowanie bąbelkowe i sortowanie przez wybór.
  10. Napisz funkcję cezar z zadania 4 przy użyciu funkcji map.

Welcome to regulatory genomics @ MIM UW

We are a team of young computer scientists and mathematicians working on current problems in regulatory genomics. We are a part of the larger Computational biology group at the Faculty of Mathematics, Informatics and Mechanics, University of Warsaw.

Currently we are mostly focusing on computational models of genome-wide chromatin dynamics and evolution of regulatory sequences.