Matura 2005 — maj, poziom rozszerzony
ARKUSZ IARKUSZ IIDANEODPOWIEDZI IODPOWIEDZI II
Arkusz I
1a
Treść zadania
Zadanie 1 (szeregi nieskończone). Wartość ln 2 można przybliżać sumą nieskończoną: ln 2 = 2/3 · (1 + 1/3·1/9 + 1/5·1/9² + 1/7·1/9³ + 1/9·1/9⁴ + ...). Oznaczmy l₀ = 2/3 oraz dla n ≥ 1: lₙ = 2/3 · (1 + 1/3·1/9 + ... + 1/(2n+1)·1/9ⁿ).
Wypełnij tabelę wartości lₙ dla n = 0, 1, 2, 3. Podaj zależność między lₙ a lₙ₋₁ dla n ≥ 1 oraz wzór rekurencyjny na różnicę rₙ = lₙ − lₙ₋₁ (n > 0).
from fractions import Fraction
# l0 = 2/3, l(n) = l(n-1) + 2/3 * 1/((2n+1) * 9^n)
# r(1) = 2/81, r(n) = r(n-1) * (2n-1) / ((2n+1) * 9)
l = Fraction(2, 3)
print(0, l, float(l))
for n in range(1, 4):
l = l + Fraction(2, 3) * Fraction(1, (2 * n + 1) * 9 ** n)
print(n, l, round(float(l), 6))#include <cmath>
#include <numeric>
#include <print>
int main() {
// ułamek l = licznik / mianownik (zamiast Fraction z Pythona)
long long licznik = 2, mianownik = 3;
std::println("0 {}/{} {}", licznik, mianownik, (double)licznik / mianownik);
long long potega9 = 1;
for (int n = 1; n < 4; n++) {
potega9 *= 9;
// l + 2/3 * 1/((2n+1) * 9^n) = l + 2 / (3 * (2n+1) * 9^n)
long long m = 3 * (2 * n + 1) * potega9;
licznik = licznik * m + 2 * mianownik;
mianownik = mianownik * m;
long long d = std::gcd(licznik, mianownik);
licznik /= d;
mianownik /= d;
double zaokraglone = std::round((double)licznik / mianownik * 1e6) / 1e6;
std::println("{} {}/{} {}", n, licznik, mianownik, zaokraglone);
}
}public class Zadanie {
static long nwd(long a, long b) {
return b == 0 ? a : nwd(b, a % b);
}
public static void main(String[] args) {
// ułamek l = licznik / mianownik (zamiast Fraction z Pythona)
long licznik = 2, mianownik = 3;
System.out.println("0 " + licznik + "/" + mianownik + " " + (double) licznik / mianownik);
long potega9 = 1;
for (int n = 1; n < 4; n++) {
potega9 *= 9;
// l + 2/3 * 1/((2n+1) * 9^n) = l + 2 / (3 * (2n+1) * 9^n)
long m = 3L * (2 * n + 1) * potega9;
licznik = licznik * m + 2 * mianownik;
mianownik = mianownik * m;
long d = nwd(licznik, mianownik);
licznik /= d;
mianownik /= d;
double zaokraglone = Math.round((double) licznik / mianownik * 1e6) / 1e6;
System.out.println(n + " " + licznik + "/" + mianownik + " " + zaokraglone);
}
}
}Odpowiedź: l0 = 2/3, l1 = 56/81 ≈ 0,6913, l2 = 842/1215 ≈ 0,693004, l3 = 53056/76545 ≈ 0,693135; l(n) = l(n-1) + 2/3 · 1/((2n+1)·9^n); r1 = 2/81, r(n) = r(n-1) · (2n-1)/((2n+1)·9)
↑Arkusz I
1b
Treść zadania
Na podstawie wzoru z zadania 1 (lₙ = lₙ₋₁ + 2/3 · 1/((2n+1)·9ⁿ)) podaj algorytm ze specyfikacją (lista kroków, schemat blokowy lub program), który dla danej liczby ε > 0 oblicza przybliżoną wartość ln 2, sumując jak najmniej wyrazów — tak, aby różnica między dwoma ostatnimi przybliżeniami była mniejsza niż ε.
import math
def ln2(eps):
# Dane: eps > 0, Wynik: przybliżona wartość ln 2
n = 1
r = 2 / 81 # różnica l1 - l0
l = 2 / 3 + r # l1
while r >= eps:
n += 1
r = r * (2 * n - 1) / ((2 * n + 1) * 9)
l = l + r
return l
for eps in [0.1, 0.001, 0.000001, 0.000000001]:
print(eps, ln2(eps), math.log(2))#include <cmath>
#include <print>
double ln2(double eps) {
// Dane: eps > 0, Wynik: przybliżona wartość ln 2
int n = 1;
double r = 2.0 / 81; // różnica l1 - l0
double l = 2.0 / 3 + r; // l1
while (r >= eps) {
n++;
r = r * (2 * n - 1) / ((2 * n + 1) * 9);
l = l + r;
}
return l;
}
int main() {
for (double eps : {0.1, 0.001, 0.000001, 0.000000001})
std::println("{} {} {}", eps, ln2(eps), std::log(2.0));
}public class Zadanie {
static double ln2(double eps) {
// Dane: eps > 0, Wynik: przybliżona wartość ln 2
int n = 1;
double r = 2.0 / 81; // różnica l1 - l0
double l = 2.0 / 3 + r; // l1
while (r >= eps) {
n++;
r = r * (2 * n - 1) / ((2 * n + 1) * 9);
l = l + r;
}
return l;
}
// liczba w zapisie jak w Pythonie (1e-06 zamiast javowego 1.0E-6)
static String zapis(double x) {
String s = Double.toString(x);
if (!s.contains("E")) return s;
String[] czesci = s.split("E");
String mantysa = czesci[0].endsWith(".0") ? czesci[0].substring(0, czesci[0].length() - 2) : czesci[0];
int wykladnik = Integer.parseInt(czesci[1]);
return mantysa + "e" + (wykladnik < 0 ? "-" : "+") + String.format("%02d", Math.abs(wykladnik));
}
public static void main(String[] args) {
for (double eps : new double[]{0.1, 0.001, 0.000001, 0.000000001})
System.out.println(zapis(eps) + " " + ln2(eps) + " " + Math.log(2));
}
}Odpowiedź: algorytm sumuje kolejne wyrazy r(n), dopóki różnica dwóch ostatnich przybliżeń (czyli r(n)) nie jest mniejsza niż ε; wynik to ostatnie przybliżenie l(n).
↑Arkusz I
2a
Treść zadania
Zadanie 2 (ewolucja). Na planecie MLAP organizm to napis z wielkich liter. Nowy organizm to A. Po każdym roku życia każda litera zostaje zastąpiona dwiema literami według reguł postaci L → F S. Rozważamy reguły: A → BC, A → CD, B → AD, C → BA, D → AA, D → BB. Organizmy roczne to BC lub CD, dwuletnie np. ADBA, BAAA, BABB. Dwa organizmy są odróżnialne, gdy odpowiadające im napisy są różne.
Wypisz wszystkie odróżnialne organizmy trzyletnie, które można otrzymać z organizmu dwuletniego ADBA.
reguly = [("A", "BC"), ("A", "CD"), ("B", "AD"), ("C", "BA"), ("D", "AA"), ("D", "BB")]
def nastepne_pokolenie(organizm):
wyniki = [""]
for litera in organizm:
nowe = []
for poczatek in wyniki:
for lewa, prawa in reguly:
if lewa == litera:
nowe.append(poczatek + prawa)
wyniki = nowe
return sorted(set(wyniki))
for organizm in nastepne_pokolenie("ADBA"):
print(organizm)#include <print>
#include <set>
#include <string>
#include <utility>
#include <vector>
const std::vector<std::pair<char, std::string>> reguly = {
{'A', "BC"}, {'A', "CD"}, {'B', "AD"}, {'C', "BA"}, {'D', "AA"}, {'D', "BB"}};
std::set<std::string> nastepne_pokolenie(const std::string& organizm) {
std::vector<std::string> wyniki = {""};
for (char litera : organizm) {
std::vector<std::string> nowe;
for (const auto& poczatek : wyniki)
for (const auto& [lewa, prawa] : reguly)
if (lewa == litera)
nowe.push_back(poczatek + prawa);
wyniki = nowe;
}
return std::set<std::string>(wyniki.begin(), wyniki.end()); // posortowane, bez powtórzeń
}
int main() {
for (const auto& organizm : nastepne_pokolenie("ADBA"))
std::println("{}", organizm);
}import java.util.*;
public class Zadanie {
static final String[][] reguly = {
{"A", "BC"}, {"A", "CD"}, {"B", "AD"}, {"C", "BA"}, {"D", "AA"}, {"D", "BB"}};
static TreeSet<String> nastepnePokolenie(String organizm) {
List<String> wyniki = List.of("");
for (char litera : organizm.toCharArray()) {
var nowe = new ArrayList<String>();
for (String poczatek : wyniki)
for (String[] r : reguly)
if (r[0].charAt(0) == litera)
nowe.add(poczatek + r[1]);
wyniki = nowe;
}
return new TreeSet<>(wyniki); // posortowane, bez powtórzeń
}
public static void main(String[] args) {
for (String organizm : nastepnePokolenie("ADBA"))
System.out.println(organizm);
}
}Odpowiedź: BCAAADBC, CDAAADBC, BCBBADBC, CDBBADBC, BCAAADCD, CDAAADCD, BCBBADCD, CDBBADCD
↑Arkusz I
2b
Treść zadania
Organizmy z zadania 2 podwajają długość co rok (start: jedna litera A). Podaj sposób sprawdzenia, czy dla danej liczby naturalnej n ≥ 1 mogą istnieć organizmy o długości n, a jeśli tak — ustal wiek takiego organizmu. Podaj też, ile poprawnych długości organizmów leży w przedziale (n, m] dla liczb naturalnych n < m. Odpowiedź uzasadnij.
def wiek(n):
# organizm o długości n istnieje tylko, gdy n jest potęgą dwójki; wiek = log2(n)
lata = 0
while n % 2 == 0:
n //= 2
lata += 1
if n == 1:
return lata
return -1 # nie ma takiego organizmu
def ile_wielkosci(n, m):
# liczba potęg dwójki w przedziale (n, m]
ile = 0
potega = 1
while potega <= m:
if potega > n:
ile += 1
potega *= 2
return ile
print(wiek(1), wiek(8), wiek(12), wiek(1024))
print(ile_wielkosci(3, 100))#include <print>
int wiek(long long n) {
// organizm o długości n istnieje tylko, gdy n jest potęgą dwójki; wiek = log2(n)
int lata = 0;
while (n % 2 == 0) {
n /= 2;
lata++;
}
if (n == 1) return lata;
return -1; // nie ma takiego organizmu
}
int ile_wielkosci(long long n, long long m) {
// liczba potęg dwójki w przedziale (n, m]
int ile = 0;
long long potega = 1;
while (potega <= m) {
if (potega > n) ile++;
potega *= 2;
}
return ile;
}
int main() {
std::println("{} {} {} {}", wiek(1), wiek(8), wiek(12), wiek(1024));
std::println("{}", ile_wielkosci(3, 100));
}public class Zadanie {
static int wiek(long n) {
// organizm o długości n istnieje tylko, gdy n jest potęgą dwójki; wiek = log2(n)
int lata = 0;
while (n % 2 == 0) {
n /= 2;
lata++;
}
if (n == 1) return lata;
return -1; // nie ma takiego organizmu
}
static int ileWielkosci(long n, long m) {
// liczba potęg dwójki w przedziale (n, m]
int ile = 0;
long potega = 1;
while (potega <= m) {
if (potega > n) ile++;
potega *= 2;
}
return ile;
}
public static void main(String[] args) {
System.out.println(wiek(1) + " " + wiek(8) + " " + wiek(12) + " " + wiek(1024));
System.out.println(ileWielkosci(3, 100));
}
}Odpowiedź: organizm o długości n istnieje wtedy i tylko wtedy, gdy n = 2^k, a jego wiek to k = log2 n; w przedziale (n, m] jest ⌊log2 m⌋ − ⌊log2 n⌋ poprawnych wielkości.
↑Arkusz I
2d
Treść zadania
Dla zbioru reguł L₁ → F₁S₁, ..., Lₚ → FₚSₚ z zadania 2 dana jest rekurencyjna funkcja sprawdź(napis, start):
jeśli długość napisu nie jest potęgą 2 → NIE
jeśli napis = start → TAK
jeśli długość napisu = 1 → NIE
podziel napis na równe połowy napis1, napis2
dla i = 1..p: jeśli Li = start oraz sprawdź(napis1, Fi) = TAK
i sprawdź(napis2, Si) = TAK → TAK
NIEUzupełnij specyfikację funkcji (czym są dane napis i start). Dla reguł A → BC, A → CD, B → AD, C → BA, D → AA, D → BB oraz napis = BCAAADCD, start = A podaj parametry wszystkich wywołań rekurencyjnych i odpowiedź, jaką zwróci funkcja.
reguly = [("A", "BC"), ("A", "CD"), ("B", "AD"), ("C", "BA"), ("D", "AA"), ("D", "BB")]
def potega_dwojki(n):
while n % 2 == 0:
n //= 2
return n == 1
def sprawdz(napis, start):
# Dane: napis - ciąg n liter, start - litera nowo powstałego organizmu
# Wynik: czy napis to organizm, który można uzyskać z organizmu start
print("sprawdz(", napis, ",", start, ")")
if not potega_dwojki(len(napis)):
return False
if napis == start:
return True
if len(napis) == 1:
return False
polowa = len(napis) // 2
napis1 = napis[:polowa]
napis2 = napis[polowa:]
for lewa, prawa in reguly:
if lewa == start:
wynik1 = sprawdz(napis1, prawa[0])
wynik2 = sprawdz(napis2, prawa[1])
if wynik1 and wynik2:
return True
return False
print(sprawdz("BCAAADCD", "A"))#include <print>
#include <string>
#include <utility>
#include <vector>
const std::vector<std::pair<std::string, std::string>> reguly = {
{"A", "BC"}, {"A", "CD"}, {"B", "AD"}, {"C", "BA"}, {"D", "AA"}, {"D", "BB"}};
bool potega_dwojki(size_t n) {
while (n % 2 == 0) n /= 2;
return n == 1;
}
bool sprawdz(const std::string& napis, const std::string& start) {
// Dane: napis - ciąg n liter, start - litera nowo powstałego organizmu
// Wynik: czy napis to organizm, który można uzyskać z organizmu start
std::println("sprawdz( {} , {} )", napis, start);
if (!potega_dwojki(napis.size())) return false;
if (napis == start) return true;
if (napis.size() == 1) return false;
size_t polowa = napis.size() / 2;
std::string napis1 = napis.substr(0, polowa);
std::string napis2 = napis.substr(polowa);
for (const auto& [lewa, prawa] : reguly) {
if (lewa == start) {
bool wynik1 = sprawdz(napis1, prawa.substr(0, 1));
bool wynik2 = sprawdz(napis2, prawa.substr(1, 1));
if (wynik1 && wynik2) return true;
}
}
return false;
}
int main() {
std::println("{}", sprawdz("BCAAADCD", "A") ? "True" : "False");
}public class Zadanie {
static final String[][] reguly = {
{"A", "BC"}, {"A", "CD"}, {"B", "AD"}, {"C", "BA"}, {"D", "AA"}, {"D", "BB"}};
static boolean potegaDwojki(int n) {
while (n % 2 == 0) n /= 2;
return n == 1;
}
static boolean sprawdz(String napis, String start) {
// Dane: napis - ciąg n liter, start - litera nowo powstałego organizmu
// Wynik: czy napis to organizm, który można uzyskać z organizmu start
System.out.println("sprawdz( " + napis + " , " + start + " )");
if (!potegaDwojki(napis.length())) return false;
if (napis.equals(start)) return true;
if (napis.length() == 1) return false;
int polowa = napis.length() / 2;
String napis1 = napis.substring(0, polowa);
String napis2 = napis.substring(polowa);
for (String[] r : reguly) {
if (r[0].equals(start)) {
boolean wynik1 = sprawdz(napis1, r[1].substring(0, 1));
boolean wynik2 = sprawdz(napis2, r[1].substring(1, 2));
if (wynik1 && wynik2) return true;
}
}
return false;
}
public static void main(String[] args) {
System.out.println(sprawdz("BCAAADCD", "A") ? "True" : "False");
}
}Odpowiedź: wywołania: (BCAAADCD, A), (BCAA, B), (BC, A), (B, B), (C, C), (AA, D), (A, A), (A, A), (ADCD, C), (AD, B), (A, A), (D, D), (CD, A), (C, B), (D, C), (C, C), (D, D); wynik: TAK
↑Arkusz II
4a
Treść zadania
Zadanie 4 (projekt). Licencja na oprogramowanie do przetwarzania N gigabajtów danych kosztuje 0,01·N w firmie D1 oraz 0,5·√N w firmie D2. Czas obliczeń programu D1 wynosi f(N) = 10m³ + 7m² + 0,1m + 0,1 sekund, gdzie m = 0,0001·N; program D2 jest pięciokrotnie wolniejszy (5·f(N)). Koszt obliczeń jest równy ich czasowi, więc koszt wyboru D1 to 0,01N + f(N), a D2 to 0,5√N + 5f(N). Wybieramy zawsze tańsze rozwiązanie.
Wyznacz, dla jakich N ∈ [1, 7000] należy wybrać D1, a dla jakich D2 (każdy przedział w osobnym wierszu, końce z dokładnością do 0,01). Podaj też w tabeli koszt realizacji projektu przy wyborze D1 i D2 dla N = 100, 1000 i 5000 (zaokrąglony do 0,01). Wyniki umieść w dokumencie Raport4.
import math
def f(N):
m = 0.0001 * N
return 10 * m ** 3 + 7 * m ** 2 + 0.1 * m + 0.1
def koszt_d1(N):
return 0.01 * N + f(N)
def koszt_d2(N):
return 0.5 * math.sqrt(N) + 5 * f(N)
# sprawdzamy wszystkie N z [1, 7000] z krokiem 0,01
poprzednia = None
for k in range(100, 700001):
N = k / 100
firma = "D1" if koszt_d1(N) <= koszt_d2(N) else "D2"
if firma != poprzednia:
print("od N =", N, "wybieramy", firma)
poprzednia = firma
print()
print("N", "D1", "D2")
for N in [100, 1000, 5000]:
print(N, round(koszt_d1(N), 2), round(koszt_d2(N), 2))#include <cmath>
#include <format>
#include <print>
#include <string>
double f(double N) {
double m = 0.0001 * N;
return 10 * std::pow(m, 3) + 7 * std::pow(m, 2) + 0.1 * m + 0.1;
}
double koszt_d1(double N) { return 0.01 * N + f(N); }
double koszt_d2(double N) { return 0.5 * std::sqrt(N) + 5 * f(N); }
double zaokraglij2(double x) { return std::round(x * 100) / 100; }
// liczba rzeczywista wypisana jak w Pythonie (1.0 zamiast 1)
std::string zapis(double x) {
std::string s = std::format("{}", x);
if (s.find_first_of(".e") == std::string::npos) s += ".0";
return s;
}
int main() {
// sprawdzamy wszystkie N z [1, 7000] z krokiem 0,01
std::string poprzednia = "";
for (int k = 100; k <= 700000; k++) {
double N = k / 100.0;
std::string firma = koszt_d1(N) <= koszt_d2(N) ? "D1" : "D2";
if (firma != poprzednia) {
std::println("od N = {} wybieramy {}", zapis(N), firma);
poprzednia = firma;
}
}
std::println();
std::println("N D1 D2");
for (int N : {100, 1000, 5000})
std::println("{} {} {}", N, zaokraglij2(koszt_d1(N)), zaokraglij2(koszt_d2(N)));
}public class Zadanie {
static double f(double N) {
double m = 0.0001 * N;
return 10 * Math.pow(m, 3) + 7 * Math.pow(m, 2) + 0.1 * m + 0.1;
}
static double kosztD1(double N) { return 0.01 * N + f(N); }
static double kosztD2(double N) { return 0.5 * Math.sqrt(N) + 5 * f(N); }
static double zaokraglij2(double x) { return Math.round(x * 100) / 100.0; }
public static void main(String[] args) {
// sprawdzamy wszystkie N z [1, 7000] z krokiem 0,01
String poprzednia = "";
for (int k = 100; k <= 700000; k++) {
double N = k / 100.0;
String firma = kosztD1(N) <= kosztD2(N) ? "D1" : "D2";
if (!firma.equals(poprzednia)) {
System.out.println("od N = " + N + " wybieramy " + firma);
poprzednia = firma;
}
}
System.out.println();
System.out.println("N D1 D2");
for (int N : new int[]{100, 1000, 5000})
System.out.println(N + " " + zaokraglij2(kosztD1(N)) + " " + zaokraglij2(kosztD2(N)));
}
}Odpowiedź: D1 dla N ∈ [1; 3617,62], D2 dla N ∈ [3617,63; 7000]
| N | D1 | D2 |
|---|---|---|
| 100 | 1,10 | 5,51 |
| 1000 | 10,19 | 16,76 |
| 5000 | 53,15 | 51,11 |
Arkusz II
4b
Treść zadania
Dla danych z zadania 4 sporządź zestawienie porównujące koszt opłat licencyjnych firmy D2 (0,5√N) z kosztem obliczeń przy wyborze D2 (5f(N)) dla N od 6000 do 9000 z krokiem 100. Zestawienie ma mieć trzy kolumny: N, koszt licencji, koszt obliczeń; dołącz wykres liniowy ilustrujący wyniki (Raport4).
import math
def f(N):
m = 0.0001 * N
return 10 * m ** 3 + 7 * m ** 2 + 0.1 * m + 0.1
print("N;licencja D2;obliczenia D2")
for N in range(6000, 9001, 100):
licencja = 0.5 * math.sqrt(N)
obliczenia = 5 * f(N)
print(N, "%.2f" % licencja, "%.2f" % obliczenia, sep=";")#include <cmath>
#include <print>
double f(double N) {
double m = 0.0001 * N;
return 10 * std::pow(m, 3) + 7 * std::pow(m, 2) + 0.1 * m + 0.1;
}
int main() {
std::println("N;licencja D2;obliczenia D2");
for (int N = 6000; N <= 9000; N += 100) {
double licencja = 0.5 * std::sqrt(N);
double obliczenia = 5 * f(N);
std::println("{};{:.2f};{:.2f}", N, licencja, obliczenia);
}
}import java.util.Locale;
public class Zadanie {
static double f(double N) {
double m = 0.0001 * N;
return 10 * Math.pow(m, 3) + 7 * Math.pow(m, 2) + 0.1 * m + 0.1;
}
public static void main(String[] args) {
System.out.println("N;licencja D2;obliczenia D2");
for (int N = 6000; N <= 9000; N += 100) {
double licencja = 0.5 * Math.sqrt(N);
double obliczenia = 5 * f(N);
// Locale.ROOT - kropka dziesiętna niezależnie od ustawień systemu
System.out.println(String.format(Locale.ROOT, "%d;%.2f;%.2f", N, licencja, obliczenia));
}
}
}Odpowiedź: 6000: licencja 38,73, obliczenia 24,20; 6100: 39,05, 25,18; 6200: 39,37, 26,18; … 9000: 47,43, 65,75 (koszt obliczeń przewyższa licencję od N = 7700).
↑Arkusz II
5a
Treść zadania
Zadanie 5. Najlepszą sumą ciągu a₁, ..., aₙ nazywamy największą wartość spośród sum kolejnych (sąsiednich) elementów ciągu; pojedynczy element też jest sumą. Np. dla ciągu 1, 2, −5, 7 najlepsza suma wynosi 7.
Wyznacz najlepszą sumę dla ciągu 1, −2, 6, −5, 7, −3. Czy na podstawie tego wyniku można podać najlepszą sumę ciągu 1, −2, 2, 2, 2, −5, 3, 3, 1, −3? Odpowiedź uzasadnij.
def najlepsza_suma(ciag):
najlepsza = ciag[0]
biezaca = 0
for x in ciag:
biezaca = max(biezaca + x, x)
najlepsza = max(najlepsza, biezaca)
return najlepsza
print(najlepsza_suma([1, -2, 6, -5, 7, -3]))
print(najlepsza_suma([1, -2, 2, 2, 2, -5, 3, 3, 1, -3]))#include <algorithm>
#include <print>
#include <vector>
int najlepsza_suma(const std::vector<int>& ciag) {
int najlepsza = ciag[0];
int biezaca = 0;
for (int x : ciag) {
biezaca = std::max(biezaca + x, x);
najlepsza = std::max(najlepsza, biezaca);
}
return najlepsza;
}
int main() {
std::println("{}", najlepsza_suma({1, -2, 6, -5, 7, -3}));
std::println("{}", najlepsza_suma({1, -2, 2, 2, 2, -5, 3, 3, 1, -3}));
}public class Zadanie {
static int najlepszaSuma(int[] ciag) {
int najlepsza = ciag[0];
int biezaca = 0;
for (int x : ciag) {
biezaca = Math.max(biezaca + x, x);
najlepsza = Math.max(najlepsza, biezaca);
}
return najlepsza;
}
public static void main(String[] args) {
System.out.println(najlepszaSuma(new int[]{1, -2, 6, -5, 7, -3}));
System.out.println(najlepszaSuma(new int[]{1, -2, 2, 2, 2, -5, 3, 3, 1, -3}));
}
}Odpowiedź: 8; drugi ciąg ma tę samą najlepszą sumę (8), bo powstał z pierwszego przez zastąpienie liczb dodatnich ciągami liczb dodatnich o tej samej sumie (6 = 2+2+2, 7 = 3+3+1).
↑Arkusz II
5b
Treść zadania
Zaproponuj algorytm wyznaczania najlepszej sumy (zadanie 5) dla dowolnego ciągu liczb całkowitych i napisz program, który obliczy najlepsze sumy ciągów zapisanych w plikach dane5-1.txt, dane5-2.txt, dane5-3.txt. Podaj wynik dla każdego pliku oraz opis algorytmu.
def najlepsza_suma(ciag):
# algorytm Kadane, czas O(n)
najlepsza = ciag[0]
biezaca = 0
for x in ciag:
biezaca = max(biezaca + x, x)
najlepsza = max(najlepsza, biezaca)
return najlepsza
for nazwa in ["dane5-1.txt", "dane5-2.txt", "dane5-3.txt"]:
with open(nazwa) as file:
ciag = [int(linia) for linia in file if linia.strip()]
print(nazwa, najlepsza_suma(ciag))#include <algorithm>
#include <fstream>
#include <print>
#include <string>
#include <vector>
long long najlepsza_suma(const std::vector<long long>& ciag) {
// algorytm Kadane, czas O(n)
long long najlepsza = ciag[0];
long long biezaca = 0;
for (long long x : ciag) {
biezaca = std::max(biezaca + x, x);
najlepsza = std::max(najlepsza, biezaca);
}
return najlepsza;
}
int main() {
for (std::string nazwa : {"dane5-1.txt", "dane5-2.txt", "dane5-3.txt"}) {
std::ifstream plik(nazwa);
std::vector<long long> ciag;
long long x;
while (plik >> x) ciag.push_back(x);
std::println("{} {}", nazwa, najlepsza_suma(ciag));
}
}import java.nio.file.*;
import java.util.*;
public class Zadanie {
static long najlepszaSuma(List<Long> ciag) {
// algorytm Kadane, czas O(n)
long najlepsza = ciag.get(0);
long biezaca = 0;
for (long x : ciag) {
biezaca = Math.max(biezaca + x, x);
najlepsza = Math.max(najlepsza, biezaca);
}
return najlepsza;
}
public static void main(String[] args) throws Exception {
for (String nazwa : List.of("dane5-1.txt", "dane5-2.txt", "dane5-3.txt")) {
var ciag = new ArrayList<Long>();
for (String linia : Files.readAllLines(Path.of(nazwa)))
if (!linia.isBlank()) ciag.add(Long.parseLong(linia.trim()));
System.out.println(nazwa + " " + najlepszaSuma(ciag));
}
}
}Odpowiedź: dane5-1.txt: 106, dane5-2.txt: 139, dane5-3.txt: 1342
↑Arkusz II
5c
Treść zadania
Najpopularniejszy element ciągu to element występujący w nim najwięcej razy (przy remisie można podać dowolny z nich, np. dla 1, 3, 5, 1, 3 poprawne są 1 i 3). Zaprojektuj jak najszybszy algorytm jego wyznaczania, oszacuj liczbę wykonywanych operacji w zależności od długości ciągu, a następnie zastosuj go do ciągów z plików dane5-1.txt, dane5-2.txt, dane5-3.txt i podaj wyniki w czytelnej tabeli.
def najpopularniejszy(ciag):
# sortowanie O(n log n), potem jedno przejście po posortowanym ciągu O(n)
ciag = sorted(ciag)
najlepszy, najwiecej = ciag[0], 0
licznik = 0
for i in range(len(ciag)):
if i > 0 and ciag[i] == ciag[i - 1]:
licznik += 1
else:
licznik = 1
if licznik > najwiecej:
najwiecej = licznik
najlepszy = ciag[i]
return najlepszy, najwiecej
for nazwa in ["dane5-1.txt", "dane5-2.txt", "dane5-3.txt"]:
with open(nazwa) as file:
ciag = [int(linia) for linia in file if linia.strip()]
print(nazwa, *najpopularniejszy(ciag))#include <algorithm>
#include <fstream>
#include <print>
#include <string>
#include <utility>
#include <vector>
std::pair<long long, int> najpopularniejszy(std::vector<long long> ciag) {
// sortowanie O(n log n), potem jedno przejście po posortowanym ciągu O(n)
std::sort(ciag.begin(), ciag.end());
long long najlepszy = ciag[0];
int najwiecej = 0, licznik = 0;
for (size_t i = 0; i < ciag.size(); i++) {
if (i > 0 && ciag[i] == ciag[i - 1])
licznik++;
else
licznik = 1;
if (licznik > najwiecej) {
najwiecej = licznik;
najlepszy = ciag[i];
}
}
return {najlepszy, najwiecej};
}
int main() {
for (std::string nazwa : {"dane5-1.txt", "dane5-2.txt", "dane5-3.txt"}) {
std::ifstream plik(nazwa);
std::vector<long long> ciag;
long long x;
while (plik >> x) ciag.push_back(x);
auto [najlepszy, najwiecej] = najpopularniejszy(ciag);
std::println("{} {} {}", nazwa, najlepszy, najwiecej);
}
}import java.nio.file.*;
import java.util.*;
public class Zadanie {
static long[] najpopularniejszy(List<Long> ciag) {
// sortowanie O(n log n), potem jedno przejście po posortowanym ciągu O(n)
ciag = new ArrayList<>(ciag);
Collections.sort(ciag);
long najlepszy = ciag.get(0);
int najwiecej = 0, licznik = 0;
for (int i = 0; i < ciag.size(); i++) {
if (i > 0 && ciag.get(i).equals(ciag.get(i - 1)))
licznik++;
else
licznik = 1;
if (licznik > najwiecej) {
najwiecej = licznik;
najlepszy = ciag.get(i);
}
}
return new long[]{najlepszy, najwiecej};
}
public static void main(String[] args) throws Exception {
for (String nazwa : List.of("dane5-1.txt", "dane5-2.txt", "dane5-3.txt")) {
var ciag = new ArrayList<Long>();
for (String linia : Files.readAllLines(Path.of(nazwa)))
if (!linia.isBlank()) ciag.add(Long.parseLong(linia.trim()));
long[] wynik = najpopularniejszy(ciag);
System.out.println(nazwa + " " + wynik[0] + " " + wynik[1]);
}
}
}Odpowiedź: dane5-1.txt: -22 (lub -15, 6, 19, 24), dane5-2.txt: -18 (lub 18), dane5-3.txt: 22; czas O(n log n)
↑