{"id":"informator-maturalny-informatyka-2015/zad/22","paper_id":"informator-maturalny-informatyka-2015","number":"22","points":null,"ptype":"open","subject":"informatyka","category":"informator-maturalny","year":2015,"month":null,"level":null,"text":"Zadanie 22. Bloki trójkowe (0-12)\nNiech n będzie dodatnią liczbą całkowitą i niech a1, a2, …, an będzie ciągiem nieujemnych\nliczb całkowitych. Dla pary liczb i, j takich, że 1 ≤\n≤\n≤\n, blokiem b(i,j) nazywamy\npodciąg kolejnych elementów ciągu a z pozycji od i do j, czyli ai, ai+1, …, aj. Długością\nbloku nazywamy liczbę jego elementów. O bloku, którego suma elementów jest podzielna\nprzez 3 mówimy, że jest blokiem trójkowym.\nPrzykład:\nW ciągu 0,0,2,3,2,1,2 najdłuższym blokiem trójkowym jest b(4,6) = 3,2,1.\nW plikach tekstowych bloki1.txt, bloki2.txt i bloki3.txt zapisano ciągi\nodpowiednio 1000, 30000 i 1000000 nieujemnych liczb całkowitych mniejszych od 10 000.\nW każdym pliku liczby zapisano w kolejnych wierszach, po jednej liczbie w każdym wierszu.\nDla każdego pliku z danymi wyznacz długość najdłuższego bloku trójkowego w ciągu\nzapisanym w tym pliku.\nPrzykład:\nDla danych z pliku z 7 liczbami:\n0\n0\n2\n3\n2\n1\n2\ndługość najdłuższego bloku trójkowego wynosi 3.\nDo oceny oddajesz plik(i) o nazwie(ach)\ntu wpisz nazwę/nazwy pliku/plików\nzawierający(e) komputerową realizację Twoich obliczeń oraz pliki tekstowe wyniki1.txt,\nwyniki2.txt, wyniki3.txt, gdzie każdy z nich zawiera liczbę równą długości\nnajdłuższego bloku trójkowego w ciągach zapisanych odpowiednio w plikach bloki1.txt,\nbloki2.txt i bloki3.txt.\nWymagania ogólne\nIII. Rozwiązywanie problemów i podejmowanie\ndecyzji z wykorzystaniem komputera, z zastosowaniem\npodejścia algorytmicznego.\nWymagania szczegółowe\n5. Rozwiązywanie problemów i podejmowanie decyzji\nz wykorzystaniem komputera, stosowanie podejścia\nalgorytmicznego.\nZdający:\n1) analizuje, modeluje i rozwiązuje sytuacje\nproblemowe z różnych dziedzin,\n11) opisuje podstawowe algorytmy i stosuje algorytmy\nna liczbach całkowitych,\n14) dobiera odpowiednie struktury danych\ndo realizacji algorytmu, w tym struktury dynamiczne,\n15) stosuje zasady programowania strukturalnego\ni modularnego do rozwiązywania problemu,\n76 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015\n23) stosuje podstawowe konstrukcje programistyczne\nw wybranym języku programowania, instrukcje\niteracyjne i warunkowe, rekurencję i procedury,\ninstrukcje wejścia i wyjścia, poprawnie tworzy\nstrukturę programu,\n24) dobiera najlepszy algorytm, odpowiednie\nstruktury danych i oprogramowanie do rozwiązania\npostawionego problemu,\n26) ocenia poprawność komputerowego rozwiązania\nna podstawie jego testowania.\nSchemat punktowania\nCzynność\nLiczba\npunktów\nza zadanie\nZa poprawne wyniki dla pliku 1 - 3 punkty.\nZa poprawne wyniki dla pliku 2 - 4 punkty.\nZa poprawne wyniki dla pliku 3 - 5 punktów.\n12\nZadanie 22. Bloki trójkowe (0-12) - rozwiązanie\nPliki z danymi, plik programu źródłowego oraz pliki wynikowe zawierające odpowiedzi\nznajdują się w folderze BLOKI TROJKOWE.\nKomentarz\nUważny czytelnik szybko zauważy, że proste rozwiązanie jest ukryte w treści zadania.\nWystarczy przejrzeć wszystkie bloki, dla każdego bloku zsumować jego elementy, sprawdzić,\nczy otrzymana suma jest podzielna przez 3 i spośród wszystkich bloków spełniających ten\nwarunek wybrać najdłuższy. Oto fragment algorytmu zapisany w pseudo-języku C++, będący\nrealizacją tego prostego pomysłu:\nnajdluzszy = 0; // długość najdłuższego z dotychczas\n//przejrzanych bloków trójkowych\nfor (i = 1; i <= n; i++)\nfor (j = i; j <= n; j++){\n// obliczamy sumę elementów w bloku b(i,j)\nsuma = 0;\nfor (k = i; k <= j; k++)\nsuma = suma + ak; // (*)\n// sprawdzamy, czy suma jest podzielna przez 3, czyli\n// czy reszta z dzielenia suma przez 3 daje 0\nif (suma % 3 == 0){\n// jeśli suma jest podzielna przez 3 i blok b(i,j)\n// jest dłuższy od dotychczas najdłuższego bloku\n// trójkowego, to zapamiętujemy jego długość\ndl = j - i + 1;\nif (dl >= najdluzszy)\nnajdluzszy = dl;\n}\n}\n// najdluzszy jest długością najdłuższego bloku trójkowego w\n// ciągu a\nPrzykładowe zadania z rozwiązaniami 77\nJedyną dobrą cechę powyższego rozwiązania jest jego prostota i to, że w ogóle mamy\njakiekolwiek rozwiązanie. Poza tym przedstawione rozwiązanie ma same wady.\nPo pierwsze musimy pamiętać o tym, żeby arytmetyka języka programowania, którego\nużywamy, umożliwiała operowanie na liczbach pojawiających się w obliczeniach.\nZauważmy, że największa liczba jaka mogłaby się w obliczeniach dla opisanych danych\nwynosi 1 000 000 * 9 999 = 9 999 000 000. W języku programowania C++ największa\nliczba typu int ze znakiem ma wartość 2 147 483 647, a bez znaku 4 294 967 295. Tak jest,\ngdy typ int jest 32-bitowy. Dla 16-bitowego typu int odpowiednie wielkości są znacząco\nmniejsze. Oczywiście można by użyć typów pozwalających na operowanie na dużo większych\nliczbach, ale za chwilę okaże się, że nie jest to konieczne.\nDrugą wadą powyższego rozwiązania jest to, że musimy wielokrotnie przeglądać te same\nelementu ciągu, a co za tym idzie najlepiej byłoby cały ciąg wczytać do tablicy. To\nw przypadku największego pliku wymaga tablicy o 1 000 000 elementów. W przypadku\njęzyka programowania C++ i 32-bitowego typu int wymaga to 4 000 000 bajtów, czyli około\n4 gigabajtów pamięci. Nie jest to może dużo dla współczesnych komputerów, ale co gdyby\ndane liczyły nie milion, a miliard, bilion elementów?\nTrzecią wadą, chyba najistotniejszą, jest powolność zaproponowanego algorytmu.\nZastanówmy się, ile łącznie dodawań wykonamy w kroku (*). Nietrudno zauważyć, że tych\ndodawań jest tyle, ile wynosi łączna suma długości wszystkich przedziałów. Tę wielkość\nłatwo oszacować z dołu. Przedziałów o długości co najmniej n/3 jest co najmniej (n/3)2. A\nzatem łączna suma wszystkich przedziałów wynosi co najmniej (n/3)3. To dla n = 1 000 000\ndaje więcej niż 3*1016. Komputer wykonujący 109 dodawań na sekundę spędzałby na\nrozwiązywaniu naszego zadania więcej niż 3*107 sekund, a to jest więcej niż 8 tysięcy\ngodzin. To jest trochę za długo jak na czas przeznaczony na rozwiązywanie zadań\nmaturalnych!\nJeden ze sposobów poszukiwania lepszych, szybszych algorytmów polega na przyjrzeniu się\nrozwiązaniu, które już mamy w ręku i zastanowieniu się, czy nie prowadzi ono do\nwykonywania wielu zbędnych operacji. Tak jest właśnie w tym przypadku. Zauważmy, że dla\nkażdych dwóch bloków b(i,j-1) i b(i,j), różniących się tylko jednym elementem aj, liczymy\nniezależnie dwie sumy ai+ ai+1 + + aj-1 oraz ai+ ai+1 + + aj, a przecież, żeby dostać\ndrugą sumę wystarczy do pierwszej dodać tylko aj. Jaki zysk! Zamiast j-i+1 dodawań\nwykonujemy tylko jedno. Ten pomysł pozwala nam natychmiast zaproponować następujący\nalgorytm:\nnajdluzszy = 0; // długość najdłuższego z dotychczas\n//przejrzanych bloków trójkowych\nfor (i = 1; i <= n; i++){\n//liczymy sumy elementów w blokach o początkach na pozycji i\n//wartością suma będzie suma elementów ostatniego\n//przetworzonego bloku; inicjalnie suma == 0\nsuma = 0;\nfor (j = i; j <= n; j++){\n// obliczamy sumę elementów w bloku b(i,j)\n// suma jest równa sumie elementów w bloku b(i,j-1)\n// plus aj\nsuma = suma + aj; // (*)\n78 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015\n// sprawdzamy, czy suma jest podzielna przez 3, czyli\n// czy reszta z dzielenia suma przez 3 daje 0\nif (suma % 3 == 0){\n// jeśli jest podzielna przez 3 i blok b(i,j)\n// jest dłuższy od dotychczas najdłuższego bloku\n// trójkowego, to zapamiętujemy jego długość\ndl = j - i + 1;\nif (dl >= najdluzszy)\nnajdluzszy = dl;\n}\n}\n// najdluzszy jest długością najdłuższego bloku trójkowego w\n// ciągu a\nIle tym razem wykonujemy dodawań (*)? Nietrudno zauważyć, że tyle, ile jest bloków. Żeby\npoliczyć sumę elementów w bloku b(i,j), wykonujemy tylko jedno dodawanie - do sumy\nelementów z bloku b(i,j-1) dodajemy aj. Ile jest wszystkich bloków? Bloków o początku na\npozycji 1 jest n, bloków o początku na pozycji 2 jest n-1, bloków o początku na pozycji 3 jest\nn-2, itd. Tak więc bloków o początku na pozycji i jest n-i+1. Wszystkich bloków jest\nn + n-1 + + 1 = n(n-1)/2. Dla n = 1 000 000 ta wartość wynosi 499 999 500 000. A zatem\nkomputer wykonujący 109 dodawań na sekundę wykonałby nasze zadanie w około 500\nsekund, czyli w około 7 minut. Natomiast dla ciągu o długości 30 000 odpowiedź\ndostalibyśmy natychmiast.\nW przypadku rozpatrywanego zadania myślenie algorytmiczne może dać jeszcze lepsze\nefekty. Najpierw pozbądźmy się problemu dużych liczb. To łatwe. W wierszu (*) wystarczy\nsumować modulo 3. Inaczej mówiąc, w zmiennej suma zamiast sumy elementów pamiętamy\nresztę z dzielenia tej sumy przy dzieleniu przez 3. Więcej o wykonywaniu operacji\narytmetycznych modulo napisaliśmy w komentarzu do zadania Podzielność. Przy tym\npodejściu wiersz (*) miałby postać:\nsuma = (suma + aj) % 3;// (*)\nNatomiast instrukcja warunkowa if (suma % 3 == 0)przybrałaby postać:\nif (suma == 0)\nW ten sposób poradziliśmy sobie z problemem dużych liczb, ale czasowa złożoność\nobliczeniowa naszego algorytmu pozostała bez zmian. Następujące spostrzeżenia pozwolą\nprzyśpieszyć poszukiwanie najdłuższego bloku trójkowego. Dla każdego k = 1, 2, …, n\noznaczmy przez sk sumę pierwszych k elementów w ciągu a. Innymi słowy sk jest sumą\nelementów w bloku b(1,k). Dla wygody przyjmijmy, że mamy też element a0 = 0 i w naturalny\nsposób weźmy s0 = 0. Zauważmy teraz, że suma elementów w bloku b(i,j),\n1 ≤ i≤ j ≤n , jest równa sj - si-1. Dla naszych celów wartości s wystarczy liczyć modulo 3.\nW takim przypadku wartością sk może być tylko 0, 1 lub 2. Teraz najważniejsze:\nBlok b(i,j) jest blokiem trójkowym wtedy i tylko, gdy sj oraz si-1 mają taką samą wartość 0, 1,\nlub 2.\nPrzykładowe zadania z rozwiązaniami 79\nPowyższe spostrzeżenie daje bardzo proste rozwiązanie naszego zadania. Dla każdej\nwartości w = 0, 1, 2 poszukujemy pierwszej i ostatniej pozycji, dla której wartości sum s są\ntakie same. Najbardziej odległe pozycje wyznaczają długość najdłuższego bloku trójkowego.\nPozostaje jeszcze pytanie, czy zawsze taki blok istnieje. Osobom o zainteresowaniach\nbardziej matematycznych proponujemy wykazanie, że w każdym ciągu o długości co najmniej\n3 taki blok musi istnieć. Dla naszych potrzeb przyjmijmy, że blok długości 0 jest blokiem\ntrójkowym. Wówczas, jeśli wynikiem działania naszego algorytmu jest 0, oznacza to, że\nżaden blok w danym ciągu nie jest trójkowy.\nPoniżej przedstawiamy program napisany w języku C++, który konkretyzuje opisane\npowyżej idee.\n#include \n#include \nusing namespace std;\nint najdluzszy_blok(){\nint poczatki = {0,-1,-1};\n//poczatki[w] - pierwsza pozycja, dla której suma s jest\n//równa w\n// -1 oznacza, że takiej pozycjijeszcze nie\n// znaleziono\nint suma_mod_3 = 0;\nint liczba_wczytanych = 0;\nint element;\nint najdluzszy;\nwhile (cin>> element){\nliczba_wczytanych++;\nsuma_mod_3 = (suma_mod_3 + element) % 3; //(*)\nif (poczatki[suma_mod_3] == -1)\npoczatki[suma_mod_3] = liczba_wczytanych;\nelse\nnajdluzszy = max(najdluzszy, liczba_wczytanych\n- poczatki[suma_mod_3])\n}\nreturn najdluzszy;\n}\nint main(){\ncout << \"Dl bloku: \" << najdluzszy_blok() << endl;\nreturn 0;\n}\nNa koniec zauważmy, że w tym algorytmie liczba dodawań (*) wynosi tylko n i na dodatek\nnie musieliśmy najpierw wczytać całego ciągu do tablicy.\n80 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015\nOpinia KRASP o informatorach maturalnych od 2015 roku 81\nOpinia Konferencji Rektorów Akademickich Szkół Polskich\no informatorach maturalnych od 2015 roku\nKonferencja Rektorów Akademickich Szkół Polskich z wielką satysfakcją odnotowuje\nkonsekwentne dążenie systemu oświaty do poprawy jakości wykształcenia absolwentów\nszkół średnich. Konferencja z uwagą obserwuje kolejne działania Ministerstwa Edukacji\nNarodowej w tym zakresie, zdając sobie sprawę, że od skuteczności tych działań w dużym\nstopniu zależą także efekty kształcenia osiągane w systemie szkolnictwa wyższego.\nW szczególności dotyczy to kwestii właściwego przygotowania młodzieży do studiów\nrealizowanych z uwzględnieniem nowych form prowadzenia procesu kształcenia.\nPodobnie jak w przeszłości, Konferencja konsekwentnie wspiera wszystkie działania\nzmierzające do tego, by na uczelnie trafiali coraz lepiej przygotowani kandydaci na studia.\nTemu celowi służyła w szczególności pozytywna opinia Komisji Edukacji KRASP z 2008 roku\nw sprawie nowej podstawy programowej oraz uchwała Zgromadzenia Plenarnego KRASP\nz dn. 6 maja 2011 r. w sprawie nowych zasad egzaminu maturalnego.\nZ satysfakcją dostrzegamy, że ważne zmiany w egzaminie maturalnym, postulowane\nw cytowanej wyżej uchwale zostały praktycznie wdrożone przez MEN poprzez zmianę\nodpowiednich rozporządzeń.\nPrzedłożone do zaopiniowania informatory o egzaminach maturalnych opisują formę\nposzczególnych egzaminów maturalnych, przeprowadzanych na podstawie wymagań\nokreślonych w nowej podstawie programowej, a także ilustrują te wymagania wieloma\nprzykładowymi zadaniami egzaminacyjnymi.\nPo zapoznaniu się z przedłożonymi materiałami, KRASP z satysfakcją odnotowuje:\nw zakresie języka polskiego:\nwzmocnienie roli umiejętności komunikacyjnych poprzez odejście od prezentacji na\negzaminie ustnym i zastąpienie jej egzaminem ustnym, na którym zdający będzie musiał\nad hoc przygotować samodzielną wypowiedź argumentacyjną,\nrezygnację z klucza w ocenianiu wypowiedzi pisemnych,\nzwiększenie roli tekstów teoretycznoliterackich i historycznoliterackich na maturze\nrozszerzonej;\nw zakresie historii:\nkompleksowe sprawdzanie umiejętności z zakresu chronologii historycznej, analizy\ni interpretacji historycznej oraz tworzenia narracji historycznej za pomocą rozbudowanej\nwypowiedzi pisemnej na jeden z zaproponowanych tematów, łącznie pokrywających\nwszystkie epoki oraz obszary historii;\nw zakresie wiedzy o społeczeństwie:\npołożenie silniejszego akcentu na sprawdzanie umiejętności złożonych (interpretowanie\ninformacji, dostrzeganie związków przyczynowo-skutkowych) w oparciu o poszerzony\nzasób materiałów źródłowych: teksty (prawne, naukowe, publicystyczne), materiały\nstatystyczne, mapy, rysunki itp.\n82 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015\nw zakresie matematyki:\nistotne zwiększenie wymagań na poziomie rozszerzonym poprzez włączenie zadań\nz rachunku różniczkowego i pojęć zaawansowanej matematyki,\nistotne poszerzenie wymagań z zakresu kombinatoryki oraz teorii prawdopodobieństwa;\nw zakresie biologii oraz chemii:\nzwiększenie znaczenia umiejętności wyjaśniania procesów i zjawisk biologicznych\ni chemicznych,\nmierzenie\numiejętności\nanalizy\neksperymentu\nsposobu\njego\nplanowania,\nprzeprowadzania, stawianych hipotez i wniosków formułowanych na podstawie\ndołączonych wyników;\nw zakresie fizyki:\nzwiększenie znaczenia rozumienia istoty zjawisk oraz tworzenie formuł matematycznych\nłączących kilka zjawisk,\nmierzenie umiejętności planowania i opisu wykonania prostych doświadczeń, a także\numiejętności analizy wyników wraz z uwzględnieniem niepewności pomiarowych;\nw zakresie geografii:\nuwzględnienie interdyscyplinarności tej nauki poprzez sprawdzanie umiejętności\nintegrowania wiedzy z nauk przyrodniczych do analizy zjawisk i procesów zachodzących\nw środowisku geograficznym,\nznaczne wzbogacenie zasobu materiałów źródłowych (mapy, wykresy, tabele\nstatystyczne, teksty źródłowe, barwne zdjęcia, w tym lotnicze i satelitarne), także\nw postaci barwnej.\nKonferencja Rektorów Akademickich Szkół Polskich z zadowoleniem przyjmuje też\ninformację o wprowadzeniu na świadectwach maturalnych od 2015 roku dodatkowej formy\nprzedstawiania wyniku uzyskanego przez zdającego w postaci jego pozycji na skali\ncentylowej, tj. określenie, jaki odsetek zdających uzyskał taki sam lub słabszy wynik od\nposiadacza świadectwa. Wprowadzenie tej dodatkowej skali uwolni szkoły wyższe od\ndotychczasowego dylematu odnoszenia do siebie surowych wyników kandydatów na studia\nrekrutowanych na podstawie wyników egzaminów maturalnych o istotnie różnym poziomie\ntrudności - rekrutacja stanie się prostsza i bardziej obiektywna.\nReasumując, w opinii Konferencji Rektorów Akademickich Szkół Polskich zaprezentowana\nw przedłożonych informatorach forma matury istotnie przyczyni się do tego, że młodzież\nprzekraczająca progi uczelni będzie lepiej przygotowana do podjęcia studiów wyższych.\n5 lipca 2013 r.\nPrzewodniczący KRASP\nprof. zw. dr hab. Wiesław Banyś","answer":null,"answer_text":null,"solution":null,"image":"img/informator-maturalny-informatyka-2015/zad-22.webp","solution_image":null,"topics":null,"page_from":75,"source":"ocr","answer_source":null,"answer_text_source":null,"solution_source":null,"text_source":"ocr","source_label":"Informatyka · Informator maturalny · 2015","subject_label":"Informatyka","category_label":"Informator maturalny","text_html":"

Zadanie 22. Bloki trójkowe (0-12)
Niech n będzie dodatnią liczbą całkowitą i niech a1, a2, …, an będzie ciągiem nieujemnych
liczb całkowitych. Dla pary liczb i, j takich, że 1 ≤
≤
≤
, blokiem b(i,j) nazywamy
podciąg kolejnych elementów ciągu a z pozycji od i do j, czyli ai, ai+1, …, aj. Długością
bloku nazywamy liczbę jego elementów. O bloku, którego suma elementów jest podzielna
przez 3 mówimy, że jest blokiem trójkowym.
Przykład:
W ciągu 0,0,2,3,2,1,2 najdłuższym blokiem trójkowym jest b(4,6) = 3,2,1.
W plikach tekstowych bloki1.txt, bloki2.txt i bloki3.txt zapisano ciągi
odpowiednio 1000, 30000 i 1000000 nieujemnych liczb całkowitych mniejszych od 10 000.
W każdym pliku liczby zapisano w kolejnych wierszach, po jednej liczbie w każdym wierszu.
Dla każdego pliku z danymi wyznacz długość najdłuższego bloku trójkowego w ciągu
zapisanym w tym pliku.
Przykład:
Dla danych z pliku z 7 liczbami:
0
0
2
3
2
1
2
długość najdłuższego bloku trójkowego wynosi 3.
Do oceny oddajesz plik(i) o nazwie(ach)
tu wpisz nazwę/nazwy pliku/plików
zawierający(e) komputerową realizację Twoich obliczeń oraz pliki tekstowe wyniki1.txt,
wyniki2.txt, wyniki3.txt, gdzie każdy z nich zawiera liczbę równą długości
najdłuższego bloku trójkowego w ciągach zapisanych odpowiednio w plikach bloki1.txt,
bloki2.txt i bloki3.txt.
Wymagania ogólne
III. Rozwiązywanie problemów i podejmowanie
decyzji z wykorzystaniem komputera, z zastosowaniem
podejścia algorytmicznego.
Wymagania szczegółowe

\n
  1. Rozwiązywanie problemów i podejmowanie decyzji
\n

z wykorzystaniem komputera, stosowanie podejścia
algorytmicznego.
Zdający:

\n
  1. analizuje, modeluje i rozwiązuje sytuacje
\n

problemowe z różnych dziedzin,

\n
  1. opisuje podstawowe algorytmy i stosuje algorytmy
\n

na liczbach całkowitych,

\n
  1. dobiera odpowiednie struktury danych
\n

do realizacji algorytmu, w tym struktury dynamiczne,

\n
  1. stosuje zasady programowania strukturalnego
\n

i modularnego do rozwiązywania problemu,
76 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015

\n
  1. stosuje podstawowe konstrukcje programistyczne
\n

w wybranym języku programowania, instrukcje
iteracyjne i warunkowe, rekurencję i procedury,
instrukcje wejścia i wyjścia, poprawnie tworzy
strukturę programu,

\n
  1. dobiera najlepszy algorytm, odpowiednie
\n

struktury danych i oprogramowanie do rozwiązania
postawionego problemu,

\n
  1. ocenia poprawność komputerowego rozwiązania
\n

na podstawie jego testowania.
Schemat punktowania
Czynność
Liczba
punktów
za zadanie
Za poprawne wyniki dla pliku 1 - 3 punkty.
Za poprawne wyniki dla pliku 2 - 4 punkty.
Za poprawne wyniki dla pliku 3 - 5 punktów.
12
Zadanie 22. Bloki trójkowe (0-12) - rozwiązanie
Pliki z danymi, plik programu źródłowego oraz pliki wynikowe zawierające odpowiedzi
znajdują się w folderze BLOKI TROJKOWE.
Komentarz
Uważny czytelnik szybko zauważy, że proste rozwiązanie jest ukryte w treści zadania.
Wystarczy przejrzeć wszystkie bloki, dla każdego bloku zsumować jego elementy, sprawdzić,
czy otrzymana suma jest podzielna przez 3 i spośród wszystkich bloków spełniających ten
warunek wybrać najdłuższy. Oto fragment algorytmu zapisany w pseudo-języku C++, będący
realizacją tego prostego pomysłu:
najdluzszy = 0; // długość najdłuższego z dotychczas
//przejrzanych bloków trójkowych
for (i = 1; i <= n; i++)
for (j = i; j <= n; j++){
// obliczamy sumę elementów w bloku b(i,j)
suma = 0;
for (k = i; k <= j; k++)
suma = suma + ak; // (*)
// sprawdzamy, czy suma jest podzielna przez 3, czyli
// czy reszta z dzielenia suma przez 3 daje 0
if (suma % 3 == 0){
// jeśli suma jest podzielna przez 3 i blok b(i,j)
// jest dłuższy od dotychczas najdłuższego bloku
// trójkowego, to zapamiętujemy jego długość
dl = j - i + 1;
if (dl >= najdluzszy)
najdluzszy = dl;
}
}
// najdluzszy jest długością najdłuższego bloku trójkowego w
// ciągu a
Przykładowe zadania z rozwiązaniami 77
Jedyną dobrą cechę powyższego rozwiązania jest jego prostota i to, że w ogóle mamy
jakiekolwiek rozwiązanie. Poza tym przedstawione rozwiązanie ma same wady.
Po pierwsze musimy pamiętać o tym, żeby arytmetyka języka programowania, którego
używamy, umożliwiała operowanie na liczbach pojawiających się w obliczeniach.
Zauważmy, że największa liczba jaka mogłaby się w obliczeniach dla opisanych danych
wynosi 1 000 000 * 9 999 = 9 999 000 000. W języku programowania C++ największa
liczba typu int ze znakiem ma wartość 2 147 483 647, a bez znaku 4 294 967 295. Tak jest,
gdy typ int jest 32-bitowy. Dla 16-bitowego typu int odpowiednie wielkości są znacząco
mniejsze. Oczywiście można by użyć typów pozwalających na operowanie na dużo większych
liczbach, ale za chwilę okaże się, że nie jest to konieczne.
Drugą wadą powyższego rozwiązania jest to, że musimy wielokrotnie przeglądać te same
elementu ciągu, a co za tym idzie najlepiej byłoby cały ciąg wczytać do tablicy. To
w przypadku największego pliku wymaga tablicy o 1 000 000 elementów. W przypadku
języka programowania C++ i 32-bitowego typu int wymaga to 4 000 000 bajtów, czyli około
4 gigabajtów pamięci. Nie jest to może dużo dla współczesnych komputerów, ale co gdyby
dane liczyły nie milion, a miliard, bilion elementów?
Trzecią wadą, chyba najistotniejszą, jest powolność zaproponowanego algorytmu.
Zastanówmy się, ile łącznie dodawań wykonamy w kroku (*). Nietrudno zauważyć, że tych
dodawań jest tyle, ile wynosi łączna suma długości wszystkich przedziałów. Tę wielkość
łatwo oszacować z dołu. Przedziałów o długości co najmniej n/3 jest co najmniej (n/3)2. A
zatem łączna suma wszystkich przedziałów wynosi co najmniej (n/3)3. To dla n = 1 000 000
daje więcej niż 3*1016. Komputer wykonujący 109 dodawań na sekundę spędzałby na
rozwiązywaniu naszego zadania więcej niż 3*107 sekund, a to jest więcej niż 8 tysięcy
godzin. To jest trochę za długo jak na czas przeznaczony na rozwiązywanie zadań
maturalnych!
Jeden ze sposobów poszukiwania lepszych, szybszych algorytmów polega na przyjrzeniu się
rozwiązaniu, które już mamy w ręku i zastanowieniu się, czy nie prowadzi ono do
wykonywania wielu zbędnych operacji. Tak jest właśnie w tym przypadku. Zauważmy, że dla
każdych dwóch bloków b(i,j-1) i b(i,j), różniących się tylko jednym elementem aj, liczymy
niezależnie dwie sumy ai+ ai+1 + + aj-1 oraz ai+ ai+1 + + aj, a przecież, żeby dostać
drugą sumę wystarczy do pierwszej dodać tylko aj. Jaki zysk! Zamiast j-i+1 dodawań
wykonujemy tylko jedno. Ten pomysł pozwala nam natychmiast zaproponować następujący
algorytm:
najdluzszy = 0; // długość najdłuższego z dotychczas
//przejrzanych bloków trójkowych
for (i = 1; i <= n; i++){
//liczymy sumy elementów w blokach o początkach na pozycji i
//wartością suma będzie suma elementów ostatniego
//przetworzonego bloku; inicjalnie suma == 0
suma = 0;
for (j = i; j <= n; j++){
// obliczamy sumę elementów w bloku b(i,j)
// suma jest równa sumie elementów w bloku b(i,j-1)
// plus aj
suma = suma + aj; // (*)
78 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015
// sprawdzamy, czy suma jest podzielna przez 3, czyli
// czy reszta z dzielenia suma przez 3 daje 0
if (suma % 3 == 0){
// jeśli jest podzielna przez 3 i blok b(i,j)
// jest dłuższy od dotychczas najdłuższego bloku
// trójkowego, to zapamiętujemy jego długość
dl = j - i + 1;
if (dl >= najdluzszy)
najdluzszy = dl;
}
}
// najdluzszy jest długością najdłuższego bloku trójkowego w
// ciągu a
Ile tym razem wykonujemy dodawań (*)? Nietrudno zauważyć, że tyle, ile jest bloków. Żeby
policzyć sumę elementów w bloku b(i,j), wykonujemy tylko jedno dodawanie - do sumy
elementów z bloku b(i,j-1) dodajemy aj. Ile jest wszystkich bloków? Bloków o początku na
pozycji 1 jest n, bloków o początku na pozycji 2 jest n-1, bloków o początku na pozycji 3 jest
n-2, itd. Tak więc bloków o początku na pozycji i jest n-i+1. Wszystkich bloków jest
n + n-1 + + 1 = n(n-1)/2. Dla n = 1 000 000 ta wartość wynosi 499 999 500 000. A zatem
komputer wykonujący 109 dodawań na sekundę wykonałby nasze zadanie w około 500
sekund, czyli w około 7 minut. Natomiast dla ciągu o długości 30 000 odpowiedź
dostalibyśmy natychmiast.
W przypadku rozpatrywanego zadania myślenie algorytmiczne może dać jeszcze lepsze
efekty. Najpierw pozbądźmy się problemu dużych liczb. To łatwe. W wierszu (*) wystarczy
sumować modulo 3. Inaczej mówiąc, w zmiennej suma zamiast sumy elementów pamiętamy
resztę z dzielenia tej sumy przy dzieleniu przez 3. Więcej o wykonywaniu operacji
arytmetycznych modulo napisaliśmy w komentarzu do zadania Podzielność. Przy tym
podejściu wiersz (*) miałby postać:
suma = (suma + aj) % 3;// (*)
Natomiast instrukcja warunkowa if (suma % 3 == 0)przybrałaby postać:
if (suma == 0)
W ten sposób poradziliśmy sobie z problemem dużych liczb, ale czasowa złożoność
obliczeniowa naszego algorytmu pozostała bez zmian. Następujące spostrzeżenia pozwolą
przyśpieszyć poszukiwanie najdłuższego bloku trójkowego. Dla każdego k = 1, 2, …, n
oznaczmy przez sk sumę pierwszych k elementów w ciągu a. Innymi słowy sk jest sumą
elementów w bloku b(1,k). Dla wygody przyjmijmy, że mamy też element a0 = 0 i w naturalny
sposób weźmy s0 = 0. Zauważmy teraz, że suma elementów w bloku b(i,j),
1 ≤ i≤ j ≤n , jest równa sj - si-1. Dla naszych celów wartości s wystarczy liczyć modulo 3.
W takim przypadku wartością sk może być tylko 0, 1 lub 2. Teraz najważniejsze:
Blok b(i,j) jest blokiem trójkowym wtedy i tylko, gdy sj oraz si-1 mają taką samą wartość 0, 1,
lub 2.
Przykładowe zadania z rozwiązaniami 79
Powyższe spostrzeżenie daje bardzo proste rozwiązanie naszego zadania. Dla każdej
wartości w = 0, 1, 2 poszukujemy pierwszej i ostatniej pozycji, dla której wartości sum s są
takie same. Najbardziej odległe pozycje wyznaczają długość najdłuższego bloku trójkowego.
Pozostaje jeszcze pytanie, czy zawsze taki blok istnieje. Osobom o zainteresowaniach
bardziej matematycznych proponujemy wykazanie, że w każdym ciągu o długości co najmniej
3 taki blok musi istnieć. Dla naszych potrzeb przyjmijmy, że blok długości 0 jest blokiem
trójkowym. Wówczas, jeśli wynikiem działania naszego algorytmu jest 0, oznacza to, że
żaden blok w danym ciągu nie jest trójkowy.
Poniżej przedstawiamy program napisany w języku C++, który konkretyzuje opisane
powyżej idee.
#include <iostream>
#include <algorithm>
using namespace std;
int najdluzszy_blok(){
int poczatki = {0,-1,-1};
//poczatki[w] - pierwsza pozycja, dla której suma s jest
//równa w
// -1 oznacza, że takiej pozycjijeszcze nie
// znaleziono
int suma_mod_3 = 0;
int liczba_wczytanych = 0;
int element;
int najdluzszy;
while (cin>> element){
liczba_wczytanych++;
suma_mod_3 = (suma_mod_3 + element) % 3; //(*)
if (poczatki[suma_mod_3] == -1)
poczatki[suma_mod_3] = liczba_wczytanych;
else
najdluzszy = max(najdluzszy, liczba_wczytanych

\n\n

}
return najdluzszy;
}
int main(){
cout << "Dl bloku: " << najdluzszy_blok() << endl;
return 0;
}
Na koniec zauważmy, że w tym algorytmie liczba dodawań (*) wynosi tylko n i na dodatek
nie musieliśmy najpierw wczytać całego ciągu do tablicy.
80 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015
Opinia KRASP o informatorach maturalnych od 2015 roku 81
Opinia Konferencji Rektorów Akademickich Szkół Polskich
o informatorach maturalnych od 2015 roku
Konferencja Rektorów Akademickich Szkół Polskich z wielką satysfakcją odnotowuje
konsekwentne dążenie systemu oświaty do poprawy jakości wykształcenia absolwentów
szkół średnich. Konferencja z uwagą obserwuje kolejne działania Ministerstwa Edukacji
Narodowej w tym zakresie, zdając sobie sprawę, że od skuteczności tych działań w dużym
stopniu zależą także efekty kształcenia osiągane w systemie szkolnictwa wyższego.
W szczególności dotyczy to kwestii właściwego przygotowania młodzieży do studiów
realizowanych z uwzględnieniem nowych form prowadzenia procesu kształcenia.
Podobnie jak w przeszłości, Konferencja konsekwentnie wspiera wszystkie działania
zmierzające do tego, by na uczelnie trafiali coraz lepiej przygotowani kandydaci na studia.
Temu celowi służyła w szczególności pozytywna opinia Komisji Edukacji KRASP z 2008 roku
w sprawie nowej podstawy programowej oraz uchwała Zgromadzenia Plenarnego KRASP
z dn. 6 maja 2011 r. w sprawie nowych zasad egzaminu maturalnego.
Z satysfakcją dostrzegamy, że ważne zmiany w egzaminie maturalnym, postulowane
w cytowanej wyżej uchwale zostały praktycznie wdrożone przez MEN poprzez zmianę
odpowiednich rozporządzeń.
Przedłożone do zaopiniowania informatory o egzaminach maturalnych opisują formę
poszczególnych egzaminów maturalnych, przeprowadzanych na podstawie wymagań
określonych w nowej podstawie programowej, a także ilustrują te wymagania wieloma
przykładowymi zadaniami egzaminacyjnymi.
Po zapoznaniu się z przedłożonymi materiałami, KRASP z satysfakcją odnotowuje:
w zakresie języka polskiego:
wzmocnienie roli umiejętności komunikacyjnych poprzez odejście od prezentacji na
egzaminie ustnym i zastąpienie jej egzaminem ustnym, na którym zdający będzie musiał
ad hoc przygotować samodzielną wypowiedź argumentacyjną,
rezygnację z klucza w ocenianiu wypowiedzi pisemnych,
zwiększenie roli tekstów teoretycznoliterackich i historycznoliterackich na maturze
rozszerzonej;
w zakresie historii:
kompleksowe sprawdzanie umiejętności z zakresu chronologii historycznej, analizy
i interpretacji historycznej oraz tworzenia narracji historycznej za pomocą rozbudowanej
wypowiedzi pisemnej na jeden z zaproponowanych tematów, łącznie pokrywających
wszystkie epoki oraz obszary historii;
w zakresie wiedzy o społeczeństwie:
położenie silniejszego akcentu na sprawdzanie umiejętności złożonych (interpretowanie
informacji, dostrzeganie związków przyczynowo-skutkowych) w oparciu o poszerzony
zasób materiałów źródłowych: teksty (prawne, naukowe, publicystyczne), materiały
statystyczne, mapy, rysunki itp.
82 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015
w zakresie matematyki:
istotne zwiększenie wymagań na poziomie rozszerzonym poprzez włączenie zadań
z rachunku różniczkowego i pojęć zaawansowanej matematyki,
istotne poszerzenie wymagań z zakresu kombinatoryki oraz teorii prawdopodobieństwa;
w zakresie biologii oraz chemii:
zwiększenie znaczenia umiejętności wyjaśniania procesów i zjawisk biologicznych
i chemicznych,
mierzenie
umiejętności
analizy
eksperymentu
sposobu
jego
planowania,
przeprowadzania, stawianych hipotez i wniosków formułowanych na podstawie
dołączonych wyników;
w zakresie fizyki:
zwiększenie znaczenia rozumienia istoty zjawisk oraz tworzenie formuł matematycznych
łączących kilka zjawisk,
mierzenie umiejętności planowania i opisu wykonania prostych doświadczeń, a także
umiejętności analizy wyników wraz z uwzględnieniem niepewności pomiarowych;
w zakresie geografii:
uwzględnienie interdyscyplinarności tej nauki poprzez sprawdzanie umiejętności
integrowania wiedzy z nauk przyrodniczych do analizy zjawisk i procesów zachodzących
w środowisku geograficznym,
znaczne wzbogacenie zasobu materiałów źródłowych (mapy, wykresy, tabele
statystyczne, teksty źródłowe, barwne zdjęcia, w tym lotnicze i satelitarne), także
w postaci barwnej.
Konferencja Rektorów Akademickich Szkół Polskich z zadowoleniem przyjmuje też
informację o wprowadzeniu na świadectwach maturalnych od 2015 roku dodatkowej formy
przedstawiania wyniku uzyskanego przez zdającego w postaci jego pozycji na skali
centylowej, tj. określenie, jaki odsetek zdających uzyskał taki sam lub słabszy wynik od
posiadacza świadectwa. Wprowadzenie tej dodatkowej skali uwolni szkoły wyższe od
dotychczasowego dylematu odnoszenia do siebie surowych wyników kandydatów na studia
rekrutowanych na podstawie wyników egzaminów maturalnych o istotnie różnym poziomie
trudności - rekrutacja stanie się prostsza i bardziej obiektywna.
Reasumując, w opinii Konferencji Rektorów Akademickich Szkół Polskich zaprezentowana
w przedłożonych informatorach forma matury istotnie przyczyni się do tego, że młodzież
przekraczająca progi uczelni będzie lepiej przygotowana do podjęcia studiów wyższych.
5 lipca 2013 r.
Przewodniczący KRASP
prof. zw. dr hab. Wiesław Banyś

","solutions":[]}