Bank zadań — informatyka

Przeszukuj zadania maturalne — po dziale, trudności i treści.

Znaleziono 66 zadań.

Algorytmy tekstoweŚrednie2 pkt2026 glowny

Pary słów. W pliku pary.txt znajduje się 500 par słów złożonych z małych liter alfabetu angielskiego; każda para w osobnym wierszu, słowa oddzielone spacją (długość słowa ≤ 50). Pliki z danymi (Dane-NF-2605.zip) pobierzesz na stronie arkusza.

Niech f(s)f(s) oznacza sumę kodów ASCII znaków słowa ss. Podaj parę słów s1,s2s_1,s_2 z jednego wiersza, dla której ∣f(s1)−f(s2)∣|f(s_1)-f(s_2)| jest największa, oraz tę wartość (jest tylko jedna taka para).

Przykład: f(oko)=329f(\text{oko})=329, f(pies)=433f(\text{pies})=433, różnica 104104. Dla pary_przyklad.txt odpowiedź to: eddcd eededcddceeecededcc 1403.

Wpisz: słowo1 słowo2 wartość.

Algorytmy i złożonośćTrudne4 pkt2026 glowny

Zapisz w pseudokodzie lub w wybranym języku programowania algorytm, który dla danych dwóch liczb całkowitych dodatnich aa i bb, o tej samej liczbie cyfr w zapisie dziesiętnym, obliczy liczbę przeniesień otrzymanych w trakcie ich dodawania pisemnego. Przykład: dla 2773227732 i 7261972619 wynik to 44.

Uwaga: algorytm może operować wyłącznie na liczbach całkowitych i używać tylko zmiennych przechowujących pojedyncze liczby całkowite. Możesz korzystać tylko z operatorów arytmetycznych (dodawanie, odejmowanie, mnożenie, dzielenie, dzielenie całkowite, reszta z dzielenia), logicznych, porównań, instrukcji sterujących i przypisania oraz własnych funkcji z tych operacji. Zabronione są funkcje wbudowane, tablice/listy i konwersje napis↔liczba.

Specyfikacja. Dane: aa, bb — dodatnie liczby całkowite o tej samej liczbie cyfr. Wynik: pp — liczba przeniesień.

Algorytmy i złożonośćŁatwe1 pkt2026 glowny

Dodawanie pisemne. Dodając pisemnie dwie liczby (jedna pod drugą), zapisujemy przeniesienia do następnej kolumny, gdy suma cyfr w kolumnie (z ewentualnym przeniesieniem) jest co najmniej 10. Np. 27732+7261927732+72619 daje 4 przeniesienia.

Podaj liczbę przeniesień przy dodawaniu par liczb: 37932+1252837932+12528, 88765+1111188765+11111, 456789+222222456789+222222.

Wpisz trzy liczby oddzielone spacjami, w tej kolejności.

RekurencjaTrudne3 pkt2026 glowny

Uzupełnij tabelę. W drugiej kolumnie podaj liczbę wywołań rekurencyjnych funkcji AA dla każdej wartości nn (drugiego argumentu; pierwszy jest nieistotny). W trzeciej kolumnie podaj wyrażenie, którego wartość jest równa drugiemu argumentowi funkcji w ii-tym wywołaniu rekurencyjnym (dla 1≤i≤1\le i\le liczba wywołań).

nnliczba wywołańdrugi argument w ii-tym wywołaniu
883382i\dfrac{8}{2^i} (lub 23−i2^{3-i})
2k2^k??
2k−12^k-1??

gdzie kk jest pewną liczbą całkowitą dodatnią większą od 2.

RekurencjaŚrednie1 pkt2026 glowny

Dla funkcji A(m,n)A(m,n) z zadania 1.1 podaj wartości:

mmnnA(m,n)A(m,n)
11777777?
2⋅1062\cdot10^6256⋅106256\cdot10^6?

(Wynik możesz zapisać z użyciem mnożenia i potęgowania.)

RekurencjaŚrednie3 pkt2026 glowny

Rekurencja. Dana jest zdefiniowana rekurencyjnie funkcja A(m,n)A(m,n), gdzie mm i nn są dodatnimi liczbami całkowitymi:

A(m,n)={mn=1A(2m,n2)n>1 i n parzyste2⋅A(m,n−12)+mn>1 i n nieparzysteA(m,n)=\begin{cases} m & n=1\\ A\left(2m,\tfrac n2\right) & n>1\ \text{i}\ n\ \text{parzyste}\\ 2\cdot A\left(m,\tfrac{n-1}2\right)+m & n>1\ \text{i}\ n\ \text{nieparzyste}\end{cases}

Obliczenie A(3,9)A(3,9) wprost z definicji wymaga trzech wywołań rekurencyjnych: A(3,4)A(3,4), A(6,2)A(6,2), A(12,1)A(12,1), bo A(3,9)=2⋅A(3,4)+3=2⋅A(6,2)+3=2⋅A(12,1)+3=2⋅12+3=27A(3,9)=2\cdot A(3,4)+3=2\cdot A(6,2)+3=2\cdot A(12,1)+3=2\cdot12+3=27.

Podaj liczbę wywołań rekurencyjnych funkcji AA oraz wypisz wywołania rekurencyjne (w ostatnim wierszu podaj tylko liczbę wywołań) dla:

mmnn
3399 (przykład: 3 wywołania)
252^5252^5
10101515
112100+12^{100}+1