Rozwiązywanie arkuszy maturalnych z informatyki

Z podanych rozwiązań należy korzystać dopiero po samodzielnym rozwiązaniu danego zadania w celu sprawdzenia poprawności wyniku. Rozwiązania nie są optymalne (nie zostały sprawdzone z kluczem odpowiedzi, ponieważ na dzień dzisiejszy klucz ten nie został jeszcze opublikowany w Internecie). Nie są również jedyne - zadania można rozwiązać w inny, alternatywny sposób.

 

Poziom podstawowy

 

Zadanie 1. Szyfrowanie (8 pkt)

Poniższy algorytm szyfruje słowo s  przy pomocy pewnego szyfru przestawieniowego.

Zaszyfrowane słowo zostaje zapisane w zmiennej w.

Algorytm

1. i ← 1, w  ← '', k  ← 2

2. dopóki i <= k  wykonuj
     j  ← i
    dopóki j  <= długość(s) wykonuj:
        w  ← w s[j]
        j  ← j + k
    i  ← i + 1

Objaśnienia:

'' oznacza słowo puste, s[j] oznacza j-ty znak w słowie s  (numeracja rozpoczyna się od 1)

• oznacza sklejenie dwóch słów (ewentualnie sklejenie słowa i znaku)

← oznacza instrukcję przypisania.

 

Szybka analiza powyższego algorytmu daje odpowiedź, że tekst jest szyfrowany poprzez wybieranie z niego znaków, które w pierwszym obiegu pętli z kroku 2 leżą na pozycjach nieparzystych: 1, 3, 5, ..., a następnie w kolejnym obiegu tej pętli wybierane są znaki leżące na pozycjach parzystych: 2, 4, 6, ...

  1. Zapisz wynik działania powyższego algorytmu dla słów ARKA i MOTOR.

    ARKAAKRA

    MOTOR
    MTROO

  2. Kluczem szyfrującym nazywamy pewną wartość, która jest wymagana przy szyfrowaniu i deszyfrowaniu, a jej zmiana może dać inny wynik szyfrowania tego samego słowa. Która ze zmiennych i, j, k służy do przechowywania klucza w podanym algorytmie?

    Jedynie k  może być kluczem - definiuje odstęp pomiędzy wybieranymi kolejno znakami ze szyfrowanego tekstu. Pozostałe zmienne i  oraz j  służą do przenoszenia znaków z tekstu do szyfru i ich wartości są uzależnione od k.
     

  3. Zapisz algorytm (w postaci listy kroków, schematu blokowego lub w wybranym języku programowania), realizujący następującą metodę szyfrowania: słowo dzielimy na grupy po dwa znaki i w każdej parze zamieniamy znaki miejscami. Jeśli słowo ma nieparzystą długość, ostatni znak pozostaje niezmieniony. Wynik zaszyfrowania danego słowa s  zapisz w zmiennej w

          Przykłady:

                    MOTOR → MO TO R → OM OT R → OMOTR
                    MATURA →MA TU RA → AM UT AR → AMUTAR

 

Specyfikacja:

Dane:
  s  - łańcuch znaków, który przechowuje szyfrowane słowo, pierwszy znak ma indeks 1.

Wyniki:
  w  - łańcuch znaków, który zawiera zaszyfrowane słowo s, pierwszy znak ma indeks 1.

Zmienne pomocnicze:
  i  - indeks znaków
  x  - zmienna pomocnicza do wymiany znaków (dla wersji II)

Objaśnienia:

s[j] oznacza j-ty znak w słowie s  (numeracja rozpoczyna się od 1)
• oznacza sklejenie dwóch słów (ewentualnie sklejenie słowa i znaku)
← oznacza instrukcję przypisania
mod - operacja modulo

 

Lista kroków - wersja I:

krok 1: w  ← ''
krok 2: i  ← 1
krok 3: Jeśli i  > długość(s), to idź do kroku 7
krok 4: Jeśli i  mod 2 = 0, to  w  ← w  • s[i] • s[i-1]
krok 5: i  ← i  + 1
krok 6: Idź do kroku 3
krok 7: Jeśli długość(w) < długość(s), to w  ← w  • s[i-1]
krok 8: Zakończ

Lista kroków - wersja II:

krok 1: w  ← s
krok 2: i  ← 1
krok 3: Jeśli i  > długość(s), to zakończ
krok 4: Jeśli i  mod 2 = 1, to idź do kroku 8
krok 5: x  ← w[i]
krok 6: w[i] ← w[i-1]
krok 7: w[i-1] ← x
krok 8: i  ← i  + 1
krok 9: Idź do kroku 3

Schemat blokowy - wersja I:

obrazek

Schemat blokowy - wersja II:

obrazek


Program C++:

// Zadanie 1c - szyfrowanie
// Wersja I
//-------------------------

#include <iostream>
#include <string>

using namespace std;

int main()
{
  string s,w;
  int i;
  getline(cin,s);
  w = "";
  for(i = 0; i < s.length(); i++)
    if(i % 2) w = w + s[i] + s[i-1];
  if(w.length() < s.length()) w = w + s[i-1];
  cout << w << endl;
  return 0;
}
// Zadanie 1c - szyfrowanie
// Wersja II
//-------------------------

#include <iostream>
#include <string>

using namespace std;

int main()
{
  string s,w;
  int i;
  char x;
  getline(cin,s);
  w = s;
  for(i = 0; i < s.length(); i++)
    if(i % 2)
    {
       x = w[i];
       w[i] = w[i-1];
       w[i-1] = x;
    }
  cout << w << endl;
  return 0;
}

 

Program Pascal:

{ Zadanie 1c - szyfrowanie
  Wersja I
  ------------------------}

program szyfr;
var
  s,w : string;
  i   : integer;

begin
  readln(s);
  w := '';
  for i := 1 to length(s) do
    if i mod 2 = 0 then w := w + s[i] + s[i-1];
  if length(w) < length(s) then w := w + s[length(s)];
  writeln(w); 
end.

		
{ Zadanie 1c - szyfrowanie
  Wersja II
  ------------------------}

program szyfr;
var
  s,w : string;
  i   : integer;
  x   : char;

begin
  readln(s);
  w := s;
  for i := 1 to length(s) do
    if i mod 2 = 0 then
    begin
      x      := w[i];
      w[i]   := w[i-1];
      w[i-1] := x;
    end;
  writeln(w);
end.

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2021 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe