Category: teaching

Lab 5

  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.

Pierwsze zadanie zaliczeniowe

Jako, że sezon biegowy w pełni, w naszym pierwszym zadaniu zaliczeniowym postaramy się stworzyć system pomagający uporządkować jesienny trening grupie biegaczy. W pliku kilometraz.txt znajduje się zapis historii treningowej tej grupy, a poszczególne linie-wpisy mają postać:
runners_ID club distance time
runners_ID to liczba naturalna identyfikująca biegacza, club to nazwa klubu, do którego biegacz przynależy (nie zawiera spacji), distance jest liczbą rzeczywistą – liczbą kilometrów przebiegniętych przez biegacza, a time to liczba naturalna oznaczająca, ile sekund zajęło biegaczowi przebiegnięcie tego dystansu.
We wszystkich funkcjach w tym zadaniu zaliczeniowym, pierwszy parametr db_f będzie oznaczał plik z bazą danych treningowych w powyższym formacie.

Pierwszą częścią zadania będzie umożliwienie zawodnikom śledzenia swoich postępów. W związku z tym będziemy potrzebowali następujących funkcji:

  1. (1.5p.)distance(db_f, id), która zwróci całkowitą liczbę kilometrów, które zawodnik o identyfikatorze id odnotował w naszej bazie danych
  2. (1.5p.)best_velocity(db_f, id), zwracająca najlepszą prędkość spośród średnich osiąganych na poszczególnych treningach odnotowanych przez biegacza o identyfikatorze id (w km/h).

Jak wiadomo, trenerom łatwiej pracuje się, jeśli trenowana grupa jest w miarę możliwości jednorodna pod względem poziomu przygotowania. W związku z tym potrzebujemy funkcji, która pozwoli trenerom wybrać w swoim klubie grupę osób gotowych na planowany rodzaj treningu (3p.): funkcja group(db_f, club, min_distance, max_distance, min_average_velocity) powinna zwracać listę identyfikatorów zawodników klubu club, którzy w każdym treningowym biegu na dystansie pomiędzy min_distance i max_distance osiągali średnią prędkość co najmniej min_average_velocity (w km/h) (przyjmujemy, że jeżeli ktoś dotąd nie biegał na dystansach pomiędzy min_distance i max_distance, nie powinien być zaliczony do tej grupy).

Często po serii żmudnych treningów nadchodzi czas sprawdzenia swoich możliwości na zawodach. Aby ułatwić zadanie organizatorom zawodów, przygotujemy na podstawie naszej bazy danych prognozę popularności poszczególnych dystansów wśród biegaczy w bazie danych (4p.). Funkcja competitions(db_f, distances) przyjmuje jako parametr posortowaną rosnąco listę liczb całkowitych distances, zawierającą dystanse biegów, które odbędą się w ramach zawodów. Jako wynik, funkcja zwróci liczbę uczestników zainteresowanych poszczególnymi biegami. Przyjmiemy, że każdy biegacz jest zainteresowany tylko jednym dystansem, gdyż nie może jednocześnie biec w kilku biegach. Każdy przebiegnięty przez niego trening jest najbliższy któremuś z dystansów oferowanych przez organizatora zawodów. W przypadku treningów o długości równie bliskiej dwóm z oferowanych dystansów przyjmujemy, że taki trening bliższy jest dłuższemu dystansowi. Ulubiony dystans zawodnika będzie dystansem, który jest najbliższy największej ilości jego treningów (w przypadku remisów znowu preferujemy dłuższy z dystansów).

W najbliższym czasie pojawi się plik z przykładową bazą danych oraz wynikami przykładowych wywołań funkcji na tej bazie danych. Zadania w postaci kodu źródłowego (w jednym pliku zadanie1_nr-indeksu.py) przesyłają Państwo do wykładowcy i prowadzącego ćwiczenia (bartek@mimuw.edu.pl i (pawel.bednarz@mimuw.edu.pl lub mist@mimuw.edu.pl lub pwl@mimuw.edu.pl)) przed wykładem za trzy tygodnie (18 XI 2012, 12:15). Proszę o umieszczenie w tytule e-mail’a hasła [WDI-1].

Lab 4

  1. W pliku HP1b.gff3 znajdują się dane o miejscach wiązania białka HP1b do nici DNA muszki owocowej. Znajdź średnią wartość sygnału dla chromosomu 2L na pozycjach od 1,000,000-5,000,000.
  2. W pliku DNA.txt znajduje się fragment nici DNA człowieka. Znajdź listę wszystkich wystąpień sekwencji ACGT.
  3. Używając maksymalnie trzech wywołań funkcji strip, rstrip, lstrip przejdź od:
    • abcccbca do ccc
    • bababa do ab
  4. Zastąp spacje przez myślniki w napisie “Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nunc sit amet ligula in nisi varius mattis nec a urna. Phasellus tristique vehicula elit id imperdiet. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nunc orci libero, accumsan quis cursus vel, pretium nec dui. Nunc lobortis mollis felis, at malesuada velit volutpat id. Pellentesque quis iaculis massa. Vestibulum commodo egestas fringilla. Proin quis justo nunc. Nam sed ultricies orci. Curabitur adipiscing, dolor vel rhoncus accumsan, sapien tellus volutpat eros, at luctus mi augue sit amet turpis. Aliquam sagittis, lacus id commodo volutpat, erat justo auctor massa, in faucibus quam lectus et libero. Curabitur laoreet risus in urna aliquet vel fringilla felis volutpat. Morbi suscipit purus velit.” używając
    • funkcji replace
    • funkcji split i join
  5. (*)K-merami nazywamy sekwencje DNA długości k. Dla pliku DNA.txt wypisz najczęściej występujący 4-mer.
    Wskazówki:
    • stwórz funkcję, która dla danego k-meru znajdzie następny w stosunku do niego k-mer (w porządku leksykograficznym)
    • iterując po kolejnych 4-merach (począwszy od “AAAA”) znajdź liczbę ich wystąpień (używając funkcji z zadania 2); zapamiętaj najwyższy wynik i odpowiadający mu 4-mer

Lab 3

  1. Używając funkcji randint modułu random wygenerować 10 losowych list długości 10000, posortować je i wypisać.
  2. Napisać funkcję merge z wykładu w wersji iteracyjnej.
  3. Co robi funkcja f? 
    			def f(a, b):
				if b == 0:
					return 0
				return a + f(a, b - 1)
  4. Co się stanie jeśli w powyższym przykładzie zmienimi znak + na *?
  5. 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)
  6. Napisz rekurencyjną funkcję rec_find(v, x), która zadanej posortowanej listy v zwróci wartość True, gdy element x występuje na liście v. W przeciwnym przypadku funkcja zwraca wartość False.
  7. Napisz rekurencyjną funkcję rec_pal(s) zwracającą True, gdy s jest palindromem. W przeciwnym przypadku funkcja zwraca wartość False.
  8. Napisz rekurencyjną funkcję rec_rev(s), która dla zadanego napisu s zwróci odwrócony napis s.
  9. 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:])
  10. (*) 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 – lab2

(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 funkcję 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.