Zadanie 1
WE: a, b, c - liczby
WY: x= max(a, b, c)
Wskazówka: użyć zmiennej pomocniczej do pamiętania max(a, b)
Zadanie 2
WE: a, n - liczby całkowite, n>=1
WY: x= a^n
Zadanie 2.5
WE: a, n - liczby całkowite, n może być ujemne
WY: x= a^n
Zadanie 3
WE: a, b -liczby całkowite
WY: c= NWD(a, b)
Wskazówka: wykorzystać następującą własność NWD:
1. NWD(a, 0)= a
2. NWD(a, b)= NWD(b, a mod b)
gdzie "a mod b" oznacza resztę z dzielenia a przez b; zauważmy że a mod b < b
tak więc stosując regułę (2) możemy zredukować problem do tego samego problemu,
ale z mniejszym drugim parametrem ...
Dodatkowo: wykonaj symulacje dla a=10, b=14
Zadanie 4
WE: a, b, c - liczby
WY: odpowiedz na pytania:
- czy a, b i c mogą być długościami boków trójkąta?
- jeśli tak, to jaki to jest trójkąt (prostokątny,
ostrokątny, rozwartokątny)
Uwaga: w tym wypadku algorytm drukuje stosowne napisy przy pomocy
procedury "pisz tekst"
Zadanie 5
WE: n, k - liczby
WY: y= Newton(n, k)
gdzie Newton(n, k) to symbol Newtona "n po k"; Newton(n, k)= n!/(k!*(n-k)!).
Wymaganie dodatkowe: w czasie obliczeń starać się aby w miarę możliwości
nie powstawały duże liczby całkowite, tak więc nie należy bezpośrednio obliczać
silni ...
Przykłady: aby uniknąć dużych liczb w czasie obliczeń postępujemy tak:
Newton(7, 3) = 1*2*3*4*5*6*7 / ( (1*2*3)* (1*2*3*4) ) = 5*6*7 / (1*2*3)
w powyższym przykładzie skracamy drugi czynnik mianownika;
Newton(7, 5) = 1*2*3*4*5*6*7 / ((1*2*3*4*5)*(1*2)) = 6*7 / (1*2)
w powyższym przykładzie skracamy pierwszy czynnik mianownika.
Zadanie 5.5
WE: n, k - liczby
WY: y= Newton(n, k)
Wskazówka: wykorzystaj zależność Newton(n, k) = n/k * Newton(n-1, k-1)
Uwaga: w wyrażeniach NIE mogą się pojawiać liczby niecałkowite!
Zadanie 6
WE: (x, y) - współrzędne kartezjańskie
WY: (r, fi) - współrzędne biegunowe punktu na wejściu; r>=0, 0º<=fi<360º
Założenie: dysponujemy funkcją arcsin().
Zadanie 7
WE: a, b, c - dowolne liczby rzeczywiste
WY: podać rozwiązania równania a*x^2 + b*x + c = 0
r = liczba rozwiązań (r= 0, 1 lub 2)
x1, x2 - zmienne zawierające rozwiązania
Uwzględnić wszystkie możliwe przypadki!
Zadanie 8
Zbiornik na wodę ma kształt złożonych podstawami dwóch stożków o średnicy
podstawy "r" i wysokości "h" każdy. Ile jest wody w zbiorniku jeśli wodowskaz
jest na poziomie "x" (0<=x<=2h).
Zadanie 9
WE: p - liczba naturalna
WY: odpowiedz na pytanie czy p jest liczbą pierwszą.
Wymaganie dodatkowe: postaraj się NIE sprawdzać wszystkich liczb 2,
..., p-1 (czy są dzielnikami p).
Zadanie 10
WE: x, eps - liczby rzeczywiste
WY: y= e^x.
Wskazówka: wykorzystać fakt e^x = 1 + x + x^2/2! + x^3/3! + ... .
Obliczenia prowadzić z dokładnością eps, tj do momentu gdy |x^k/k!| < eps dla
pewnego k.
Przy obliczaniu składnika szeregu koniecznie wykorzystać wartość
poprzedniego składnika (aby zmniejszyć czas działania algorytmu).
Zadanie 10.5
WE: n -liczba całkowita
WY: q = 1 + 1/2 - 1/3 - 1/4 + 1/5 + 1/6 - 1/7 - 1/8 + ...
gdzie powyższa suma ma n -składników.
Zadanie 11
Oblicz wartość n -tego elementu ciągu określonego następująco:
a_k = a_(k-1) + 3 a_(k-2) - a_(k-3)^3
przy czym
a_0 = a_1 = a_2 = 1
Zadanie 12 (*)
WE: a, n -liczby całkowite
WY: x= a^n
Wymagania dodatkowe:
A. algorytm ma działać w czasie O(log n); przez "czas" rozumiem liczbę
operacji mnożenia (trywialny algorytm działa w czasie O(n-1), gdyż wykonuje n-1
mnożeń)
B. wolno używać JEDYNIE zmiennych całkowitych oraz operacji
arytmetycznych +, -, *, / a także operacji "mod" (a mod b = reszta z dzielenia a
przez b)
Wskazówka: do tego zadania najlepiej podejść metodą "kolejnych
przybliżeń":
1. rozważ przypadek gdy n=2^k, wtedy rozwiązanie jest proste ...
2. wymyśl rozwiązanie używające tablicy pomocniczej (tablica to ciąg
elementów; np a[1], a[2], ..., a[10])
3. podaj rozwiązanie spełniające wszystkie warunki zadania
Zadanie domowe 20
WE: a, b - liczby całkowite, >=0
WY: r= a mod b
Wymaganie dodatkowe:
1. wolno używać wyłącznie działań arytmetycznych +,-,*
2. liczba działań arytmetycznych wykonywanych przez algorytm powinna być
znacząco mniejsza niż a/b (gdybyśmy obliczali "a mod b" przy pomocy odejmowania
to właśnie tyle działań byśmy wykonali ...)
Zadanie domowe 21
Napisz algorytm znajdujący liczby naturalne
i, j, k, l <= 20
takie że i^3 + j^3 + k^3 = l^3.
Wymaganie dodatkowe: postaraj się NIE sprawdzać wszystkich możliwych 20^3
wartości zmiennych i, j, k.
Zadanie domowe 22
Zadanie 12, o ile nie zdążyliśmy go zrobić w trakcie zajęć ...