Matura 2016 (maj). Zadanie 1. Kompresja

Rozważmy algorytm kompresji, który zlicza liczbę kolejnych wystąpień tego samego znaku, a następnie zamiast całej grupy identycznych znaków podaje ten znak tylko jeden raz, poprzedzając go liczbą jego kolejnych wystąpień. Liczba kolejnych wystąpień każdego znaku nie przekracza 9, więc do zapisania tej liczby wystarczy jeden znak.

Przykład:

Zadanie 1.

Skompresuj powyższym algorytmem tekst podany w tabeli, oblicz rozmiar tekstu przed kompresją i po kompresji.

Zadanie 2.

Ile powinna wynosić minimalna liczba kolejnych znaków w grupie, aby jej kompresja była opłacalna?

Rozwiązanie:

W tekście musi występować powyżej dwa takie same znaki lub minimum dwa razy występować trzy takie same znaki.

Zadanie 3.

Czy opisana metoda kompresji jest stratna, czy – bezstratna?

Rozwiązanie:

Opisana kompresja jest bezstratna, ponieważ tekst, który został skompresowany, możliwe jest przywrócić tekst źródłowy bez jakiejkolwiek straty.

Zadanie 4.

Napisz (w postaci listy kroków, schematu blokowego, pseudokodu lub w wybranym języku programowania) algorytm obliczający rozmiar skompresowanego tekstu.

Specyfikacja:

Dane:

n – dodatnia liczba całkowita, długość kompresowanego tekstu
T[1..n] – tablica zawierająca tekst do skompresowania; T[i] – i-ty znak w tekście

Wynik:

b – rozmiar skompresowanego tekstu T

Algorytm:

#include <iostream>
using namespace std;
int main()
{
 string tekst = "***##!!*";
 string nowy = "";
 int dl = tekst.length();
 int ile=1;
 char szyfr = tekst[0];
 for (int i=1; i<dl; i++){
   if(szyfr==tekst[i])
     ile++;
   else {
     nowy+=(48+ile);
   nowy+=szyfr;
   ile=1;
   szyfr = tekst[i];
   }
 }
 nowy+=(48+ile);
 nowy+=szyfr;
 cout << nowy.length();
 return 0;
}