Month: November 2013

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 o jeden ruch skoczka szachowego. Zakładamy, że szachownica jest kwadratową tablicą o wymiarach 8×8, indeksowaną dwuelementowymi krotkami (a, b), gdzie a i b są 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 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ń. Zakładamy przy tym, że 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 – historii 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)))
   

Słowniki:

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 dla tekstu z zadania 4 (lab4), w którym kluczem będzie numer słowa w tekście, a wartością to słowo. 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 2 z labu 4 korzystając ze słowników.

Zbiory:

1. Stwórz zbiór 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).

Slajdy z ostatniego wykładu są tutaj.

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.