[PJWSTK] ASD – jesień 2015 – Zadanie 2 – Rozwiązanie nr 1

Drzewo binarne – najstarsze słowo – rozwiązanie nr 1 (trudniejsze)

ZADANIE NA 29.11.2015, WIĘC JESZCZE MACIE PONAD 2 TYGODNIE NA PRZEROBIENIE GO NA TYSIĄC SPOSOBÓW 🙂

Rozwiązanie nigdy nie wrzucane na spox, więc nie wiem ile punktów dostanie.

Jest to rozwiązanie TRUDNIEJSZE (w rekurencji jest złożona pętla która pozwala zaoszczędzić parę bajtów i sporo obliczeń). Za chwilę dodam wpis z rozwiązaniem łatwiejszym do zrozumienia, ale wolniejszym o jakieś 30%.

 

ZADANIE
Rozważmy niepuste drzewo binarne T etykietowane literami alfabetu angielskiego (tylko małe litery) i zapisane wierzchołkowo tak, że pozycję dowolnego wierzchołka x w drzewie T określa ciąg skierowań krawędzi (L – lewa krawędź, R – prawa krawędź) jakie pokonamy przechodząc w tym drzewie ścieżkę od korzenia do wierzchołka x.
Wyznacz najstarsze leksykograficznie słowo, jakie można zbudować z etykiet wierzchołków rozważanego drzewa występujących na dowolnej ścieżce wierzchołek zewnętrzny (liść) drzewa T – korzeń drzewa T.
WEJŚCIE
Ciąg wierszy zakończony symbolem znaku końca pliku (EOF) reprezentujący poprawnie (zgodnie z powyższym opisem) pewne drzewo binarne T. Każdy pojedynczy wiersz zakończony znakiem nowej linii (kod ASCII 10) opisujący pozycję wierzchołka w drzewie T i zawierający:
– małą literę alfabetu angielskiego (kod ASCII od 97 do 122) – etykieta wierzchołka,
– znak odstępu (kod ASCII 32),
– ciąg znaków L (kod ASCII 76) oraz R (kod ASCII 82) – ciąg skierowań krawędzi na ścieżce od korzenia drzewa do rozważanego wierzchołka.
WYJŚCIE
Wiersz zawierajacy ciąg znaków będący rozwiązaniem postawionego problemu.
OGRANICZENIA
Liczba wierzchołków drzewa T nie większa niż 10^7. Wysokość drzewa T ograniczona przez 2^6.

 

LIMITY
Złożoność czasowa O(n), złożoność pamięciowa O(n), gdzie n jest liczbą wierzchołków drzewa T.
PRZYKŁAD 1

wejście:
a LL
d
a R
s L

wyjście:
asd

ROZWIĄZANIE:

Pamiętajcie, żeby przed wrzuceniem na spoxa zmienić getchar na getchar_unlocked (w 2 miejscach):

#include <stdio.h>

class Element;

Element* aktualnyElement;

char najstarszyWyraz[65];

class Element
{
	public:
		char wartosc;
		Element* prawy;
		Element* lewy;
		Element* rodzic;
		Element()
		{
			wartosc = 0;
			prawy = NULL;
			lewy = NULL;
			rodzic = NULL;
		}

		void rekurencja()
		{
			// jesli ma lewy
			if(this->lewy)
			{
				this->lewy->rekurencja();
			}
			// jesli ma prawy
			if(this->prawy)
			{
				this->prawy->rekurencja();
			}
			// jesli nie ma lewego, ani prawego = JEST LISCIEM
			else if(!this->lewy)
			{
				aktualnyElement = this;
				register int i = 0;
				while(aktualnyElement->rodzic)
				{
					// aktualny 'najstarszyWyraz' jest krotszy od aktualnego wyrazu
					if(najstarszyWyraz[i] == NULL)
					{
						while(aktualnyElement->rodzic)
						{
							najstarszyWyraz[i] = aktualnyElement->wartosc;
							aktualnyElement = aktualnyElement->rodzic;
							++i;
						}
						najstarszyWyraz[i] = aktualnyElement->wartosc;
						// dodanie NULL na koncu wyrazu
						najstarszyWyraz[i+1] = 0;
						break;
					}
					// aktualna litera 'najstarszyWyraz' jest rowna literze aktualnego wyrazu
					// moze to byc nowy rekordzista, trzeba sprawdzac dalej
					else if(najstarszyWyraz[i] == aktualnyElement->wartosc)
					{
						aktualnyElement = aktualnyElement->rodzic;
						++i;
					}
					// aktualna litera 'najstrszyWyraz' jest nizsza, niz litera aktualnego wyrazy
					// aktualny wyraz jest rekordzista, trzeba go przepisac do konca
					else if(najstarszyWyraz[i] < aktualnyElement->wartosc)
					{
						while(aktualnyElement->rodzic)
						{
							najstarszyWyraz[i] = aktualnyElement->wartosc;
							aktualnyElement = aktualnyElement->rodzic;
							++i;
						}
						najstarszyWyraz[i] = aktualnyElement->wartosc;
						// dodanie NULL na koncu wyrazu
						najstarszyWyraz[i+1] = 0;
						break;
					}
					// aktualna litera 'najstarszyWyraz' jest wyzsza, niz aktualnego wyrazu
					// na pewno nie bedzie to nowy rekordzista
					else
					{
						break;
					}
				}
				// dodanie ostatniego elementu ktory zostal po wykonaniu petli
				// o ile nowy wyraz jest rekordzista
				if(najstarszyWyraz[i] <= aktualnyElement->wartosc)
				{
					najstarszyWyraz[i] = aktualnyElement->wartosc;
					// dodanie NULL na koncu wyrazu
					// nowy wyraz moze byc KROTSZY, niz poprzedni rekordzista
					najstarszyWyraz[i+1] = 0;
				}
			}
			// pod spodem kod do wypisywania na konsole aktualnie przegladanej litery i aktualnego rekordzisty
			//fprintf(stdout, "litera '%c' wyraz: '%s'\n", this->wartosc, najstarszyWyraz);
		}
};

int main()
{
	// czyscimy tablice z naj
	for(int i = 0; i < 65; ++i)
	{
		najstarszyWyraz[i] = 0;
	}
	register char znakNaWejsciu;
	register char wartosc = getchar();

	Element* korzen = new Element();
	aktualnyElement = korzen;

	while(!feof(stdin))
	{
		znakNaWejsciu = getchar();
		// litera 'a-z'
		if(znakNaWejsciu > 96 && znakNaWejsciu < 123)
		{
			// zapisz ostatnio zapamietana litere na elemencie na ktorym zatrzymal sie wskaznik
			aktualnyElement->wartosc = wartosc;
			// cofnij wskaznik na poczatek drzewa
			aktualnyElement = korzen;
			// zapamietaj nowa litere
			wartosc = znakNaWejsciu;
		}
		// R
		else if(znakNaWejsciu == 82)
		{
			// jesli element po prawej nie istnieje to go utworz
			if(!aktualnyElement->prawy)
			{
				aktualnyElement->prawy = new Element();
				aktualnyElement->prawy->rodzic = aktualnyElement;
			}
			// przejdz w prawo
			aktualnyElement = aktualnyElement->prawy;
		}
		// L
		else if(znakNaWejsciu == 76)
		{
			// jesli element po lewej nie istnieje to go utworz
			if(!aktualnyElement->lewy)
			{
				aktualnyElement->lewy = new Element();
				aktualnyElement->lewy->rodzic = aktualnyElement;
			}
			// przejdz w lewo
			aktualnyElement = aktualnyElement->lewy;
		}
	}

	// koniec wczytywania, wskaznik doszedl do jakiegos elementu
	// trzeba w tym elemencie zapisac ostatnio zapamietana wartosc
	aktualnyElement->wartosc = wartosc;

	// rekurencja przemieli drzewo i zapisze nam najstarszy wyraz do zmiennej
	korzen->rekurencja();
	fprintf(stdout, "%s", najstarszyWyraz);
	return 0;
}
Ten wpis został opublikowany w kategorii Bez kategorii, PJWSTK - ASD. Dodaj zakładkę do bezpośredniego odnośnika.

4 odpowiedzi na [PJWSTK] ASD – jesień 2015 – Zadanie 2 – Rozwiązanie nr 1

  1. Pingback: [PJWSTK] ASD – jesień 2015 – Zadanie 2 – Rozwiązanie nr 2 | Wszystko czego potrzebują studenci

  2. Marta pisze:

    próbuję pobawić się Twoim rozwiązaniem, ale wywala mi non stop SIGSEGV i nie wiem, jak to rozwiązać 🙁 jakiś pomysł?

    • Jerzy Skalski pisze:

      A jakich danych używasz? Jakiego środowiska (linux, code blocks, visual studio, …)? Na spoxie?

      Wstaw w komentarzu treść zadania aktualną, bo może się różnić np. maksymalna wysokość drzewa i już jest SIGSEGV.
      —————-
      Na próbę skompilowałem to w Visual Studio 2013 jako Projekt Visual C++ -> Console Application, a potem odpaliłem z wiersza poleceń 'ConsoleApplication2.exe < text.txt' (w text.txt mam ten przykład z 'asd' tekstem) i zadziałało bez problemów.

      • PW pisze:

        Treść:

        ZADANIE

        Rozważmy niepuste drzewo binarne T etykietowane literami alfabetu angielskiego (tylko małe litery) i zapisane wierzchołkowo tak, że pozycję dowolnego wierzchołka x w drzewie T określa ciąg skierowań krawędzi (L – lewa krawędź, R – prawa krawędź), jakie pokonamy przechodząc w tym drzewie ścieżkę od korzenia do wierzchołka x.

        Wyznacz najstarsze (największe) leksykograficznie słowo, jakie można zbudować z etykiet wierzchołków rozważanego drzewa występujących na dowolnej ścieżce wierzchołek zewnętrzny (liść) drzewa T – korzeń drzewa T.

        WEJŚCIE

        Ciąg wierszy zakończony symbolem znaku końca pliku (EOF) reprezentujący poprawnie (zgodnie z powyższym opisem) pewne drzewo binarne T. Każdy pojedynczy wiersz zakończony znakiem nowej linii (kod ASCII 10) opisujący pozycję wierzchołka w drzewie T i zawierający:

        – małą literę alfabetu angielskiego (kod ASCII od 97 do 122) – etykieta wierzchołka,

        – znak odstępu (kod ASCII 32),

        – ciąg znaków L (kod ASCII 76) oraz R (kod ASCII 82) – ciąg skierowań krawędzi na ścieżce od korzenia drzewa do rozważanego wierzchołka.

        WYJŚCIE

        Wiersz zakończony znakiem nowej linii, zawierający ciąg znaków stanowiący rozwiązanie postawionego problemu.

        Dodatkowo: wiersz zawierający liczbę kontrolną równą liczbie znaków właściwych wczytanych z wejścia (znak właściwy to każdy znak niebędący znakiem białym, tj. znak odstępu, znak nowej linii, znak tabulacji, oraz znakiem końca pliku, tj. EOF).

        OGRANICZENIA

        Liczba wierzchołków drzewa T nie większa niż 10^7. Wysokość drzewa T ograniczona przez 2^6.

        PRZYKŁAD 1

        wejście:

        a LL

        d

        a R

        s L

        wyjście:

        asd

        8

Skomentuj PW Anuluj pisanie odpowiedzi

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *