Przyspieszenie algorytmu

Mógłby mi ktoś wskazać stronę, w którą pójść, aby przyspieszyć algorytm?

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
	int przebiegi;
	cin >> przebiegi;

	for (int i = 0; i < przebiegi; i++)
	{
		vector <string> tablica;

		int slowa;
		cin >> slowa;

		for (int x = 0; x < slowa; x++)
		{
			string slowo, tmp;
			cin >> slowo;
			
			tmp+=slowo[0];
			tmp+=slowo[slowo.length()-1];
			tablica.push_back(tmp);
		}

		for (int s = 0; s < tablica.size(); s++)
			for (int x = 0; x < tablica.size()-1; x++)
				if (tablica[x][1] != tablica[x+1][0])
					swap(tablica[x], tablica[x+1]);

		bool tmp = true;
		for (int x = 0; x < tablica.size()-1; x++)
			if (tablica[x][1] != tablica[x+1][0])
			{
				tmp = false;
				break;
			}

		tmp ? cout << "Ordering is possible." << endl : cout <<  "The door cannot be opened." <<endl;
	}

	return 0;
}

Przykładowe wejście:

1
2
mo
om

Wyjście
Ordering is possible.

Rozumiem że nie warto nam mówić CO ten kod ma robić bo algorytm jest na pewno najoptymalniejszy?

Wyglada na sprawdzanie czy da sie posortowac wyrazy, tak by kazdy nastepny zaczynal sie na litere konczaca poprzedni. Pewnie zadanie na jakis konkurs. Przede wszystkim sortujesz, a masz tylko sprawdzic. Po drugie uzywasz do tego najgorszego sortowania jakie mogles wybrac (choc istnieje co najmniej jeden gorszy :P ). Skup sie na tym, zeby sprawdzic czy sie da bez potrzeby wlasciwego sortowania.

Dobra w takim razie:

• nie używaj <vector> bo wiesz ile będzie danych, użyj tablic dynamicznych
• nie sortuj bąbelkowo, jak nie umiesz/nie chcesz nic innego pisac to sort() z <algorithm>

ja bym powiedział, że sortowanie jest zupełnie zbędne. Raczej trzeba policzyć typy połączeń i na tej podstawie stwierdzić czy jest możliwe stworzenie łańcucha.

// edit: oczywiście zakładając, że johny dobrze się domyśla co to ma robić

Shalom napisał(a)

• nie używaj <vector> bo wiesz ile będzie danych, użyj tablic dynamicznych
  resize() itp. wciąż istnieją, nie trzeba koniecznie walić po push_back na element, można zrobić N elementów raz a potem się nimi bawić.

Treść jest następująca: http://0f48.skroc.pl
Zaraz przepiszę to i sprawdzę, czy zadziała.

#include <iostream>
#include <string>

using namespace std;

int main()
{
        int przebiegi;
        cin >> przebiegi;

        for (int i = 0; i < przebiegi; i++)
        {
                int slowa;
                cin >> slowa;

                string *tablica = new string[slowa];

                for (int x = 0; x < slowa; x++)
                {
                        string slowo, tmp;
                        cin >> slowo;
                        
                        tmp+=slowo[0];
                        tmp+=slowo[slowo.length()-1];
                        tablica[x] = tmp;
                }

                for (int s = 0; s < slowa; s++)
                        for (int x = 0; x < slowa-1; x++)
                                if (tablica[x][1] != tablica[x+1][0])
                                        swap(tablica[x], tablica[x+1]);

                bool tmp = true;
                for (int x = 0; x < slowa-1; x++)
                        if (tablica[x][1] != tablica[x+1][0])
                        {
                                tmp = false;
                                break;
                        }

                tmp ? cout << "Ordering is possible." << endl : cout <<  "The door cannot be opened." <<endl;
        }

        return 0;
}

Dalej za wolno.

To przeczytaj reszte uwag... ;) Dobrze przeczytalem :)

W takim razie jaki algorytm wybrać?

adam.chyla napisał(a)

                for (int x = 0; x < slowa; x++)
                {
                        string slowo, tmp;
                        cin >> slowo;
                       
                        tmp+=slowo[0];
                        tmp+=slowo[slowo.length()-1];
                        tablica[x] = tmp;
                }
 

Dalej za wolno.

1. po co deklarujesz to string slowo tmp za kazdym przebiegiem petli, alokacja 2 stringow za kazdym przebiegiem troche trwa
2. tablica[x] = tmp; - skad masz pewnosc ze po wyjsciu z tego for obiekty tmp beda jeszcze istniec albo nie zostana nadpisane? edit. w sumie jesli to jest string powinien zadzialac operator = ale to znowu spowalnie
3. operacje na string sa dosc wolne, czy nie lepiej przepisac ten kod i uzyc normalnego unsigned char* jako typu danych?

EgonOlsen napisał(a)

2. tablica[x] = tmp; - skad masz pewnosc ze po wyjsciu z tego for obiekty tmp beda jeszcze istniec albo nie zostana nadpisane? edit. w sumie jesli to jest string powinien zadzialac operator = ale to znowu spowalnie
   Przecież wpisuję wartość do tablicy, a nie adres do wartości, więc nie wiem o co Tobie chodzi.

Dostales odpowiedz, sortowanie jest zbedne. Wystarczy sprawdzic czy ilosc odpowiadajacych sobie pierwszych i ostatnich liter jest taka sama z dokladnoscia do jednej nadmiarowej pierwszej i ostatniej (pierwszego i ostatniego slowa). Jesli bedzie taka sama, to powstanie pierscien.

adam.chyla napisał(a)

EgonOlsen napisał(a)

2. tablica[x] = tmp; - skad masz pewnosc ze po wyjsciu z tego for obiekty tmp beda jeszcze istniec albo nie zostana nadpisane? edit. w sumie jesli to jest string powinien zadzialac operator = ale to znowu spowalnie
   Przecież wpisuję wartość do tablicy, a nie adres do wartości, więc nie wiem o co Tobie chodzi.

No to napisalem ze zadziala operator = , chodzi mi o to ze string jest powolny w porownaniu z operacjami bezposrednio na pamieci.

A taki przykład:

ol
lo
ll
uu
ut

Powinno wykazać błąd.

io
oo
ol

Powinno pokazać ok.

Wystarczy sprawdzic czy ilosc odpowiadajacych sobie pierwszych i ostatnich liter jest taka sama z dokladnoscia do jednej nadmiarowej pierwszej i ostatniej (pierwszego i ostatniego slowa).

Liczby się zgadzają.

a ja się upieram przy swoim, policzyć ile słów zaczyna się na kolejne litery ile kończy się na dane litery.
Ułożenie ciągu słów jest możliwe, gdy różnica liczb słów rozpoczynających się i kończących się na daną literę jest równa zero, poza dwoma literami, które zaczynają i kończą ciąg (dla nich różnica ma wymościć 1 i -1 lub 0 i 0).

Mógłbyś zademonstrować na jakimś przykładzie?

cha zapomniałem o cyklach (wielu). Czyli mój warunek jest tylko warunkiem koniecznym, ale nie wystarczającym :P.
Najprostszy przykład negatywny:

aa
bb

Tu na pewno przydała by się teoria grafów, ale z tej wiedzy mam braki