Strona główna » Algorytmy » Szyfry » Szyfr Ułamki
 

Szyfr Ułamki

https://mattomatti.com/a35j

O szyfrze

W szyfrze ułamków musimy zdefiniować ciąg liter, który będzie naszym alfabetem oraz klucz n, który jest liczbą całkowitą. Szyfrowanie polega na pogrupowanie liter w grupy po n kolejnych liter. Następnie szyfrując znak szukamy go w której grupie się znajduje. Po odnalezieniu zapisujemy kolejno, które miejsce zajmuje litera w grupie, znak "/" oraz numer grupy, gdzie znaleźliśmy znak. Wszystkie zaszyfrowane znaki rozdzielamy średnikiem. Znak spacji " " zastępujemy znakiem plusa "+". Ułamek przed znakiem spacji nie ma pos sobie średnika.

Przykładowo weźmy alfabet łaciński ABCDEFGHIJKLMNOPQRSTUVWXYZ i ustalmy klucz 5. Naszym pierwszym krokiem będzie pogrupowanie liter. Wynikiem tego jest ABCDE FGHIJ KLMNO PQRST UVWXY Z. Jeśli w danej grupie nie ma n znaków to może tak zostać, ponieważ nie ma to znaczenia. Teraz spróbujmy zaszyfrować tekst "INFORMACJA":

LiteraNr. GrupyPozycjaZapis
I242/4
N343/4
F212/1
O353/5
R434/3
M333/3
A111/1
C131/3
J252/5
A111/1

W ten sposób otrzymujemy szyfrogram: 2/4;3/4;2/1;3/5;4/3;3/3;1/1;1/3;2/5;1/1

Większość ułamków z matematycznego punktu widzenia jest skracalnych. Pod żadnym pozorem nie wolno w tym szyfrze skracać ułamków. Najlepszym przykładem jest 1/1, 2/2, 3/3, ... n/n. Z matematyki wynika , ale wtedy 1 może oznaczać dowolną i-tą grupę na i-tej pozycji. Innym przykładem jest 1/2 i 2/4.

Chcąc rozszyfrować bierzemy każdy kolejny ułamek. Licznik będzie wskazywał w której grupie jest znak, a licznik jego pozycję w wskazanej grupie. Przykładowo 3/5 to znak z trzeciej grupy na piątej pozycji czyli wg. przyjętego alfabetu litera W.

Zadanie 1

Treść

Na wejściu znajdą się dwie linijki danych. W pierwszej będzie liczba całkowita, która będzie długością podgrup. Druga linijka będzie to ciąg znaków, który będzie trzeba zaszyfrować zgodnie z szyfrem ułamkowym. Na wyjście powinien zostać wypisany wynik szyfrowania. Przykładowo dla:

  1. 2
  2. INFORMACJA

otrzymamy:

  1. 2/4;3/4;2/1;3/5;4/3;3/3;1/1;1/3;2/5;1/1

Zakładamy, że alfabet jest dany i są nim wszystkie duże litery alfabetu łacińskiego od A do Z.

Funkcje pomocnicze do szyfrowania

W celu optymalizacji wykorzystanie pamięci będziemy potrzebowali znać dokładną długość tekstu wynikowego co za tym idzie długość każdej liczby:

  1. int intDl(int n){
  2.   return (n >= 10) ? 1 + intDl(n / 10) : 1;
  3. }

Dodatkowo napiszemy funkcję, która pozwoli zapisywać liczbę na tablicy znaków. Innymi słowy będzie konwertować liczbę na tekst. Wykorzystamy do tego pętle do ... while. Dzięki temu mamy pewność, że jeśli przepisywana liczba to 0 to ją zapiszemy w wyniku.

  1. void intWrite(int n, char* s, int &i){
  2.   do{
  3.     s[i++] = n % 10 + '0';
  4.     n /= 10;
  5.   } while (n > 0);
  6. }

(1.) Funkcja nie zwraca żadnej wartości, jest ona bardziej częścią innej funkcji, ponieważ modyfikuje wartości jej przekazywane. Funkcja otrzymuje trzy argumenty: n - liczbę do przepisania, s - tablica char* do której przepisujemy kolejne cyfry oraz i - wskaźnik od którego miejsca w tablicy zaczynamy zapisywanie. (2.) Rozpoczynamy do ... while: (3.) Zapisujemy ostatnią cyfrę. (4.) Dzielimy liczbę przez 10, aby w następnej iteracji (jeśli będzie) pobrać następną cyfrę. (5.) Sprawdzamy warunek czy już przepisaliśmy całą liczbę.

Szyfrowanie

Na początek wyliczymy długość tekstu wynikowego:

  1. char* cipher(const char* txt, const int n){
  2.   int dl = 0;
  3.   for(int i = 0; txt[i]; i++)
  4.     if(txt[i] != ' ')
  5.       dl += 2 + intDl((txt[i] - 'A') / n + 1) + intDl((txt[i] - 'A') % n + 1);

(1.) Przyjmujemy dwa argumenty: txt - tekst do zaszyfrowania oraz n - długość każdej podgrupy. (2.) Ustalamy długość na 0. (3.) Dla każdego znaku, który jest różny od spacji (czyli liter od A do Z) (4.) zwiększamy długość o 2 (znak "/" i ";"). Do tego dodajemy długość liczby grupy i pozycji.

  1.   char* wynik = new char[dl];
  2.   for(int i = 0, j = 0; txt[i]; i++){
  3.     if(txt[i] == ' '){
  4.       wynik[j-1] = '+';

(6.) Alokujemy pamięć pod wynik. (7.) Dla każdego znaku w tekście do zaszyfrowania (8.) jeśli jest znakiem spacji to (9.) wstawiamy na znak na pozycji j-1.

  1.     } else {
  2.       intWrite((txt[i] - 'A') / n + 1, wynik, j);
  3.       wynik[j++] = '/';
  4.       intWrite((txt[i] - 'A') % n + 1, wynik, j);
  5.       wynik[j++] = ';';
  6.     }
  7.   }
  8.   wynik[dl - 1]='\0';
  9.   return wynik;
  10. }

(10.) Jeśli jest to litera to zapisujemy do wyniku (11.) numer grupy, (12.) znak "/", (13.) numer pozycji oraz (14.) znak średnika ";". (17.) Na koniec dopisujemy znak końca danych zamiast ostatniego średnika i (18.) zwracamy wynik.

Deszyfrowanie

Do deszyfrowania przyda się funkcje pomocnicza, która wczyta liczbę z tablicy char*. Zakładamy, że wczytujemy liczbę dopóki mamy jakiekolwiek cyfry.

  1. int intRead(const char* s, int &i){
  2.   int a = 0;
  3.   while (s[i] >= '0' && s[i] <= '9'){
  4.     a *= 10;
  5.     a += s[i++] - '0';
  6.   }
  7.   return a;
  8. }

(1.) Jako argumenty dostajemy tablice char* oraz pozycję i. W ten sposób wiemy od którego miejsca mamy zacząć wpisywać liczbę. (2.) Początkowo liczba wynosi 0. (3.) Dopóki mamy jakąkolwiek cyfrę to (4.) przesuwamy cyfry i jedną w lewo czyli mnożymy razy 10 i (5.) dodajemy kolejną wczytana cyfrę z tekstu. (7.) Na koniec zwracamy wczytaną liczbę.

Tak samo jak w przypadku szyfrowania na początek obliczymy długość tekstu:

  1. char* decipher(const char* txt, const int n){
  2.   int dl = 0;
  3.   for(int i = 0; txt[i]; i++)
  4.     if(txt[i] == '/' || txt[i] == '+')
  5.       dl++;

Każdy ułamek kończy się znakiem + lub ; i tylko ostatni ułamek nie ma ani jednego z wymienionych znaków. (2.) Deklarujemy długość tekstu na 0. (3.) Dla każdego znaku w szyfrogramie sprawdzamy czy wczytany jest znak / (który ma każdy ułamek) lub + (dodatkowe spacje). Kiedy zsumujemy wystąpienia oczytamy jak długi będzie tekst wynikowy.

  1.   char* wynik = new char[dl];
  2.   for(int i = 0, j = 0; txt[j]; i++, j++){
  3.     int t = (intRead(txt, j) - 1);
  4.     wynik[i] = t * n + (intRead(txt, ++j) - 1) + 'A';
  5.     if(txt[j] == '+') wynik[++i] = ' ';
  6.   }
  7.   wynik[dl]='\0';
  8.   return wynik;
  9. }

(6.) Alokujemy pamięć pod wynik. (7.) Dla każdego ze znaków w szyfrogramie: (7.) wczytujemy dwie liczby na podstawie których wyliczamy jaka literę przedstawia wczytany ułamek. (8.) Sprawdzamy czy poprzednim znakiem nie jest + co by oznaczało, że musimy dostawić dodatkową spacje. (12.) Na koniec dopisujemy znak końca danych zamiast ostatniego średnika i (13.) zwracamy wynik.

Testowanie funkcji

Poniższa funkcja main() pozwala sprawdzić czy napisane funkcje działają poprawnie.

  1. int main () {
  2.   int n;
  3.   cin >> n;
  4.   cin.sync();
  5.   char* txt = new char[128];
  6.   cin.getline(txt, 128);
  7.   char* txtc = cipher(txt, n);
  8.   cout << txtc << endl;
  9.   char* txtd = decipher(txtc, n);
  10.   cout << txtd << endl;
  11.   system("pause");
  12.   return 0;
  13. }

Zadanie 2

Na wejściu znajdą się trzy linijki danych. W pierwszej będzie ciąg znaków, który będzie przedstawiał alfabet, w drugiej liczba całkowita, która będzie długością podgrup. Trzecia linijka będzie to ciąg znaków, który będzie trzeba zaszyfrować zgodnie z szyfrem ułamkowym. Na wyjście powinien zostać wypisany wynik szyfrowania. Przykładowo dla:

  1. ZYXWVUTSRQPONMLKJIHGFEDCBA
  2. 5
  3. TAJNE INFO

otrzymamy:

  1. 2/2;6/1;4/2;3/3;5/2+4/3;3/3;5/1;3/2

Szyfrowanie

Dotychczasowy kod potrzebuje drobnej modyfikacji. Podczas szyfrowania nie możemy wyliczać grupy i pozycji na podstawie odległości od litery A. Wyliczymy je na podstawie pozycji znaku w podanym alfabecie. Żeby to osiągnąć dopiszemy funkcję, która dla podanego ciągu i znaku znajdzie jego pozycję i ją zwróci.

  1. int findChar(const char* data, const char c){
  2.   for(int i = 0; data[i]; i++)
  3.     if(data[i] == c)
  4.       return i;
  5.   return -1;
  6. }

Spójrzmy teraz na funkcję szyfrującą:

  1. char* cipher(const char* alphabet, const char* txt, const int n){
  2.   int dl = 0;
  3.   for(int i = 0; txt[i]; i++)
  4.     if(txt[i] != ' ')
  5.       dl += 2 + intDl(findChar(alphabet, txt[i]) / n + 1) + intDl(findChar(alphabet, txt[i]) % n + 1);
  6.   char* wynik = new char[dl];
  7.   for(int i = 0, j = 0; txt[i]; i++){
  8.     if(txt[i] == ' '){
  9.       wynik[j-1] = '+';
  10.     } else {
  11.       intWrite(findChar(alphabet, txt[i]) / n + 1, wynik, j);
  12.       wynik[j++] = '/';
  13.       intWrite(findChar(alphabet, txt[i]) % n + 1, wynik, j);
  14.       wynik[j++] = ';';
  15.     }
  16.   }
  17.   wynik[dl - 1]='\0';
  18.   return wynik;
  19. }

Zmodyfikowane są linijki (5.), (11.) i (13.), gdzie zastępujemy wyliczanie grupy i pozycji znaku - nie na podstawie tablicy ASCII, a na podstawie podanego alfabetu.

Deszyfrowanie

W funkcji rozszyfrowującej podajemy dodatkowy argument alphabet. Trzeba zmienić tylko linijkę (9.), gdzie nie wyliczamy znaku na podstawie tablicy ASCII, a pobieramy wyliczoną pozycję z tablicy alphabet.

  1.     wynik[i] = alphabet[t * n + (intRead(txt, ++j) - 1)];

Zadania

Zadanie 1

Na podstawie kodu źródłowego do zadania 2:

  1. Zmodyfikuj liczenie długości tekstu wynikowego deszyfrowania, aby nie polegać na znaku "/"
  2. Zmodyfikuj szyfrowanie i deszyfrowanie, aby:
    • ułamek był zapisany przy pomocy znaku :
    • zamiast średnika ";" był minus "-"
    • licznik oznaczał pozycję, a mianownik numer grupy

Przykładowo dla danych:
  1. ZYXWVUTSRQPONMLKJIHGFEDCBA
  2. 5
  3. TAJNE INFO
otrzymamy:
  1. 2:2-1:6-2:4-3:3-2:5+3:4-3:3-1:5-2:3