Matura 2021 — maj, poziom rozszerzony (formuła 2015)
ARKUSZ CZ. IARKUSZ CZ. IIDANEODPOWIEDZI
Treść zadania
Niech n będzie nieujemną liczbą całkowitą, której najbardziej znacząca cyfra jest większa od 0 i mniejsza od 9. Cyfrowe dopełnienie d liczby n powstaje przez zastąpienie każdej cyfry n jej uzupełnieniem do 9 (np. dla 2021 jest to 7978).
- 1.1 — Podaj czterocyfrową liczbę n, dla której |n − d| jest a) najmniejsza, b) największa.
- 1.2 — Napisz algorytm, który dla dodatniej liczby n (spełniającej warunek jak wyżej) oblicza jej cyfrowe dopełnienie d. Algorytm może używać wyłącznie zmiennych całkowitych i podstawowych operacji arytmetycznych (w tym div i mod); nie wolno korzystać z funkcji wbudowanych ani konwersji liczba ↔ napis.
def dopelnienie(n):
# 1.2 - tylko operacje na liczbach całkowitych
d = 0
potega = 1
while n > 0:
cyfra = n % 10
n = n // 10
d = d + (9 - cyfra) * potega
potega = potega * 10
return d
print(dopelnienie(2021))
# 1.1 - sprawdzamy wszystkie czterocyfrowe n z pierwszą cyfrą od 1 do 8
najmniejsza = najwieksza = 1000
for n in range(1000, 9000):
roznica = abs(n - dopelnienie(n))
if roznica < abs(najmniejsza - dopelnienie(najmniejsza)):
najmniejsza = n
if roznica > abs(najwieksza - dopelnienie(najwieksza)):
najwieksza = n
print(najmniejsza, najwieksza)#include <cstdlib>
#include <print>
int dopelnienie(int n) {
// 1.2 - tylko operacje na liczbach całkowitych
int d = 0;
int potega = 1;
while (n > 0) {
int cyfra = n % 10;
n = n / 10;
d = d + (9 - cyfra) * potega;
potega = potega * 10;
}
return d;
}
int main() {
std::println("{}", dopelnienie(2021));
// 1.1 - sprawdzamy wszystkie czterocyfrowe n z pierwszą cyfrą od 1 do 8
int najmniejsza = 1000, najwieksza = 1000;
for (int n = 1000; n < 9000; n++) {
int roznica = std::abs(n - dopelnienie(n));
if (roznica < std::abs(najmniejsza - dopelnienie(najmniejsza))) najmniejsza = n;
if (roznica > std::abs(najwieksza - dopelnienie(najwieksza))) najwieksza = n;
}
std::println("{} {}", najmniejsza, najwieksza);
}public class Zadanie {
static int dopelnienie(int n) {
// 1.2 - tylko operacje na liczbach całkowitych
int d = 0;
int potega = 1;
while (n > 0) {
int cyfra = n % 10;
n = n / 10;
d = d + (9 - cyfra) * potega;
potega = potega * 10;
}
return d;
}
public static void main(String[] args) throws Exception {
System.out.println(dopelnienie(2021));
// 1.1 - sprawdzamy wszystkie czterocyfrowe n z pierwszą cyfrą od 1 do 8
int najmniejsza = 1000, najwieksza = 1000;
for (int n = 1000; n < 9000; n++) {
int roznica = Math.abs(n - dopelnienie(n));
if (roznica < Math.abs(najmniejsza - dopelnienie(najmniejsza))) najmniejsza = n;
if (roznica > Math.abs(najwieksza - dopelnienie(najwieksza))) najwieksza = n;
}
System.out.println(najmniejsza + " " + najwieksza);
}
}Odpowiedź: 1.1: a) 4999 (lub 5000) — różnica 1; b) 1000 (lub 8999) — różnica 7999. 1.2: algorytm powyżej (dopelnienie(2021) = 7978)
↑Treść zadania
T[1..n] to tablica n liczb całkowitych (dla n = 0 pusta). Funkcja d(x) dopisuje x na końcu tablicy i przesuwa go w górę (div — dzielenie całkowite; „oraz” liczone leniwie):
d(x):
n ← n + 1
T[n] ← x
s ← n
dopóki ((s div 2) ≥ 1) oraz (T[s] > T[s div 2]) wykonuj
zamień T[s] z T[s div 2]
s ← s div 2- 2.1 — Podaj zawartość T po wykonaniu d(x) dla: T=[36,15,17,3], x=−5 oraz T=[27,6,13,4,−3,−2,−3], x=30. (Przykład: [26,3,5,−4], x=5 → [26,5,5,−4,3].)
- 2.2 — Podaj zawartość T po kolejnych wywołaniach d z argumentami 6, −4, 12, 27, 26, 8, zaczynając od pustej tablicy.
- 2.3 — Do pustej tablicy wstawiono kolejno liczby 1, 2, …, k−1, a potem wywołano d(k). Podaj, ile razy sprawdzany jest warunek pętli „dopóki” podczas d(k) dla wartości k podanych w tabeli arkusza (np. dla k = 4 — 3 razy).
def d(T, x):
# T[0] nieużywane - tablica indeksowana od 1, jak w treści
# zwraca liczbę sprawdzeń warunku pętli dopóki
T.append(x)
s = len(T) - 1
sprawdzenia = 0
while True:
sprawdzenia += 1
if not (s // 2 >= 1 and T[s] > T[s // 2]):
break
T[s], T[s // 2] = T[s // 2], T[s]
s = s // 2
return sprawdzenia
# 2.1
for T, x in [([26, 3, 5, -4], 5), ([36, 15, 17, 3], -5), ([27, 6, 13, 4, -3, -2, -3], 30)]:
T = [None] + T
d(T, x)
print(T[1:])
# 2.2
T = [None]
for x in [6, -4, 12, 27, 26, 8]:
d(T, x)
print(T[1:])
# 2.3
for k in [4, 16, 1025]:
T = [None]
for x in range(1, k):
d(T, x)
print(k, d(T, k))#include <print>
#include <utility>
#include <vector>
// T[0] nieużywane - tablica indeksowana od 1, jak w treści
// zwraca liczbę sprawdzeń warunku pętli dopóki
int d(std::vector<int>& T, int x) {
T.push_back(x);
int s = T.size() - 1;
int sprawdzenia = 0;
while (true) {
sprawdzenia++;
if (!(s / 2 >= 1 && T[s] > T[s / 2])) break;
std::swap(T[s], T[s / 2]);
s = s / 2;
}
return sprawdzenia;
}
void wypisz(const std::vector<int>& T) {
std::vector<int> bez0(T.begin() + 1, T.end());
std::println("{}", bez0); // format [1, 2, 3] jak w Pythonie
}
int main() {
// 2.1
std::vector<std::vector<int>> tablice = {{26, 3, 5, -4}, {36, 15, 17, 3}, {27, 6, 13, 4, -3, -2, -3}};
int iksy[] = {5, -5, 30};
for (int t = 0; t < 3; t++) {
std::vector<int> T = {0}; // T[0] nieużywane
T.insert(T.end(), tablice[t].begin(), tablice[t].end());
d(T, iksy[t]);
wypisz(T);
}
// 2.2
std::vector<int> T = {0};
for (int x : {6, -4, 12, 27, 26, 8}) d(T, x);
wypisz(T);
// 2.3
for (int k : {4, 16, 1025}) {
std::vector<int> T = {0};
for (int x = 1; x < k; x++) d(T, x);
std::println("{} {}", k, d(T, k));
}
}import java.util.*;
public class Zadanie {
// T.get(0) nieużywane - tablica indeksowana od 1, jak w treści
// zwraca liczbę sprawdzeń warunku pętli dopóki
static int d(List<Integer> T, int x) {
T.add(x);
int s = T.size() - 1;
int sprawdzenia = 0;
while (true) {
sprawdzenia++;
if (!(s / 2 >= 1 && T.get(s) > T.get(s / 2))) break;
Collections.swap(T, s, s / 2);
s = s / 2;
}
return sprawdzenia;
}
static List<Integer> nowaTablica(Integer... elementy) {
var T = new ArrayList<Integer>();
T.add(null); // T[0] nieużywane
T.addAll(List.of(elementy));
return T;
}
public static void main(String[] args) throws Exception {
// 2.1
Integer[][] tablice = {{26, 3, 5, -4}, {36, 15, 17, 3}, {27, 6, 13, 4, -3, -2, -3}};
int[] iksy = {5, -5, 30};
for (int t = 0; t < 3; t++) {
var T = nowaTablica(tablice[t]);
d(T, iksy[t]);
System.out.println(T.subList(1, T.size()));
}
// 2.2
var T = nowaTablica();
for (int x : new int[] {6, -4, 12, 27, 26, 8}) d(T, x);
System.out.println(T.subList(1, T.size()));
// 2.3
for (int k : new int[] {4, 16, 1025}) {
var tab = nowaTablica();
for (int x = 1; x < k; x++) d(tab, x);
System.out.println(k + " " + d(tab, k));
}
}
}Odpowiedź: 2.1: 36, 15, 17, 3, −5 oraz 30, 27, 13, 6, −3, −2, −3, 4. 2.2: 27, 26, 8, −4, 12, 6. 2.3: k = 16 — 5 razy, k = 1025 — 11 razy
↑Treść zadania
Plik instrukcje.txt zawiera 2000 instrukcji automatu tworzącego napis z wielkich liter (początkowo pusty). Każda instrukcja to polecenie, spacja i jeden znak:
DOPISZ litera— dopisz literę na końcu napisu;ZMIEN litera— zamień ostatnią literę napisu na podaną;USUN 1— usuń ostatnią literę;PRZESUN litera— pierwsze od lewej wystąpienie litery zamień na następną w alfabecie (Z → A); gdy litery brak, nic nie rób.
Odpowiedzi zapisz w wyniki4.txt, poprzedzając je numerem zadania. Plik przyklad.txt (20 instrukcji) służy do testów.
- 4.1 — Podaj długość napisu po wykonaniu wszystkich instrukcji. (Przykład: 10.)
- 4.2 — Znajdź najdłuższy ciąg kolejnych instrukcji tego samego rodzaju; podaj rodzaj i długość (jest jeden taki ciąg). (Przykład: DOPISZ 5.)
- 4.3 — Podaj literę najczęściej dopisywaną instrukcją DOPISZ i liczbę jej dopisań (jest jedna taka). (Przykład: U 3.)
- 4.4 — Podaj napis powstały po wykonaniu wszystkich instrukcji. (Przykład:
ALANTURING.)
instrukcje = []
with open("instrukcje.txt") as file:
for line in file:
polecenie, znak = line.split()
instrukcje.append((polecenie, znak))
# 4.1 i 4.4 - wykonujemy wszystkie instrukcje
napis = []
for polecenie, znak in instrukcje:
if polecenie == "DOPISZ":
napis.append(znak)
elif polecenie == "ZMIEN":
napis[-1] = znak
elif polecenie == "USUN":
napis.pop()
elif polecenie == "PRZESUN":
if znak in napis:
i = napis.index(znak) # pierwsze wystąpienie od lewej
napis[i] = chr((ord(znak) - ord("A") + 1) % 26 + ord("A"))
# 4.2 - najdłuższy ciąg kolejnych instrukcji tego samego rodzaju
najdluzszy = 0
rodzaj = ""
dlugosc = 0
for i in range(len(instrukcje)):
if i > 0 and instrukcje[i][0] == instrukcje[i - 1][0]:
dlugosc += 1
else:
dlugosc = 1
if dlugosc > najdluzszy:
najdluzszy = dlugosc
rodzaj = instrukcje[i][0]
# 4.3 - najczęściej dopisywana litera
ile = {}
for polecenie, znak in instrukcje:
if polecenie == "DOPISZ":
ile[znak] = ile.get(znak, 0) + 1
litera = max(ile, key=ile.get)
with open("wyniki4.txt", "w") as wynik:
print("4.1.", len(napis), file=wynik)
print("4.2.", rodzaj, najdluzszy, file=wynik)
print("4.3.", litera, ile[litera], file=wynik)
print("4.4.", "".join(napis), file=wynik)#include <algorithm>
#include <fstream>
#include <map>
#include <string>
#include <utility>
#include <vector>
int main() {
std::vector<std::pair<std::string, char>> instrukcje;
std::ifstream plik("instrukcje.txt");
std::string polecenie;
char znak;
while (plik >> polecenie >> znak) instrukcje.push_back({polecenie, znak});
// 4.1 i 4.4 - wykonujemy wszystkie instrukcje
std::string napis;
for (auto& [polecenie, znak] : instrukcje) {
if (polecenie == "DOPISZ") {
napis += znak;
} else if (polecenie == "ZMIEN") {
napis.back() = znak;
} else if (polecenie == "USUN") {
napis.pop_back();
} else if (polecenie == "PRZESUN") {
size_t i = napis.find(znak); // pierwsze wystąpienie od lewej
if (i != std::string::npos) napis[i] = (char)((znak - 'A' + 1) % 26 + 'A');
}
}
// 4.2 - najdłuższy ciąg kolejnych instrukcji tego samego rodzaju
int najdluzszy = 0;
std::string rodzaj;
int dlugosc = 0;
for (size_t i = 0; i < instrukcje.size(); i++) {
if (i > 0 && instrukcje[i].first == instrukcje[i - 1].first)
dlugosc++;
else
dlugosc = 1;
if (dlugosc > najdluzszy) {
najdluzszy = dlugosc;
rodzaj = instrukcje[i].first;
}
}
// 4.3 - najczęściej dopisywana litera (przy remisie pierwsza dopisana, jak max w Pythonie)
std::map<char, int> ile;
std::vector<char> kolejnosc; // kolejność pierwszego pojawienia się litery
for (auto& [polecenie, znak] : instrukcje) {
if (polecenie == "DOPISZ") {
if (ile[znak] == 0) kolejnosc.push_back(znak);
ile[znak]++;
}
}
char litera = kolejnosc[0];
for (char z : kolejnosc)
if (ile[z] > ile[litera]) litera = z;
std::ofstream wynik("wyniki4.txt");
wynik << "4.1. " << napis.size() << "\n";
wynik << "4.2. " << rodzaj << " " << najdluzszy << "\n";
wynik << "4.3. " << litera << " " << ile[litera] << "\n";
wynik << "4.4. " << napis << "\n";
}import java.io.*;
import java.nio.file.*;
import java.util.*;
public class Zadanie {
public static void main(String[] args) throws Exception {
var polecenia = new ArrayList<String>();
var znaki = new ArrayList<Character>();
for (var linia : Files.readAllLines(Path.of("instrukcje.txt"))) {
var czesci = linia.trim().split("\\s+");
polecenia.add(czesci[0]);
znaki.add(czesci[1].charAt(0));
}
// 4.1 i 4.4 - wykonujemy wszystkie instrukcje
var napis = new StringBuilder();
for (int k = 0; k < polecenia.size(); k++) {
String polecenie = polecenia.get(k);
char znak = znaki.get(k);
switch (polecenie) {
case "DOPISZ" -> napis.append(znak);
case "ZMIEN" -> napis.setCharAt(napis.length() - 1, znak);
case "USUN" -> napis.deleteCharAt(napis.length() - 1);
case "PRZESUN" -> {
int i = napis.indexOf(String.valueOf(znak)); // pierwsze wystąpienie od lewej
if (i != -1) napis.setCharAt(i, (char) ((znak - 'A' + 1) % 26 + 'A'));
}
}
}
// 4.2 - najdłuższy ciąg kolejnych instrukcji tego samego rodzaju
int najdluzszy = 0;
String rodzaj = "";
int dlugosc = 0;
for (int i = 0; i < polecenia.size(); i++) {
if (i > 0 && polecenia.get(i).equals(polecenia.get(i - 1)))
dlugosc++;
else
dlugosc = 1;
if (dlugosc > najdluzszy) {
najdluzszy = dlugosc;
rodzaj = polecenia.get(i);
}
}
// 4.3 - najczęściej dopisywana litera (LinkedHashMap pamięta kolejność, jak dict w Pythonie)
var ile = new LinkedHashMap<Character, Integer>();
for (int k = 0; k < polecenia.size(); k++)
if (polecenia.get(k).equals("DOPISZ"))
ile.merge(znaki.get(k), 1, Integer::sum);
char litera = ' ';
int najwiecej = 0;
for (var e : ile.entrySet()) {
if (e.getValue() > najwiecej) {
najwiecej = e.getValue();
litera = e.getKey();
}
}
try (var wynik = new PrintWriter("wyniki4.txt")) {
wynik.println("4.1. " + napis.length());
wynik.println("4.2. " + rodzaj + " " + najdluzszy);
wynik.println("4.3. " + litera + " " + najwiecej);
wynik.println("4.4. " + napis);
}
}
}Odpowiedź: 4.1: 517; 4.2: ZMIEN 7; 4.3: Z 37; 4.4: POZNIEJMOWIONOZECZLOWIEKTENNADSZEDLODPOLNOCYODBRAMYPOWROZNIC… (początek opowiadania „Wiedźmin” A. Sapkowskiego)
↑