Month: October 2015

WDI – zajęcia 4

Zadania powtórkowe:

1. Napisz rekurencyjną funkcję check_sort(v), która sprawdzi, czy lista v jest posortowana (ściśle, rosnąco lub malejąco).

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 2 wersje (iteracyjną i rekurencyjną) funkcji incr_segment(v), która dla zadanej listy v zwróci jej najdłuższy rosnący segment (spójny kawałek).

4. (★) 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.

Operacje na napisach:

5. Używając maksymalnie trzech wywołań funkcji strip, rstrip, lstrip należy przekształcić:

  • ‘abcccbca’ w ‘ccc’
  • ‘bababa’ w ‘ab’

6. 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

7. Napisz skrypt, który dokona korekty tekstu z poprzedniego ćwiczenia:

  • każde słowo rozpoczynające zdanie musi zaczynać się z dużej litery,
  • pozostałe słowa zaczynają się z małej litery,
  • sąsiednie słowa muszą być rozdzielone dokładnie jedną spacją,
  • znaki interpunkcyjne przylegają do poprzedzającego je słowa,
  • tekst rozpczyna się od słowa, a kończy kropką (należy usunąć zbędne białe znaki).

Zadania z kolokwiów:
Kolokwium 2012:
– zadanie 1 – segmenty (było na kartkówce)
Kolokwium poprawkowe 2012:
– zadanie 2 i 3 – quasindromy
– zadanie 1 – ceny

WDI – zajęcia 3

    1. Co robi funkcja f? 
      		def f(a, b):
			if b == 0:
				return 0
			return a + f(a, b - 1)
    2. Co się stanie jeśli w powyższym przykładzie zmienimi znak + na *?
    3. 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)
    4. 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:])
    5. Napisz rekurencyjną funkcję rec_rev(s), która dla zadanego napisu s zwróci odwrócony napis s.
      Hint: Wykorzystaj dodawanie napisów s1+s2 oraz to, że napisy można indeksować podobnie jak listy.
    6. Napisz rekurencyjną funkcję rec_pal(s) zwracającą True, gdy s jest palindromem. W przeciwnym przypadku funkcja zwraca wartość False.
    7. Napisz rekurencyjną funkcję rec_find(v, x), która dla zadanej posortowanej rosnąco listy liczb v zwróci wartość True, gdy element x występuje na liście v. W przeciwnym przypadku funkcja zwraca wartość False. Zakładamy, że lista v jest posortowana rosnąco — nie trzeba tego sprawdzać.
    8. Napisać funkcję merge z wykładu w wersji iteracyjnej.

    9. (★) Zdefinujmy ciąg Fibonacciego w następujący sposób:

      • f(0) = 0, f(1) = f(2) = 1 gdy n <= 2
      • f(n) = f(n-1) + f(n-2) w p.p.

      Wypisz drzewo wywołań rekurencyjnych f(n). Za pomocą znaków | (pipe) połącz wywołania rekurencyjne z wywołującą funkcją (f(n-1) oraz f(n-2) z f(n)), a odgałęzienia do sumowanych wyników zaznacz znakiem + (plus). Przykłady pokazują jak wygląda wyjście dla różnych wartości n.

    10. (★) Podziałem liczby naturalnej n na k części nazywamy ciąg k liczb naturalnych sumujących się do n. Napisz funkcję p(n,k), która dla danej liczby naturalnej n znajdzie liczbę podziałów liczby n na k części.

WDI – zajęcia 2

Zadania na laboratorium nr 2:

  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 używając funkcji eval.
  3. Zaimplementuj funkcję double_sum.
  4. Znajdź sumę liczb naturalnych mniejszych niż 1000, które są wielokrotnościami 3 lub 5.
  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 funkcję palindrom(s), która dla zadanego ciągu znaków s sprawdzi, czy napis ten jest palindromem.
  7. (★) Dana jest lista N liczb. Czy istnieje liczba występująca na tej liście więcej niż N/2 razy?
  8. (★) W przestrzeni rozmieszczono n punktów w taki sposób, że żadne trzy z nich nie są współliniowe. Następnie każdą parę tych punktów połączono odcinkiem i każdy odcinek pokolorowano na czarno albo na czerwono. Trójkątem jednobarwnym nazwiemy każdy trójkąt mający wszystkie trzy boki tego samego koloru. Dane jest n = 6 punktów oraz lista czerwonych odcinków wyrażona za pomocą listy incydencji: l = [[1,3,5],[0,2,4],[1,3,5],[0,2,4],[1,3,5],[0,2,4]]. Indeks listy l oznacza punkt, a pod danym indeksem listy l znajduje się lista punktów z którymi ten punkt tworzy odcinek. Na przykład punkt o indeksie 0 tworzy odcinki z punktami o indeksach: 1,3 oraz 5 (l[0] = [1,3,5]). Znajdź liczbę wszystkich trójkątów jednobarwnych.