{"id":"informatyka-2005-maj-matura-rozszerzona-2/zad/5","paper_id":"informatyka-2005-maj-matura-rozszerzona-2","number":"5","points":null,"ptype":"open","subject":"informatyka","category":"matura","year":2005,"month":"maj","level":"rozszerzona","text":"Zadanie 5. Najlepsze sumy, najpopularniejsze elementy. (20 pkt)\nNajlepszą sumą ciągu liczb a1, a2, , an nazywamy największą wartość wśród sum złożonych\nz sąsiednich elementów tego ciągu. Na przykład dla ciągu: 1, 2, -5, 7 mamy następujące\nsumy:\n1, 1+2 = 3, 1+2+(-5) = -2, 1+2+(-5)+7 = 5, 2, 2+(-5) = -3, 2+(-5)+7 = 4, -5, -5+7 = 2, 7.\nZatem najlepszą sumą jest 7 (zwróć uwagę, że jeden element też uznajemy za sumę).\nDo oceny oddajesz:\nNa nośniku WYNIKI dokument tekstowy Raport5 zawierający odpowiedzi do punktów a), b), c).\nWykonaj poniższe polecenia.\na) Dany jest następujący ciąg liczb całkowitych: 1, -2, 6, -5, 7, -3. Wyznacz najlepszą sumę\ndla tego ciągu i wpisz poniżej jej wartość:\nNajlepsza suma:\nCzy na podstawie uzyskanego wyniku można podać wartość najlepszej sumy dla ciągu:\n1, -2, 2, 2, 2, -5, 3, 3, 1, -3.\nDo oceny oddajesz w dokumencie Raport5 wartości najlepszej sumy dla ciągu oraz\nodpowiedź z uzasadnieniem na powyższe pytanie.\nb) Zaproponuj algorytm wyznaczania najlepszej sumy dla dowolnego ciągu liczb\ncałkowitych. Na jego podstawie napisz program do obliczenia najlepszych sum ciągów\nliczb podanych w plikach dane5-1.txt, dane5-2.txt, dane5-3.txt (znajdującym się na\nnośniku DANE). Wpisz poniżej najlepsze sumy dla poszczególnych ciągów:\nNajlepsza suma dla dane5-1.txt\nNajlepsza suma dla dane5-2.txt\nNajlepsza suma dla dane5-3.txt\nDo oceny oddajesz także w dokumencie Raport5:\n• opis algorytmu zawierającego odpowiednie fragmenty kodu Twojego programu,\n• wartości najlepszych sum dla poszczególnych plików, które wpisałeś do powyższej\ntabeli.\nc) Wyznacz „najpopularniejszy” element w ciągu, czyli element występujący największą\nliczbę razy. Zaprojektuj jak najszybszy algorytm wyznaczania najpopularniejszego\nelementu ciągu oraz oszacuj liczbę wykonywanych przez niego operacji (czas działania)\njako funkcję od liczby elementów w ciągu. Zaprogramuj swój algorytm i zastosuj go do\nciągów znajdujących się w plikach dane5-1.txt, dane5-2.txt, dane5-3.txt. W przypadku,\ngdy w ciągu jest więcej niż jeden najpopularniejszy element, jako wynik podajemy\ndowolny z nich. Na przykład dla ciągu 1, 3, 5, 1, 3 poprawną odpowiedzią jest zarówno\n1, jak i 3 (oba elementy występują dwa razy). Wpisz poniżej najpopularniejsze elementy\ndla poszczególnych ciągów:\n5\nArkusz II\nNajpopularniejszy element w dane5-1.txt\nNajpopularniejszy element w dane5-2.txt\nNajpopularniejszy element w dane5-3.txt\nDo oceny oddajesz w dokumencie Raport5:\n• najpopularniejsze elementy w plikach dane5-1.txt, dane5-2.txt, dane5-3.txt\numieszczone w tabeli czytelnie prezentującej te wyniki,\n• opis algorytmu zawierającego odpowiednie fragmenty kodu Twojego programu\noraz oszacowanie czasu jego działania.\nPunktacja:\nCzęść zadania\nMaks.\na)\n4\nb)\n8\nc)\n8\nRazem\n20\n6\nArkusz II","answer":"a) najlepsza suma = 8 dla obu podanych ciągów; b),c) algorytmy podane, ale wyniki dla dane5-*.txt nieznane (plik poza korpusem)","answer_text":null,"solution":"Brak oficjalnego klucza CKE dla Arkusza II w dostępnym korpusie (plik *-odpowiedzi\nzawiera model odpowiedzi tylko dla Arkusza I). Podpunkt a) jest samodzielny (podany wprost\nciąg liczb), więc policzyłem go; podpunkty b) i c) wymagają zawartości plików dane5-1.txt,\ndane5-2.txt, dane5-3.txt z nośnika DANE, których nie ma w tym korpusie — konkretnych\nwyników liczbowych dla tych plików nie da się więc podać.\n\na) (4 pkt) Dla ciągu 1, -2, 6, -5, 7, -3: najlepsza suma = 8 (podciąg 6, -5, 7: 6-5+7=8).\nDla ciągu 1, -2, 2, 2, 2, -5, 3, 3, 1, -3: najlepsza suma = 8 (podciąg 2,2,2,-5,3,3,1: 2+2+2-5+3+3+1=8).\nTak, na podstawie samego wyniku dla pierwszego ciągu NIE można wprost wywnioskować wartości\nnajlepszej sumy dla innego, niezwiązanego ciągu — każdy ciąg trzeba przeanalizować osobno\n(przypadkowa równość obu wyników w tym przykładzie to zbieg okoliczności, nie prawidłowość\nogólna).\n\nb) (8 pkt) Algorytm wyznaczania najlepszej sumy (algorytm Kadane'a, liniowy O(n)):\nbest ← a[1]; biezaca ← a[1]\ndla i od 2 do n wykonuj\nbiezaca ← max(a[i], biezaca + a[i])\nbest ← max(best, biezaca)\nwypisz best\nKonkretne wartości najlepszych sum dla dane5-1.txt, dane5-2.txt, dane5-3.txt są NIEZNANE —\npliki te nie znajdują się w korpusie źródłowym.\n\nc) (8 pkt) Algorytm wyznaczania najpopularniejszego elementu (elementu o największej liczbie\nwystąpień) w czasie O(n log n): posortuj ciąg, następnie jednym przebiegiem policz długości\nmaksymalnych bloków jednakowych elementów i zapamiętaj element o najdłuższym bloku\n(przy remisie zwróć dowolny z nich) — sortowanie O(n log n) dominuje, przejście liniowe O(n).\n(Alternatywnie: tablica haszująca licząca wystąpienia, oczekiwany czas O(n), kosztem pamięci\nO(n).) Konkretne najpopularniejsze elementy dla dane5-1.txt, dane5-2.txt, dane5-3.txt są\nNIEZNANE — pliki te nie znajdują się w korpusie źródłowym.","image":"img/informatyka-2005-maj-matura-rozszerzona-2/zad-5.webp","solution_image":null,"topics":null,"page_from":4,"source":"ai","answer_source":"ai","answer_text_source":null,"solution_source":"ai","text_source":"ocr","source_label":"Informatyka · Matura · maj 2005 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Zadanie 5. Najlepsze sumy, najpopularniejsze elementy. (20 pkt)
Najlepszą sumą ciągu liczb a1, a2, , an nazywamy największą wartość wśród sum złożonych
z sąsiednich elementów tego ciągu. Na przykład dla ciągu: 1, 2, -5, 7 mamy następujące
sumy:
1, 1+2 = 3, 1+2+(-5) = -2, 1+2+(-5)+7 = 5, 2, 2+(-5) = -3, 2+(-5)+7 = 4, -5, -5+7 = 2, 7.
Zatem najlepszą sumą jest 7 (zwróć uwagę, że jeden element też uznajemy za sumę).
Do oceny oddajesz:
Na nośniku WYNIKI dokument tekstowy Raport5 zawierający odpowiedzi do punktów a), b), c).
Wykonaj poniższe polecenia.
a) Dany jest następujący ciąg liczb całkowitych: 1, -2, 6, -5, 7, -3. Wyznacz najlepszą sumę
dla tego ciągu i wpisz poniżej jej wartość:
Najlepsza suma:
Czy na podstawie uzyskanego wyniku można podać wartość najlepszej sumy dla ciągu:
1, -2, 2, 2, 2, -5, 3, 3, 1, -3.
Do oceny oddajesz w dokumencie Raport5 wartości najlepszej sumy dla ciągu oraz
odpowiedź z uzasadnieniem na powyższe pytanie.
b) Zaproponuj algorytm wyznaczania najlepszej sumy dla dowolnego ciągu liczb
całkowitych. Na jego podstawie napisz program do obliczenia najlepszych sum ciągów
liczb podanych w plikach dane5-1.txt, dane5-2.txt, dane5-3.txt (znajdującym się na
nośniku DANE). Wpisz poniżej najlepsze sumy dla poszczególnych ciągów:
Najlepsza suma dla dane5-1.txt
Najlepsza suma dla dane5-2.txt
Najlepsza suma dla dane5-3.txt
Do oceny oddajesz także w dokumencie Raport5:
• opis algorytmu zawierającego odpowiednie fragmenty kodu Twojego programu,
• wartości najlepszych sum dla poszczególnych plików, które wpisałeś do powyższej
tabeli.
c) Wyznacz „najpopularniejszy” element w ciągu, czyli element występujący największą
liczbę razy. Zaprojektuj jak najszybszy algorytm wyznaczania najpopularniejszego
elementu ciągu oraz oszacuj liczbę wykonywanych przez niego operacji (czas działania)
jako funkcję od liczby elementów w ciągu. Zaprogramuj swój algorytm i zastosuj go do
ciągów znajdujących się w plikach dane5-1.txt, dane5-2.txt, dane5-3.txt. W przypadku,
gdy w ciągu jest więcej niż jeden najpopularniejszy element, jako wynik podajemy
dowolny z nich. Na przykład dla ciągu 1, 3, 5, 1, 3 poprawną odpowiedzią jest zarówno
1, jak i 3 (oba elementy występują dwa razy). Wpisz poniżej najpopularniejsze elementy
dla poszczególnych ciągów:
5
Arkusz II
Najpopularniejszy element w dane5-1.txt
Najpopularniejszy element w dane5-2.txt
Najpopularniejszy element w dane5-3.txt
Do oceny oddajesz w dokumencie Raport5:
• najpopularniejsze elementy w plikach dane5-1.txt, dane5-2.txt, dane5-3.txt
umieszczone w tabeli czytelnie prezentującej te wyniki,
• opis algorytmu zawierającego odpowiednie fragmenty kodu Twojego programu
oraz oszacowanie czasu jego działania.
Punktacja:
Część zadania
Maks.
a)
4
b)
8
c)
8
Razem
20
6
Arkusz II

","solutions":[{"source":"ai","label":"AI","kind":"text","html":"

Brak oficjalnego klucza CKE dla Arkusza II w dostępnym korpusie (plik *-odpowiedzi
zawiera model odpowiedzi tylko dla Arkusza I). Podpunkt a) jest samodzielny (podany wprost
ciąg liczb), więc policzyłem go; podpunkty b) i c) wymagają zawartości plików dane5-1.txt,
dane5-2.txt, dane5-3.txt z nośnika DANE, których nie ma w tym korpusie — konkretnych
wyników liczbowych dla tych plików nie da się więc podać.

\n

a) (4 pkt) Dla ciągu 1, -2, 6, -5, 7, -3: najlepsza suma = 8 (podciąg 6, -5, 7: 6-5+7=8).
Dla ciągu 1, -2, 2, 2, 2, -5, 3, 3, 1, -3: najlepsza suma = 8 (podciąg 2,2,2,-5,3,3,1: 2+2+2-5+3+3+1=8).
Tak, na podstawie samego wyniku dla pierwszego ciągu NIE można wprost wywnioskować wartości
najlepszej sumy dla innego, niezwiązanego ciągu — każdy ciąg trzeba przeanalizować osobno
(przypadkowa równość obu wyników w tym przykładzie to zbieg okoliczności, nie prawidłowość
ogólna).

\n

b) (8 pkt) Algorytm wyznaczania najlepszej sumy (algorytm Kadane'a, liniowy O(n)):
best ← a[1]; biezaca ← a[1]
dla i od 2 do n wykonuj
biezaca ← max(a[i], biezaca + a[i])
best ← max(best, biezaca)
wypisz best
Konkretne wartości najlepszych sum dla dane5-1.txt, dane5-2.txt, dane5-3.txt są NIEZNANE —
pliki te nie znajdują się w korpusie źródłowym.

\n

c) (8 pkt) Algorytm wyznaczania najpopularniejszego elementu (elementu o największej liczbie
wystąpień) w czasie O(n log n): posortuj ciąg, następnie jednym przebiegiem policz długości
maksymalnych bloków jednakowych elementów i zapamiętaj element o najdłuższym bloku
(przy remisie zwróć dowolny z nich) — sortowanie O(n log n) dominuje, przejście liniowe O(n).
(Alternatywnie: tablica haszująca licząca wystąpienia, oczekiwany czas O(n), kosztem pamięci
O(n).) Konkretne najpopularniejsze elementy dla dane5-1.txt, dane5-2.txt, dane5-3.txt są
NIEZNANE — pliki te nie znajdują się w korpusie źródłowym.

"}]}