Zadanie 1

Zapisz w wybranej przez siebie notacji (w postaci pseudokodu lub w wybranym języku programowania) algorytm, który z podanego słowa będącego ciągiem znaków składającym się z wielkich liter alfabetu łacińskiego (z pominięciem litery J) usuwa drugie i kolejne wystąpienia znaku (zachowuje jedynie pierwsze wystąpienie danej litery).

Uwaga: W zapisie algorytmu możesz wykorzystać tylko operacje arytmetyczne: dodawanie, odejmowanie, mnożenie, dzielenie, dzielenie całkowite, resztę z dzielenia, oraz porównywanie liczb; instrukcje sterujące i przypisania do zmiennych lub samodzielnie napisane funkcje zawierające wyżej wymienione operacje.

Specyfikacja problemu:

Dane:

• haslo[0..n - 1] – tablica przechowująca litery słowa, z którego mają zostać  usunięte powtarzające się litery (z zachowaniem ich pierwszych wystąpień); tablica znaków zawierająca wyłącznie wielkie litery alfabetu łacińskiego (bez litery J)

• n – zmienna przechowująca długość słowa; liczba naturalna

Wynik:

• hasloWynik[0..k - 1] – tablica przechowującą litery słowa, z którego zostały usunięte powtarzające się znaki (liczba tych liter wynosi k – rozmiar tablicy); tablica znaków zawierająca wyłącznie wielkie litery alfabetu łacińskiego (bez litery J).

Przykładowe rozwiązanie

Zaczynamy od utworzenia funkcji usunPowtorzenia. Przyjmuje ona jako parametry tablicę znaków haslo przechowującą podane słowo, a także długość tej tablicy, czyli n. Funkcja ma na celu usunięcie powtarzających się znaków z ciągu znaków haslo o długości n.

funkcja usunPowtorzenia(haslo, n):

Funkcja porówna każdą literę (element tablicy) ze znakami po niej następującymi, aby sprawdzić, czy dany znak nie został powtórzony. Rozpoczynamy pierwszą iterację pętli porównującej elementy tablicy. Indeks początkowy ustawiamy na 0, ponieważ pierwsza litera (indeks 0) nie może być powtórzeniem.

funkcja usunPowtorzenia(haslo, n):
    i ← 0
    dopóki i < n wykonuj:

Indeks i wskazuje na konkretną literę. Szukając powtórzeń, dla każdego i sprawdzamy wszystkie elementy o większym indeksie. Rozpoczynamy od ostatniej litery hasła, a kończymy na elemencie tablicy o indeksie i + 1. Tworzymy kolejną pętlę.

funkcja usunPowtorzenia(haslo, n):
    i ← 0
    dopóki i < n wykonuj:
        j ← n - 1
        dopóki j > i wykonuj:

Sprawdźmy, czy element o indeksie j ma przypisaną tę samą literę, co element o indeksie i. Jeśli tak, sprawdzany znak jest powtarzającą się literą, więc powinniśmy go usunąć. Usuwamy element o indeksie j, ponieważ przechowuje on kolejne wystąpienie litery. Wykorzystamy do tego funkcję pomocniczą usun, która usuwa znak z określonej pozycji w ciągu znaków. Funkcja przyjmuje trzy argumenty: ciąg znaków haslo, pozycję znaku do usunięcia j oraz długość ciągu n.

funkcja usunPowtorzenia(haslo, n):
    i ← 0
    dopóki i < n wykonuj:
        j ← n - 1
        dopóki j > i wykonuj:
            jeżeli haslo[i] = haslo[j]:
                usun(haslo, j, n)

Działanie funkcji polega na zastępowaniu wybranych elementów tablicy elementami o indeksie powiększonym o jeden, zaczynając od usuwanego znaku, a kończąc na przedostatniej literze w tablicy, a następnie usuwaniu ich.

Funkcja iteruje przez indeksy od j do n - 1. Danemu elementowi o indeksie i przypisuje wartość elementu o indeksie i + 1.

Po wyjściu z pętli dla ostatni element tablicy jest usuwany.

Analizując działanie funkcji usun(), możemy dojść do wniosku, że wcześniejszy wybór kolejności sprawdzania znaków w kluczu (od ostatniej litery klucza do elementu tablicy o indeksie i + 1) nie jest przypadkowy. Gdybyśmy przyjęli odwrotną kolejność, mogłoby dojść do sytuacji, w której w miejsce sprawdzonego już, powtarzającego się znaku zostałaby umieszczona ta sama litera. W rezultacie znak ten nie zostałby sprawdzony, a w kluczu znalazłyby się powtarzające się litery.

Definicja funkcji usun():

funkcja usun(haslo, j, n):
    dla i = j, j + 1, ..., n - 1 wykonuj:
        haslo[i] ← haslo[i + 1]

Minusem takiego rozwiązania jest duplikowanie ostatniego elementu tablicy – po wykonaniu przedstawionych operacji ten sam znak znajduje się na przedostatniej i ostatniej pozycji w tablicy. Tymczasem ostatnia litera powinna zostać usunięta. Aby tego dokonać, przeprowadzamy operację zmniejszenia wartości zmiennej przechowującej rozmiar tablicy po każdym wykonaniu funkcji usun(). W ten sposób pierwsza pętla funkcji usunPowtorzenia() nie będzie odczytywała znaków, które powinny zostać usunięte, czyli powtarzających się liter na końcu tabeli powstałych w wyniku działania funkcji usun(). Dodatkowo po zakończeniu operacji usuwania powtarzających się liter wartość zmiennej n będzie równa rozmiarowi tablicy z unikalnymi (niepowtarzającymi się) znakami.

funkcja usunPowtorzenia(haslo, n):
	i ← 0
	dopóki i < n wykonuj:
		j ← n - 1
		dopóki j > i wykonuj:
			jeżeli haslo[i] = haslo[j]:
				usun(haslo, j, n)
				n ← n - 1

Kolejnym krokiem jest dodanie inkrementacji i dekrementacji zmiennych sterujących:

funkcja usunPowtorzenia(haslo, n):
	i ← 0
	dopóki i < n wykonuj:
		j ← n - 1
		dopóki j > i wykonuj:
			jeżeli haslo[i] = haslo[j]:
				usun(haslo, j, n)
				n ← n - 1
			j ← j - 1          
		i ← i + 1

Następnie tworzymy nową tablicę o rozmiarze n przechowującą słowo bez powtarzających się znaków. Deklarujemy tablicę hasloWynik, a następnie zapełniamy ją pierwszymi n znakami tablicy haslo.

funkcja usunPowtorzenia(haslo, n):
	i ← 0
	dopóki i < n wykonuj:
		j ← n - 1
		dopóki j > i wykonuj:
			jeżeli haslo[i] = haslo[j]:
				usun(haslo, j, n)
				n ← n - 1
			j ← j - 1          
		i ← i + 1    

	hasloWynik[0..n - 1]

	k ← 0
	dopóki k < n wykonuj:
		hasloWynik[k] ← haslo[k]
		k ← k + 1

Na koniec zwracamy tablicę hasloWynik z niepowtarzającymi się literami.

Oto gotowy algorytm:

funkcja usun(ciagZnakow, pozycja, n):
	dla i = pozycja, pozycja + 1, ..., (n - 1) wykonuj:
		ciagZnakow[i] ← ciagZnakow[i + 1]

funkcja usunPowtorzenia(haslo, n):
	i ← 0
	dopóki i < n wykonuj:
		j ← n - 1
		dopóki j > i wykonuj:
			jeżeli haslo[i] = haslo[j]:
				usun(haslo, j, n)
				n ← n - 1
			j ← j - 1          
		i ← i + 1    

	hasloWynik[0..n - 1]

	k ← 0
	dopóki k < n wykonuj:
		hasloWynik[k] ← haslo[k]
		k ← k + 1

	zwróć hasloWynik
    
usunPowtorzenia(haslo, n)

Funkcję usun() można zaimplementować również na inne sposoby. Mogłaby na przykład zastępować powtarzające się litery białymi znakami (np. spacją).

Przykład implementacji:

funkcja usun(ciagZnakow[0..n - 1], pozycja):
	ciagZnakow[pozycja] ← ' '

W takim wypadku należy pamiętać, aby nie odczytywać białych znaków w kolejnych funkcjach będących elementem algorytmu.

Słownik