Zestawy zadań z przedmiotu: Wstęp do Informatyki
Kierunek: Informatyka, sem I.
Studia stacjonarne.
Zestaw I.
1. Trzy liczby naturalne a, b, c spełniają warunek a2+b2=c2. Wyznaczyć wszystkie trójki liczb (a, b, c) w których c nie przekracza zadanej liczby naturalnej N.
2. Wyznaczyć największą liczbę spośród n wczytywanych z klawiatury. Rozważyć przypadek kilku kolejnych największych liczb.
3. Sprawdzić czy wczytywane dwie liczby są kolejnymi elementami ciągu an = bn - an-1, gdzie: bn=bn-1-2, a1=1, b1=1.
4. Dla liczb całkowitych dodatnich N, M wyznaczyć największy wspólny dzielnik (WD) i najmniejszą wspólną wielokrotność (WW ).
5. Oblicz wartość jednomianu p(x) = 1+x+...+x+...+xn w zadanym punkcie x=y. Zastosować schemat Hornera.
6. Dokonać konwersji dziesiętnej, nieujemnej liczby całkowitej N na liczbę w systemie o podstawie B. Wyprowadzić wartość liczby w nowym systemie.
7. Wyznaczyć wszystkie liczby pierwsze nie większe od danej liczby naturalnej N.
8. Program, który wczytuje wprowadzoną z klawiatury liczbę naturalną N winien odpowiadać na pytanie, czy liczba ta jest wielokrotnością dowolnej liczby naturalnej większej od 1 i nie jest równocześnie wielokrotnością sześcianu dowolnej liczby naturalnej większej od 1.
9. Liczbę fn nazywamy liczbą Fibonacciego, gdy spełnia warunki:
fn = 1
dla n=1,2,
fn = fn-1 + fn-2
dla n > 2.
Sprawdzić czy wprowadzona z klawiatury liczba naturalna M jest sumą co najwyżej czterech kolejnych liczb Fibonacciego.
10. Dane są ciągi {an}, {bn} określone następująco:
a1 = a2 =1, an= an-1+ an-2, dla n>2; b1 = b2 = b3=1, bn= bn-1+ bn-2 + bn-3 dla n>3; Wyznaczyć ciąg {cn}, którego wyrazy są kolejnymi liczbami naturalnymi należącymi do ciągu {an}
lub {bn}. Wyprowadzić kolejne wyrazy ciągu {cn}, które są mniejsze od wprowadzonej z klawiatury liczby naturalnej N.
11. Obliczyć wartości funkcji sin(x), cos(x), tan(x) wykorzystując ich rozwinięcie w szereg Taylora.
12. Obliczyć sumę n początkowych wyrazów szeregu:
2
4
6
1 − x
+ x
− x
+ ...
2 !
4 !
6 !
13. Obliczyć sumę wyrazów szeregu:
3
5
7
x −
x
+ x
− x
+ ...,
x
< 1
3
5
7
z zadaną dokładnością ε (a
n-an-1 <ε), gdzie an, an-1 są wartościami: n-tego, (n-1)-ego wyrazu
szeregu.
14. Przybliżony pierwiastek sześcienny z danej liczby x wyraża się wzorem: a
2
i+1 =1/3(2 ai + x/ ai ),
a1=1.
Wyznaczyć wartość pierwiastka przyjmując warunek stopu: (ai+1-ai)/ a i .
15. Funkcja f(t,s) zdefiniowana jest w sposób następujący:
f(t,s) = (t2+s2)/2
t∈[to, tmx], s∈[so, smx]. Wyznaczyć wartości funkcji f(t,s) określonych na dyskretnych, równoodległych punktach przedziałów określoności dla ustalonego kroku dyskretyzacji h.
16. Sprawdzić, czy wyznaczone wartości, tożsamych matematycznie funkcji f(x)=√(x2+1)-1 oraz g(x)=x2/( √(x2+1)+1) w punktach x= 8-1, 8-2, 8-3, ... , są takie same. Uzasadnić wyniki.
17. Wyprowadzić w sposób uporządkowany (niemalejąco) wszystkie wartości p/2q, gdzie p, q są liczbami naturalnymi z przedziału 0<p, q<10.
18. Ile liczb z przedziału [10,1000] składa się z nieparzystych cyfr, a ile z parzystych.
19. Niech X= x1 x2 ... xm będzie słowem w alfabecie Σ. Jeżeli x1 x2... xm = xm xm-1... x1 to mówimy, że X jest palindromem. Sprawdzić czy zadane słowo lub zdanie (zignoruj spacje, znaki interpunkcyjne i różnice wielkości liter) alfabetu Σ jest palindromem.
20. Wygenerować wszystkie k-elementowe podzbiory zbioru n-elementowego X={1, 2, ..., n}. Podać liczbę takich podzbiorów.
Zestaw II.
1. Dana jest n-elementowa tablica A. Wyznaczyć maksymalną wartość będącą kwadratem różnicy dwóch sąsiednich elementów tej tablicy.
2.
Dana jest tablica A. Obliczyć sumę średniej arytmetycznej z ujemnych wartości i średniej geometrycznej z dodatnich wartości elementów tablicy.
3.
W tablicy A zamienić ze sobą elementy w sposób następujący, pierwszy z ostatnim drugi z przedostatnim itd.
4.
Sprawdzić czy w zadanej tablicy A liczb całkowitych istnieją dwa elementy, których suma wartości jest równa liczbie x.
5.
Wprowadzając z klawiatury ciąg liczb dodatnich zakończonych liczbą –1, będącą znacznikiem końca wprowadzania, umieścić m największych wartości w tablicy A. Zakładamy, że tablica jest co najmniej m-elementowa.
6.
Dana jest tablica A oraz wartości L, U. Obliczyć wartość iloczynu wszystkich średnich arytmetycznych, z k-kolejnych elementów, których wartości są większe od L i mniejsze od U.
Wyznaczyć liczbę czynników powyższego iloczynu, a spośród nich minimalną wartość.
7. Dokonać jednoznacznego przekształcenia dwuwymiarowej tablicy B w jednowymiarową tablicę A.
8. Wyznaczyć iloczyn wartości elementów drugiej przekątnej tablicy B.
9.
W zbiorze powtarzających się elementów wyznaczyć podzbiory elementów identycznych i liczbę ich powtórzeń (tzw. histogram).
10. Posortować tablicę A zgodnie z algorytmem sortowania „przez wybór” (Select_Sort), który sformułowany jest następująco: dla każdej pozycji k w sortowanej tablicy A, rozważamy wszystkie elementy o indeksach większych od k. Wybieramy najmniejszy z nich i dokonujemy zamiany z k-tym elementem. Rozważyć przypadek stabilnego algorytmu zachowującego wyjściową kolejność elementów o tych samych wartościach.
11. Dane są dwa uporządkowane rosnąco ciągi elementów: x ={xi, i=1, 2,..., n } oraz y = { yj, j =1, 2,
..., m}. Utworzyć z tych ciągów nowy uporządkowany rosnąco.
12. Dana jest dwuwymiarowa tablica B. Wyznaczyć indeksy takiego elementu tablicy B, dla którego iloraz sumy elementów w j-tej kolumnie przez sumę elementów w i-tym wierszu jest największy.
13. Dla dwuwymiarowej tablicy B wyznaczyć numer wiersza i kolumny elementu, dla którego suma otaczających go wartości jest najmniejsza.
14. Sprawdzić, czy w tablicy A suma dowolnych dwóch sąsiednich elementów jest równa średniej arytmetycznej wszystkich elementów tablicy.
15. Wyznaczyć numer wiersza dwuwymiarowej tablicy B, w którym występuje najdłuższy podciąg złożony z tych samych liczb. W przypadku kilku podciągów o tej samej długości należy zwrócić pozycję pierwszego z nich.
16. W kwadratowej tablicy B wyznaczyć indeksy elementu, dla którego suma elementów „w ukośnych rzędach” jest największa.
17. Dana jest dwuwymiarowa tablica B. Wyznaczyć ilość wierszy (kolumn), których wartości stanowią ciągi arytmetyczne.
18. Wypełnij dwuwymiarową tablicę A wartościami 0, 1, tak aby elementowi aij nadawana była wartość 1 jeśli największy wspólny dzielnik i oraz j wynosi 1, a 0 w przeciwnym przypadku.
19. Sprawdzić czy dany znak ×∈Σ występuje w zadanym tekście, obliczyć liczbę wystąpień oraz usunąć jego wystąpienia w tekście, (Σ- alfabet).
20. Dane są dwa ciągi znaków. Sprawdzić czy jeden z nich pojawia się wewnątrz drugiego.
1. Dla dodatnich liczb całkowitych k>0 definiowany jest szereg harmoniczny, którego k-ty wyraz wynosi:
1
1
1
h = 1 +
+
+ ... +
k
2
3
k
Zbudować rekurencyjny algorytm wyznaczenia wartości n-tego (n>0) wyrazu szeregu.
2. Wyznaczyć symbol Newtona, dla którego zachodzi następująca zależność:
1
jesli
k = 0
lub
k = n
n
=
n − 1
n − 1
+
k
w przeciwnym
przypadku
k − 1
k
3.
Pustą kwadratową tablicę B wypełnić „po spirali” wartościami tworzącymi ciąg arytmetyczny o zadanym wyrazie początkowym i zadanej różnicy ciągu. Rozpatrzyć przypadek wypełnienia zaczynając od dowolnego elementu skrajnego i środkowego. Rozważyć algorytm iteracyjny i rekurencyjny.
4.
Wyznaczyć liczbę najmniejszą i największą w ciągu liczb całkowitych o długości n=2k, k>0, (algorytm rekurencyjny).
5.
Zaprojektować rekurencyjny algorytm sortowania „przez wybór” (Select_Sort) i zastosować do posortowania tablicy A.
6.
Wielomian n-tego stopnia pn(x) zapisany jest w postaci Hornera :
pn(x) = ((.....((x + 1) x + 1) x + ...+ 1) x + 1)
Zaprojektować rekurencyjny algorytm wyznaczenia wartości pn(x).
7. Sprawdzić czy zadana liczba x należy do posortowanego ciągu liczb (a0, a2,..., an-1), n=2k, k>0.
Zastosować regułę przeszukiwania binarnego ciągu (algorytm rekurencyjny).
8. Dla liczb całkowitych a, b wyznaczyć wartość funkcji WD zdefiniowanej następująco: b
jeśli b ≤ a i a mod b = 0
WP(a,b) =
WP(b,a) jeśli a < b
WP(b, a mod b ) w przeciwnym przypadku.
Zbudować algorytm rekurencyjny.
9. Zastosować rekurencję do wygenerowania wszystkich n! permutacji zbioru X={1, 2, ..., n} w porządku leksykograficznym (antyleksykograficznym).
10. Zaprojektować rekurencyjny algorytm do rozwiązania problemu ”wież Hanoi”.