Linki: Algorytmy na maturze, Algorytmy z podstawy programowej
Egzamin maturalny z informatyki sprawdza, w jakim stopniu absolwent spełnia wymagania z zakresu tego przedmiotu określone w podstawie programowej kształcenia ogólnego w zakresie rozszerzonym i podstawowym. Poszczególne zadania zestawu egzaminacyjnego mogą też odnosić się do wymagań przypisanych do etapów wcześniejszych.
Poniżej przedstawiono kilka przykładowych pseudokodów z egzaminów maturalnych do przetestowania.
(z testów https://egzamin-informatyka.blogspot.com/search/label/Pseudokod)
"Na przykład dla" n ← 4
s ← 0
dla i = 1, 2, ..., n
dla j = i, i + 1, ..., n
s ← s + 1
wypisz s
funkcja f(n)
jeżeli n > 0
wypisz n
f(n-2)
wypisz n
"W wyniku wywołania" f(6) "otrzymamy ciąg 6 4 2 2 4 6."
funkcja f(n)
jeżeli n = 0
zwróć 1
w przeciwnym razie
s ← 1
i ← 0
dopóki i ≤ n-1 wykonuj
s ← s + f(i)
i ← i + 1
zwróć s
wypisz f(10)
"Po wykonaniu algorytmu dla" n←123 "zmienna w przyjmuje wartość 6."
w ← 0
dopóki n ≠ 0 wykonuj
w ← w + (n mod 10)
n ← n div 10
wypisz w
funkcja Rek(n)
jeżeli(n > 0)
Rek(n-1)
wypisz n
Rek(5)
funkcja F(n)
jeżeli n = 1
zwróć 1
w przeciwnym razie
zwróć F(n div 2) + 1
wypisz F(9)
Wyróżniamy dwa typy: analiza algotytmu i algorytmizacja Przykładowe rozwiązania I wersja II wersja (poprawiona)
https://egzamin-informatyka.blogspot.com/search/label/Algorytmizacja
https://egzamin-informatyka.blogspot.com/search/label/AnalizaAlgorytmu
Zadanie 1. n-permutacja EINP-R1-100-2205
http://egzamin-informatyka.blogspot.com/2022/05/zadanie-1-n-permutacja-0-6.html
dla i = 1, 2, ..., n
B[i] ← 0
k ← 0
dla i = 1, 2, ..., n
jeżeli A[i] ≤ n
B[A[i]] ← B[A[i]]+1
w przeciwnym razie
k ← k + 1
dla i = 1, 2, ..., n
jeżeli B[i]>1
k ← k + B[i] - 1
wypisz k
Zadanie 2. Analiza algorytmu z EINP-R1-100-2105
https://egzamin-informatyka.blogspot.com/2021/05/zadanie-2-analiza-algorytmu-06.html
funkcja d(x)
n ← n + 1
jeżeli n < dlugosc(T)
T[n] ← x
w przeciwnym razie
DODAJ (T, x)
s ← n
dopóki (((s div 2) ≥ 1) oraz (T[s] > T[s div 2])) wykonuj
pom ← T[s]
T[s] ← T[s div 2]
T[s div 2] ← pom
s ← s div 2
wypisz "T po wykonaniu d(x) "+T
n←4 T←[26, 3, 5, -4] x←5
d(x)
Zadanie 1. Cyfrowe dopełnienie z EINP-R1-100-2105
"Cyfrowym dopełnieniem liczby" n ← 2021 "jest liczba 7978."
potega ← 1
d ← 0
dopóki n > 0 wykonuj
cyfra ← n mod 10
n ← n div 10
cyfra ← 9 - cyfra
d ← d + potega * cyfra
potega ← potega * 10
wypisz d
https://egzamin-informatyka.blogspot.com/2021/05/zadanie-1-cyfrowe-dopenienie-06.html
n ← 2021
d ← 0
suma ← 0
kopia ← n
dopóki kopia > 0 wykonuj
kopia ← kopia div 10
suma ← suma * 10 + 9
d ← suma - n
wypisz d
Zadanie 2. Rekurencja z MIN-R1_1P-172
http://egzamin-informatyka.blogspot.com/2017/05/zadanie-2-rekurencja-06.html
funkcja licz(x)
jeżeli x = 1
wypisz 1
w przeciwnym razie
w ← licz(x div 2)
jeżeli x mod 2 = 1
wypisz w + 1
w przeciwnym razie
wypisz w - 1
licz(11)
Wersja iteracyjna:
funkcja potega(a, x, M)
jeżeli x = 0
zwróć 1
jeśli x mod 2 = 0
w ← potega(a, x div 2, M)
zwróć w * w mod M
jeśli x mod 2 = 1
w ← potega(a, (x - 1) div 2, M)
zwróć a * w * w mod M
wypisz potega(2, 5, 7)
Wersja rekurecyjna:
funkcja potega(a, x, M)
w ← 1
z ← a
dopóki x > 0 wykonuj
jeżeli x mod 2 = 1
w ← w * z mod M
z ← z * z mod M
x ← x div 2
zwróć w
wypisz potega(2, 5, 7)
"Przykładowo dla" A ← [4, 2, 1, 5, 3] n ← długość(A)
dla i = 2, 3, ..., n
v ← A[i]
j ← i
dopóki (j > 1) oraz (v < A[j - 1]) wykonuj
A[j] ← A[j - 1]
j ← j - 1
A[j] ← v
wypisz "A = " + A
A ← [2,4,6,8,10,9,7,5,3,1]
funkcja W(j)
jeśli j > 1
jeśli A[j] < A[j-1]
v ← A[j]
A[j] ← A[j-1]
A[j-1] ← v
W(j-1)
zwróć A
wypisz W(7)
| Operatory | Łączność | Opis |
|---|---|---|
← |
Prawy | Przypisanie |
lub |
Lewy | Logiczne lub |
oraz |
Lewy | Logiczne i |
nie |
Lewy | Logiczne nie |
=, ≠ |
Lewy | Równości |
<, ≤, >, ≥ |
Lewy | Porównania |
+, - |
Lewy | Dodawania (w tym konatenacji) |
*, /, mod, div |
Lewy | Mnożenia |
- |
Prawy | Negacja jednoargumentowa |
..(..), ..[..] |
Lewy | Połączenia lub indeksy |
(...) |
Lewy | Nawiasy |
Uwaga: W niektórych pseudokodach maturalnych (starszych) można spotkać operator przypisania w postaci ":=" lub "=" oraz operator zamiany "↔". Edytor umożliwia ich stosowanie ale nie jest to zalecane.
Jest to nieco bardziej sformalizowana wersja gramatyki.
program : instrukcje ;
instrukcje : instrukcja* ;
blok : "wcięcie" instrukcje "zmiana poziomu" ;
instrukcja : exprStmt
| funkcjaStmt
| ifStmt
| repeatStmt
| returnStmt ;
exprStmt : expr ;
ifStmt : "jezeli" expr blok ( "wprzeciwnymrazie" blok )? ;
repeatStmt : "dopoki" expr "wykonuj" blok ;
dlaStmt : "dla" expr blok ;
procedureStmt : "funkcja" ID "(" argumenty? ")" blok ;
argumenty : ID ( "," ID )* ;
returnStmt : "zwroc" expr ;
expr : ( ID | ( call "[" expr "]" ) ) ( "←" expr )
| or ;
or : and ( "lub" and )* ;
and : not ( "oraz" not )* ;
not : ( "nie" )? equality ;
equality : comparison ( ( "=" | "≠" ) comparison )* ;
comparison : arithmetic ( ( ">" | "≥" | "<" | "≤" ) arithmetic )* ;
arithmetic : term ( ( "+" | "-" ) term )* ;
term : czynnik ( ( "*" | "/" | "mod" | "div" ) czynnik )* ;
czynnik : ( "-" )? call ;
call : primary ( ( "(" exprList? ")" ) | ( "[" expr "]" ) )* ;
primary : NUMBER
| ID
| STRING
| "[" exprList? "]"
| "(" expr ")" ;
exprList : expr ( "," expr )* ;
NUMBER : CYFRA+ ;
ID : LITERA ( LITERA | CYFRA )* ;
STRING : '"' [^"]* '"' ;
CYFRA : [0-9] ;
LITERA : [a-zA-Z_] ;
Uwaga: Instrukcja bloku jest realizowana przez wcięcia wykonywane spacją i powinny być na tym samym poziomie (zaleca się minimum 2 spacje na poziom). Łączenie łańcuchów (konatenacja) jest relizowana za pomocą operatora "+" z domyślą konwersją typu.