Matura z informatyki 2010 – maj, poziom rozszerzony

Szyfrowanie przestawieniowe jest klasyczną metodą szyfrowania polegającą na zmianie kolejności liter w szyfrowanym tekście. Często używa się reguł zamiany opartych na różnych figurach geometrycznych – w tym zadaniu użyjemy kwadratu. Szyfrowanie będzie polegało na wprowadzeniu tekstu do kwadratowej tablicy szyfrującej o wymiarach n×n po kolei wierszami, a następnie odczytaniu tekstu z tablicy kolumnami od lewej do prawej. Wymiar n tablicy jest najmniejszą liczbą, przy której tekst zmieści się w całości w kwadracie n×n. W przypadku, gdy tekst jest krótszy i nie wypełnia wszystkich pól tablicy, puste pola uzupełnia się znakami odstępu. W tym zadaniu znaki odstępu będziemy oznaczać _.

Przykład:

Załóżmy, że tekst ALGORYTM_PRZESTAWIENIOWY ma być zaszyfrowany w tablicy kwadratowej. Liczba znaków w tekście do zaszyfrowania jest równa 24, czyli tablica szyfrująca ma wymiary 5×5. Ostatni element tablicy będzie uzupełniony znakiem odstępu. Tekst zapisujemy do tablicy wierszami.

Następnie odczytujemy zaszyfrowany tekst kolumnami: AYRAILTZWOGMEIWO_SEYRPTN_

public class Main {

  public char[] szyfruj(char[] tekst) {
    //dlugosc tekstu
    int d = tekst.length;
    int n = (int) Math.ceil(Math.sqrt(d));
    char[][] tab = new char[n][n];
    int znak = 0;
    for (int i = 0; i < tab.length; i++) {
      //wiersz
      char[] cs = tab[i];
      for (int j = 0; j < cs.length; j++) {
        //kolumna - indeks maksymalny jest d-1
        if (znak >= d) {
          cs[j] = ' ';
        } else {
          cs[j] = tekst[znak];
        }
        znak++;
      }
    }
    int s = n*n;
    char szyfr[] = new char[s];
    znak = 0;
    for (int i = 0; i < tab.length; i++) {
      //wiersz
      char[] cs = tab[i];
      for (int j = 0; j < cs.length; j++) {
        //kolumna
        char c = tab[j][i];
        szyfr[znak] = tab[j][i];
        znak++;
      }
    }
    return szyfr;
  }
}

W tablicy a[1…1023] zapisano ciąg zer i jedynek w taki sposób, że wszystkie zera poprzedzają jedynki.

Uwaga: W tablicy mogą być same zera lub same jedynki.

Oto niepełny algorytm obliczania liczby zer w tablicy a:

← – oznacza instrukcję przypisania

div – oznacza dzielenie całkowite

liczba_zer ← 0
l ← 1, p ← 1023
dopóki l ≤ p wykonuj
        s ← (l + p) div 2
        jeśli a[s] = 1 to
                p ← s − 1
        w przeciwnym przypadku
                liczba_zer ← liczba_zer + 
                l ← 

Podpunkty a) – e) zawierają po trzy stwierdzenia, z których każde jest albo prawdziwe, albo fałszywe. Zdecyduj, które z podanych stwierdzeń są prawdziwe (P), a które fałszywe (F).

Anagram to słowo powstałe z innego słowa przez przestawienie liter. Przez słowo rozumiemy w tym zadaniu dowolny ciąg liter alfabetu łacińskiego.

Przykłady anagramów:

dla słowa: barok – korba, robak, arobk, rokab, orkab …

dla słowa: ranty – tyran, narty, ntyra, natyr, ytnar …

W pliku tekstowym anagram.txt znajduje się 200 wierszy zawierających po 5 słów w każdym wierszu. Słowa oddzielone są znakiem odstępu. Długość każdego ze słów wynosi od 1 do 20 znaków.

Przykład:

abcd cdba dbac cbad dcba
barbakan xle ala foto otof
smok ayszkm lampa ayszkm bakara
skok arabanta oko agnieba dyskietka
……

Napisz program w wybranym przez siebie języku programowania, za pomocą którego wykonasz poniższe polecenia. Odpowiedzi zapisz w plikach odp_4a.txt oraz odp_4b.txt.

abcd cdba dbac cbad dcba
wrona rossa slowo gwert rezas
grant hello zakon lloeh hello
kabaret kabanos kabaret gertyfu kabaret
ola ala aga oal ola
rezas rossa zaser sarez rezas
foto foto tofo tofo foto
romans  romans  normag masrom ansrom
ekran ranek lampa zakon ekran
korba orkan delpu pudel udelp
czek azer reza zare rzea
cebula romans  romans mansro romans
kruk kruk buka zuka nuka
agent rossa serce cerse sdfrt
qwerty wertyq wertyu magnor normag
glob lobg bogl glbo gblo
triada dariat aadrit iatdar adatri
kotek tekok teokk kokte otekk
obrus bruso soubo seawo rusob
rower werro werro owerr erwor
ipfon ipfon fonip ipfon zakop
nerka drewn korba korba korba
patyk wrona wrona wrona wrona
foto tofo foot ftoo ootf
spiker kerspi erspik erspki kiersp
burza orkan lukde pudeh lerfy

abcd cdba dbac cbad dcba
foto foto tofo tofo foto
glob lobg bogl glbo gblo
triada dariat aadrit iatdar adatri
kotek tekok teokk kokte otekk
rower werro werro owerr erwor
foto tofo foot ftoo ootf
spiker kerspi erspik erspki kiersp

Numer PESEL to 11-cyfrowy kod, jednoznacznie identyfikujący określoną osobę fizyczną. Dla wszystkich urodzonych przed 1.1.2000 r. skonstruowany został w następujący sposób:

• cyfry od 1 do 6 to data urodzenia (w kolejności: rok, miesiąc, dzień),
• cyfry od 7 do 9 to liczba porządkowa,
• cyfra 10-ta to płeć (cyfra parzysta dla kobiet, nieparzysta dla mężczyzn),
• cyfra 11-ta to cyfra kontrolna.

Przykład:

Numer PESEL 75121968629 oznacza kobietę (bo przedostatnia cyfra w numerze jest parzysta), urodzoną 19 grudnia 1975 roku, której nadano liczbę porządkową 686.

Cyfra kontrolna jest obliczana wg następującego algorytmu:

1. Każdą cyfrę numeru PESEL (oprócz ostatniej, która jest cyfrą kontrolną) mnożymy przez odpowiadającą jej wagę. Tablica wag ma postać: 1, 3, 7, 9, 1, 3, 7, 9, 1, 3. W podanym powyżej numerze PESEL cyfrą kontrolną jest 9.

PESEL: 7 5 1 2 1 9 6 8 6 2 9 (ostatnią cyfrę pomijamy, bo to cyfra kontrolna)
WAGI:  1 3 7 9 1 3 7 9 1 3
WYNIKI: 7x1=7; 5x3=15; 1x7=7; 2x9=18 ;1x1=1; 9x3=27; 6x7=42; 8x9=72; 6x1=6; 2x3=6

2. Wyniki sumujemy: 7 + 15 + 7 + 18 + 1 + 27 + 42 + 72 + 6 + 6 = 201 3. Wyznaczamy resztę z dzielenia sumy przez 10: 201:10 = 20 reszta = 1 4. Jeżeli reszta = 0, to cyfra kontrolna wynosi 0. Jeżeli reszta ≠ 0, to cyfra kontrolna będzie uzupełnieniem reszty do 10, czyli w podanym przykładzie jest to cyfra 9.

Plik pesel.txt zawiera numery PESEL 150 osób zatrudnionych w biurze obliczeniowym „Statystyk". Korzystając z informacji zawartych w pliku pesel.txt oraz dostępnych narzędzi informatycznych, wykonaj poniższe polecenia. Odpowiedzi do poszczególnych podpunktów umieść w pliku odp_5.txt, poprzedzając je literą oznaczającą ten podpunkt.

Uwaga: Możesz przyjąć, że nawet gdy cyfra kontrolna numeru PESEL jest niepoprawna, to dane osobowe w nim zapisane, są prawidłowe.

Lista numerów PESEL:
54043010088
60061144469
77072919805
77120835871
83041812338
89081421445
91032272651
92022716243

Szkoła dysponuje danymi zawartymi w trzech plikach: uczniowie.txt, oceny.txt, przedmioty.txt.

• Plik uczniowie.txt zawiera następujące dane o uczniach: idUcznia, nazwisko, imie, ulica, dom, idKlasy.
• Plik oceny.txt zawiera dane o ocenach: idUcznia, ocena, data, idPrzedmiotu.
• Plik przedmioty.txt zawiera dane o przedmiotach: idPrzedmiotu, nazwaPrzedmiotu, nazwisko_naucz, imie_naucz.

Korzystając z danych zawartych w plikach uczniowie.txt, oceny.txt, przedmioty.txt oraz z dostępnych narzędzi informatycznych wykonaj poniższe polecenia. Każdą odpowiedź umieść w pliku odp_6.txt, poprzedzając ją oznaczeniem odpowiedniego podpunktu od a) do f).