[PJWSTK] ASD – Kolokwium 3 – Rozwiązanie

Opublikowano 17 listopada 2012, autor: Jerzy Skalski

Trzecie zadanie z ASD:

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ź, P – prawa krawędź) jakie pokonamy przechodząc w drzewie T ścieżkę od korzenia do wierzchołka x (przykłady poniżej).

Wyznacz najstarsze leksykograficznie słowo, jakie można zbudować z etykiet wierzchołków 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 w sposób poprawny pewne drzewo binarne T. Każdy pojedynczy wiersz zakończony znakiem nowego wiersza/linii (ASCII kod 10) opisujący pozycję wierzchołka w drzewie T i zawierający:

małą literę alfabetu nagielskiego (ASCII kod od 97 do 122) – etykieta wirzchołka,
znak odstępu/spacji (ASCII kod 32),
ciąg znaków L (ASCII kod 76) oraz R (ASCII kod 82) – ciąg skierowań krawędzi.
Liczba wierzchołków drzwa T ograniczona zawarta w przedziale [1,10^6]. Wysokość drzewa T ograniczona przez 2^6.

Wyjście

Wiersz zawierajacy ciąg znaków będący rozwiązaniem postawionego problemu.

Złożoności i limity

Złożoność czasowa O(nh), złożoność pamięciowa O(n) bez uwzględnienia kosztów mechanizmu rekursji, gdzie n jest liczbą wierzchołków drzewa T a h jest jego wysokością. Fizyczny limit pamięci, bez uwzględnienia kosztu mechanizmu rekursji, zależny od rozmiaru danych wejściowych i ograniczony przez 10n B+1 KB.

Przykład 1

Wejście:
a LL
d
a R
s L

Wyjście:
asd
Przykład 2

Wejście:
s LR
o LRR
m RR
p LRLRL
k
w LRL
a LL
t L
h R
j LRLR

Wyjście:
pjwstk

Jedno z wielu możliwych rozwiązań:

#include<iostream>
using namespace std;

class Element
{
    public:
	char value;
	Element* left;
	Element* right;
	Element()
	{
		value = NULL;
		left = NULL;
		right = NULL;
	}
};

void showTree(Element* element)
{
	if(element->left)
		showTree(element->left);
	if(element->right)
		showTree(element->right);
	cout << element->value;
}

char isOneNode(Element* element)
{
	if(element->left && element->right)
		return 0;
	else if(element->left)
		return isOneNode(element->left);
	else if(element->right)
		return isOneNode(element->right);
	else
		return 1;
}

char getTheBest(Element* element)
{
	char r1 = 0;
	char r2 = 0;
	if(!element->left && !element->right)
	{
		return element->value - 70;
	}
	else
	{
		if(element->left)
		{
			r1 = getTheBest(element->left);
		}
		if(element->right)
		{
			r2 = getTheBest(element->right);
		}
	}
	if(r1 != 0 && r1 < 90)
	{
		delete element->left;
		element->left = NULL;
		r1 = r1 + 70;
	}
	if(r2 != 0 && r2 < 90)
	{
		delete element->right;
		element->right = NULL;
		r2 = r2 + 70;
	}
	if(r1 > r2)
	{
		delete element->right;
		element->right = NULL;
		return r1;
	}
	else if(r1 < r2)
	{
		delete element->left;
		element->left = NULL;
		return r2;
	}
	return r2;
}

int main()
{
	char lastChar;
	char tmpChar;
	Element* root = new Element();
	Element* currentNode = root;
	cin >> lastChar;
	while(cin >> tmpChar)
	{
		if(tmpChar == 'L')
		{
			if(currentNode->left == NULL)
			{
				currentNode->left = new Element();
			}
			currentNode = currentNode->left;
		}
		else if(tmpChar == 'R')
		{
			if(currentNode->right == NULL)
			{
				currentNode->right = new Element();
			}
			currentNode = currentNode->right;
		}
		else
		{
			currentNode->value = lastChar;
			lastChar = tmpChar;
			currentNode = root;
		}
	}
	currentNode->value = lastChar;
	while(!isOneNode(root))
	{
		cout << getTheBest(root);
	}
	showTree(root);
	return 0;
}
Post Views: 14 684
Ten wpis został opublikowany w kategorii PJWSTK, PJWSTK - ASD. Dodaj zakładkę do bezpośredniego odnośnika.

14 odpowiedzi na [PJWSTK] ASD – Kolokwium 3 – Rozwiązanie

    • Jerzy Skalski pisze:
      20 kwietnia 2014 o 02:30

      Rozwiązanie 'prawie’ takie samo co w kodzie z poprzednich lat. Trzeba tylko ogarnąć jak działa moje rozwiązanie i czym się różni stare polecenie od nowego. Trzeba też niestety ogarnąć dlaczego ja robiłem jakieś porównania mniejsze/większe od 90 i odejmowałem/dodawałem 70 do liczby (żeby zmieścić 2 wartości 97-122 [litery] w jednym bajcie). Jeśli dobrze pamiętam można to zastąpić przekazując do funkcji 'getTheBest’ dodatkowo wskaźnik na jeden bajt (w waszym przypadku to już chyba 2 x INT, bo mają być 2 liczby 32 bitowe).
      Niestety ja nie mam czasu nad tym pracować, bo za dużo mam własnych projektów na trzecim roku.

      Podsumowując moje rozwiązanie:
      1. buduje drzewo binarne
      2. idzie do liści drzewa
      3. zaczyna 'ciąć’ gałęzie które mają 'niższą’ literę na końcu i wyświetlać 'najwyższą’ literę jaka jest na jakimś liściu
      4. jeśli w wyniku kolejnych tur cięcia gałęzi zostanie tylko jedna gałąź to ją wyświetla

      W waszym przypadku nie chodzi [chyba] o szukanie najniższej wartości na liściach tylko najniższej sumy od liścia do korzenia (więc trochę więcej zachodu z tym będzie?).

      Na początek polecam napisać kilka różnych struktur np. wersje przechowującą dodatkowo wskaźnik 'parent’ (nie tylko na 'dzieci’ left/right) i wersje z 'listą’ wszystkich elementów drzewa oprócz samego drzewa binarnego (z listą można baardzo łatwo napisać algorytm który rozwiąże dany problem, ale będzie miał dużą złożoność obliczeniową i pamięciową, ale zawsze lepiej 60% niż 0% dostać) – i zobaczyć jaki będzie sam czas ładowania danych na spoxie, bez wyszukiwania wyniku nawet.

      Mogę jutro napisać rozwiązanie tego problemu (niedziela), ale będzie to rozwiązanie absolutnie najgorsze! Jak ktoś chce przetestować na spox (wynik pewnie z 20%, ale może i 100% jak dane będą MIŁE 🙂 ) to niech napisze swoją e_S_kę w odpowiedzi. Nie będę tu postował, żeby kilka osób nie miało tego samego,

      Odpowiedz
      • ... pisze:
        21 kwietnia 2014 o 20:18

        Mógłbyś wrzucić samą funkcję wczytującą dane bo nie mogę sobie poradzić z minusami?

        Odpowiedz
        • Jerzy Skalski pisze:
          22 kwietnia 2014 o 01:29

          Wersja z listą wszystkich elementów i 'parent’ – banalny algorytm:
          http://paste.ots.me/560669/text
          Wersja bez listy, ale z 'parent’ – prosty algorytm (modyfikacja showTree(x) żeby liczyło koszt):
          http://paste.ots.me/560670/text
          Wersja bez listy i bez 'parent’ – trudny algorytm (obejrzyjcie mój kod z głównego wpisu, tam jest sprawdzanie rekurencyjnie, u was musi być z tego zrobione licznie):
          http://paste.ots.me/560671/text

          Kody do wyświetlania załadowanych danych są w komentarzach.
          Najprościej 'showTree’ przerobić, żeby 'jesli liść’ to leciało po 'parent’ i liczyło koszt w 'while’ i zapisywało do zmiennej min/max 'jesli nowy rekord’. Oczywiście czas wykonania był by dużo niższy jeśli do 'showTree’ przekazało by się oprócz 'Element*’ dodatkowo 2 wskaźniki na 'int’ z min/max wartością i po policzeniu lewego i prawego zapisywalo by się lepszy min/max z obu ramion. W ten sposób po wykonaniu calego algorytmu miało by się wartosci min/max w zmiennych. Trzeba jednak uwzglednic dlugi czas na deklaracje nowych zmiennych.

          UWAGA: PRZESTRZEGAM PRZED BŁĘDAMI ZWIĄZANYMI Z DANYMI JAKIE DAJECIE NA WEJŚCIU!
          Upewnijcie się, że plik zawiera to co powinien bez zbędnych znaków (np. 'nowa linia’ składająca się z '\r\n’ zamiast '\n’). Na linux można przejrzeć plik funkcją:
          od -c nazwa
          Przykładowy plik z danymi z pierwszego przykładu:
          http://gamescraft.net/dane1.txt
          Wygląda tak:
          0000000 3 L L \n 5 \n – 8 R \n 1 L \n
          0000020 – 2 L R
          0000025

          Odpowiedz
        • Jerzy Skalski pisze:
          22 kwietnia 2014 o 11:52

          Trochę głupot chyba napisałem z tym, że trzeba 2 parametry przekazywać i cuda wyczyniać. Wydaje mi się, że wystarczy drzewo przeglądać w kolejności pre/post/in order i przekazywać tylko rekurencyjnie ile kosztowało dojście do 'teraz’ -czyli przerobione 'showTree(Element* element, long koszt)’ lub 'showTree(Element* element, Element* rodzic)’ [jeśli w elemencie by się trzymało koszt dojścia]. W ten sposób każdy element będzie znał koszt dojścia do niego samego. Wystarczy dodać, żeby sprawdzał czy nie jest liściem i jak jest to, żeby koszt porównywał z rekordami min/max.

          W takim wypadku wystarczy drzewo bez listy i bez parent. Można w nim ewentualnie przechowywac 'long kosztDojscia’ – do rozważenia po dokładniejszym zapoznaniu się z działaniem algorytmu.

          Odpowiedz
  2. Jerzy Skalski pisze:
    20 kwietnia 2015 o 11:13

    Rozwiązanie z pierwszego wpisu jest w 100% zgodne z tegorocznym poleceniem, więc nie wiem jak ktoś może te darmowe 100% przegapić. Jedyne co trzeba zrobić to zmienić wczytywanie na metode z mojego innego wpisu na temat szybkiego wczytywania intów [ getchar_unlocked() ].

    Oczywiscie trzeba tez to tak przerobic, zeby plagiator tego nie wykryl 🙂

    Odpowiedz
    • xyz pisze:
      7 maja 2015 o 17:58

      jaki plagiator? z zad2 wrzuciłem kod z tej strony, z usunięciem jednej spacji tylko i przeszło 😉

      Odpowiedz
    • KGN pisze:
      8 maja 2015 o 14:02

      To właśnie dziwne bo próbowałem z tą inną metodą, oczywiście zmieniając wszystko tak aby działało na char’ach ale to tylko pogorszyło czas wczytywania

      Odpowiedz
      • Jerzy Skalski pisze:
        8 maja 2015 o 14:47

        Mogę tylko napisać, że z inną (odpowiednią, tu jest wczytywanie do końca pliku, a nie określonej ilości znaków jak w poprzednich poleceniach, wiec trzeba użyc 'eof()’ w odpowiednich częściach kodu 'szybkie wczytywanie’) wersją kodu na szybkie wczytywanie można nabić 100%.

        Odpowiedz
  3. qwerty pisze:
    9 maja 2015 o 10:56

    Co znaczy by zmodyfikowac kod aby plagiator nie wykryl? Z tego co wiem to nawet zmiana nazw zmiennych nic nie da. Raczej przemieszczanie linii kodu tez nie. A mocniejsze zmiany psuja caly kod… nie bardzo rozumiem wiec jak to edytowac. Nawet jak juz mam zmienione na szybkie wczytywanie. Jakies wskazowki? Porady. Nie chodzi mi o wskazywanie palcem co na co zmienoc.

    Odpowiedz
    • Jerzy Skalski pisze:
      9 maja 2015 o 21:21

      Zmienić nazwy zmiennych, klasy, funkcji, a potem zmienić kolejność deklarowania zmiennych, pętle 'for’ na 'while’ i odwrotnie.
      Czasem są 'if’ z kilkoma warunkami i akurat da się zmienić nie psując logiki programu.
      Czasem jak się liczy, że będzie 'nadwyżka czasu’ to można język z C na C++ zmienić i odwrotnie, a w niektórych przypadkach nawet na Jave.

      Odpowiedz

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

Dodaj komentarz

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