Drugie zadanie zaliczeniowe

• adres - 2pkt
• prezenty - 3pkt
• uzupelnij - 2pkt
• rozdziel - 6pkt
• zapotrzebowanie - 2pkt
• kiedy_prezent - 5pkt

Ćwiczenia ze wstępu do informatyki, semestr zimowy, 2012/13

Sprawy organizacyjne

• Konsultacje: środa, 12:30-14:30, sala 5810
• Mój mail: pb248404@mimuw.edu.pl
• Na stronie http://codingbat.com/python można znaleźć proste zadania z pythona pozwalające oswoić się ze składnią

Zadania

Laboratorium 2 (15.10.2012)

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.

Laboratorium 3 (22.10.2012)

1. Używając funkcji randint modułu random wygenerować 10 losowych list długości 10000, posortować 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. 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:])
   			

7. Napisz rekurencyjną funkcję rec_rev(s), która dla zadanego napisu s zwróci odwrócony napis s.
8. 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.
9. Napisz rekurencyjną funkcję rec_pal(s) zwracającą True, gdy s jest palindromem. W przeciwnym przypadku funkcja zwraca wartość False.
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.

Laboratorium 4 (29.10.2012 + 05.11.2012)

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

Powtórka przed kolokwium

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) == 1
   collatz_steps(4) == 3
   

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.

Kod funkcji sortujących...

• sortowanie przez wybór
• sortowanie przez wstawianie
• sortowanie bąbelkowe
• sortowanie przez scalanie (wersja z wykładu)

... i wyszukiwania binarnego

• Funkcja binary_search(v, x) sprawdzająca, czy na liście posortowanej v znajduje się element x.
• Funkcja binary_index(v, x) zwracająca indeks pewnego (ćwiczenie: dla liczby naturalnej n znaleźć wektor v, dla którego funkcja binary_index zwróci index n-tego z kolei wystąpienia elementu x w wektorze v) wystąpienia elementu x na liście posortowanej v (lub -1 w przypadku, gdy ten element nie występuje na liście).

Kolejna porcja zadań powtórkowych (07.11.2012)

1. Binarny ciąg Van der Corputa powstaje poprzez odwracanie zapisu binarnego kolejnych liczb naturalnych. Przed odwróceniem zapisy binarne są najpierw uzupełniane zerami do odpowiedniego miejsca. Np. jeśli rozpatrujemy ciąg trzycyfrowy (w zapisie binarnym), to przed odwróceniem mamy ciąg zapisów: [000, 001, 010, 011, 100, 101, 110, 111], co tłumaczy się na ciąg [0, 1, 2, 3, 4, 5, 6, 7]. Po odwróceniu zapisów mamy natomiast [000, 100, 010, 110, 001, 101, 011, 111], co tłumaczy się na ciąg [0, 4, 2, 6, 1, 5, 3, 7]. Napisz funkcję vdcorput(p), która dla zadanej liczby cyfr p zwróci odpowiadający jej ciąg Van der Corputa.
2. Napisz iteracyjną i rekurencyjną wersję funkcji incr_segment(v), która dla zadanej listy v zwróci jej najdłuższy rosnący segment (spójny kawałek).
3. Napisz funkcję prefix(s, w), która dla dwóch słów s i w zwróci najdłuższy wspólny prefix obu słów.
4. Napisz funkcję ol_concat(s, w), która sklei ze sobą dwa słowa być może nakładając na siebie koniec s z początkiem w lub koniec w z początkiem s (jeśli są identyczne) aby otrzymać najkrótsze w tym sensie połączenie tych słów. Np. dla słów ol_concat(kajak, kredka) powinno być równe kredkajak, gdyż można je skleić albo do kredkajak, albo do kajakredka, ale pierwsze z tych słów jest krótsze w zapisie.
5. Napisz funkcję convert(n, p1, p2), która przekształci liczbę n w systemie p1-tkowym na liczbę w systemie p2-tkowym. Można założyć, że zarówno p1 jak i p2 są z przedziału [2, 9]. Np. convert(23, 10, 2)=10111.
6. Zaimplementuj funkcję bucket_sort(v), która posortuje ciąg liczb całkowitych z przedziału [-10000; 10000] używając sortowania kubełkowego.

Laboratorium 6 (12.11.2012)

1. Stwórz pusty słownik. Zapoznaj się z funkcjami, jakie są dla niego dostępne. Dodaj do niego następujące elementy: pod kluczem 1 wartość 3, 5->2, "a"->4. Usuń jeden z elementów używając metody del, a drugi używając metody pop. Przypisz na pozostały element wartość 10.
2. Sprawdź, jak działają metody iterkeys, itervalues, iteritems. Której z nich odpowiada zwykła iteracja pętlą for?
3. Stwórz słownik, zawierający pary (indeks, słowo) z tekstu z zadania 4 (lab4), gdzie indeks oznacza numer słowa (numerowane od 0). Użyj funkcji enumerate.
4. Stwórz funkcję zwracającą dla zadanego napisu słownik, który pod indeksem odpowiadającym danemu słowu zawiera jego długość.
5. Rozwiąż poprzednie zadanie używając funkcji map i zip.
6. Używając klasy defaultdict (moduł collections) stwórz funkcję zwracającą dla danego słowa słownik, który pod indeksem odpowiadającym danej literze będzie zawierał liczbę jej wystąpień.
7. Używając klasy defaultdict stwórz dla zadanego napisu słownik, zawierający dla słów z napisu ilość ich wystąpień.
8. Rozwiąż zadanie 5.2 (lab 4) korzystając ze słowników.

1. Stwórz zbiory liter z napisów "alabama" i "alaska". Jak wygląda różnica pomiędzy jednym zbiorem a drugim (użyj operatora "-")?
2. Zobacz jakie inne funkcje na zbiorach są dostępne w pythonie.
3. Stwórz zbiór słów z pliku the_emperors_new_clothes.txt (usuń najpierw znaki interpunkcyjne zastępując je spacjami).
4. Stwórz również zbiór słów z pliku the_bell.txt i wypisz słowa występujące w pierwszym, ale nie występujące w drugim.
5. Znajdź słowa, które występują dokładnie w jednym z powyższych plików oraz słowa wspólne dla obu plików.
6. Dla danego zbioru wygeneruj jego zbiór potęgowy (zbiór wszystkich podzbiorów tego zbioru).

Laboratorium 7 (19.11.2012)

1. Przepisz poniższy program tak, aby uniknąć użycia zmiennych globalnych (zachowaj sposób wyliczania wyniku w funkcji f).

   a = 2
   b = 5
   c = 0
   def f():
       global c
       for i in range(b):
           c += i ** a
   f()
   print c
   

2. Napisz funkcję knight(a), która dla zadanej pozycji a (dwuelementowa krotka) na szachownicy zwróci listę pozycji odległych od niej o jeden ruch skoczka szachowego. Zakładamy, że szachownica jest kwadratową tablicą o wymiarach 8x8, indeksowaną dwuelementowymi krotkami (a, b), gdzie a i b są liczbami naturalnymi z przedziału [0,7].
3. Napisz funkcję perfect(n), która dla zadanej liczby naturalnej n sprawdzi, czy liczba ta jest liczbą doskonałą.
4. Napisz funkcję all_perfects(n), która znajdzie wszystkie liczby doskonałe mniejsze lub równe od n w następujący sposób. Najpierw konstruujemy słownik, w którym pod kluczami, będącymi liczbami całkowitymi, znajdzie się lista liczb, których suma dzielników (różnych od tej liczby) jest równa kluczowi. Następnie funkcja all_perfects w pętli znajdzie w tym słowniku liczby doskonałe.
5. W pewnym banku kody do systemu składają się z ciągów cyfr długości 10. Podczas każdego logowania zostajemy poproszeni o podanie pewnych (losowych) 3 cyfr naszego hasła. Okazało się, że na komputerze, z którego zwykle logujemy się do systemu naszego banku ktoś zainstalował oprogramowanie zbierające dane na temat historii naszych logowań. Są w nim odnotowywane jedynie poprawne próby logowania. Dane są zbierane w formie słownika pythonowego. Kluczami są trzyelementowe krotki oznaczające indeksy cyfr hasła, o które zostaliśmy poproszeni, np. klucz (0, 3, 7) oznacza, że w pewnej próbie logowania system poprosił nas o zerową, trzecią i siódmą cyfrę z hasła. Wartościami w słowniku będą natomiast cyfry hasła występujące na pozycjach z klucza. Napisz funkcję attempts(d), która dla zadanego słownika d zawierającego historię logowań zwróci liczbę prób potrzebną do złamania naszego hasła (chodzi tutaj o przypadek pesymistyczny, w którym dla każdej nieznanej cyfry z hasła włamujący "trafia" dopiero podczas ostatniej próby). Przykład:

   attempts({(0,1,2):(7,3,5), (3,4,5):(7,2,0), (6,7,8):(9,4,1)})==10
   attempts({(0,1,2):(7,3,5), (3,4,5):(7,2,0), (6,7,8):(9,4,1), (0,8,9):(7,1,1)})==1
   

6. Napisz funkcję BST(l), która dla zadanej listy liczb całkowitych l zwróci drzewo binarnych poszukiwań powstałe poprzez dodawanie do drzewa liczb w kolejności ich występowania na liście l. Każdy węzeł drzewa ma być trzyelementową krotką, a brakujące puste poddrzewo reprezentowane jest przez obiekt None. Przykład:

   BST([4,1,6,2,5,6,8])=((None, 1, (None, 2, None)), 4, ((None, 5, None), 6, (None, 8, None)))
   

Zadania powtórkowe przed kolokwium poprawkowym (06.12.2012)

1. Dana jest tablica kwadratowa A rozmiaru n x n wypełniona liczbami całkowitymi. Napisz funkcje sum_iter(A) i sum_rec(A) zwracające tablicę B, która na pozycji (i, j) ma sumę wszystkich pozycji (k, l) z tablicy A, dla których 0 ≤ k ≤ i i 0 ≤ l ≤ j.
2. Niech S(f, n) oznacza sumę wartości funkcji f dla wszystkich liczb naturalnych od 0 do n. Funkcja g zdefiniowana jest tak:
   • g(0) = 1
   • g(n) = S(g, n-1) + 6, dla n > 0.
   Funkcja h natomiast zdefiniowana jest tak:
   • h(0) = 2
   • h(n) = S(h, n-1) - S(g, n-1) + 6, dla n > 0.
   Napisz rekurencyjne i iteracyjne wersje funkcji g i h. Która z nich działa szybciej? Spróbuj policzyć h(10) dla każdej z nich.
3. Napis s został zakodowany w taki sposób, że wszystkie jego spółgłoski i samogłoski zostały ułożone w odwrotnej kolejności, tzn. pierwsza samogłoska została zamieniona kolejnością z ostatnią, następnie druga z przedostatnią, itd. Analogicznie postępowano ze spółgłoskami. Napisz procedurę decode(s), która zdekoduje napis s zakodowany opisanym szyfrem.

Laboratorium 9 (10.12.2012)

1. Napisz funkcję zip_code(s), która sprawdzi, czy napis s jest poprawnym polskim kodem pocztowym.
2. Napisz funkcję remove_numbers(s), która usunie z napisu s wszystkie cyfry.
3. Napisz funkcję sum_all(s), która dla zadanego napisu s zsumuje wszystkie liczby całkowite występujące w napisie s.
4. Napisz funkcję trim_all(s), która zamieni wszystkie ciągi białych znaków w napisie s na pojedynczą spację, czyli np.

   trim_all("Ala     ma kota   .")=="Ala ma kota ."

5. Załóżmy, że mamy napisać fragment strony internetowej w języku przypominającym html. Do dyspozycji mamy trzy rodzaje znaczników: em, b i br. Znaczniki em i b otaczają fragment tekstu powodując zmianę wyglądu jego czcionki. Z tego powodu występują dwie odmiany tych znaczników: odmiana otwierająca (<em>, <b>) i zamykająca (</em>, </b>). Znacznik br natomiast występuje tylko w jednej wersji (<br/>) powodującej złamanie wiersza w miejscu jego wystąpienia. Dodatkowo chcemy, aby były to jedyne znaczniki występujące w tekście (nie chcemy innych wystąpień znaków < i > w tekście) oraz nie chcemy, aby wewnątrz znaczników em i b znajdowały się inne znaczniki oraz chcemy, aby znaczniki były poprawnie domknięte. Napisz funkcję test_markups(s), która sprawdzi, czy napisany przez nas tekst s spełnia te wymogi.
6. Napisz funkcję pretty_printer(s), która znajdzie wszystkie wystąpienia liczb całkowitych w tekście s i wypisze je w oddzielnych liniach w formacie:

   start end number number_pow
   

   gdzie start i end to początkowa i końcowa pozycja liczby number w tekście s, a number_pow to liczba 2 podniesiona do potęgi number.
7. Napisz za pomocą pojedynczego wyrażenia regularnego funkcję, która dla pliku dmel stworzy nowy plik, składający się ze wszystkich wpisów o funkcji OrthoD B i roli orthologous_to, które zawierają dwa wystąpienia tego samego znaku (+ lub -). Dodatkowo chcemy, aby w nowym pliku kolumny zawierające początkową i końcową pozycję wpisu były ze sobą zamienione miejscami.

Laboratorium 10 (17.12.2012)

1. W pliku avgs.txt dana jest lista miejscowości wraz ze średnią temperaturą w grudniu. Posortuj ją używając potoków w kolejności rosnącej średniej temperatury.
2. Wypisz nazwę i rozmiar 5 największych plików z katalogu domowego.
3. Przeszukaj swój katalog domowy rekurencyjnie i znajdź wszystkie wystąpienia plików o tej samej nazwie (mogą się różnić co najwyżej wielkością liter). Na wyjściu chcemy dostać takie nazwy poprzedzone liczbą wystąpień.
4. Policz liczbę takich nieunikalnych nazw plików z poprzedniego zadania.
5. Wypisz do pliku bests.txt początek, koniec i score z pliku dmel.gff posortowane po score do pliku best_scores.txt.
6. Wypisz wartości score z wygenerowanego pliku best_scores.txt na pozycjach od 1000 do 2000.
7. Napisz potok, który wypisze "Yes" dla pliku posortowanego i "No" wpp.

Testy do zadania 2 (21.01.2013)