Rashmistrz Temat założony przez niniejszego użytkownika |
[C++] Zadanie "Taśma" » 2014-12-11 16:08:00 Rozwiązuję zadanie z MAIN2 pt."Taśma". Program działa bez zarzutu przy małych liczbach, jednak przy dużym "zestawie danych" za długo pracuje, tzn. przy sprawdzaniu przez system sprawdzający wyrzuca: "Przekroczenie limitu czasu"... (o 10ms-60ms) Jak ten program można zoptymalizować lub zmienić? Mój kod: #include <iostream> using std::cin; using std::cout;
inline int szukaj( int liczby[], register int dlugosc_sekwencji ) { register int a, b, c; a = dlugosc_sekwencji; for(; c =--a, a != 0; ) for( b = 0; c != dlugosc_sekwencji; ) if( liczby[ b++ ] != liczby[ c++ ] ) return c - b; return 0; }
int main() { register int dlugosc_sekwencji; cin >> dlugosc_sekwencji; int liczby[ dlugosc_sekwencji ]; for( register int a = 0; a < dlugosc_sekwencji; ++a ) cin >> liczby[ a ]; int sprawdzono = szukaj( liczby, dlugosc_sekwencji ); if( sprawdzono ) cout << sprawdzono; else cout << "BRAK"; return 0; } Treść zadania: (Dostępna pamięć: 256 MB.) 6–12.12.2014
"Taśma"Jaś przypadkowo znalazł w domu bardzo długą taśmę. Bez chwili namysłu napisał na taśmie pewien ciąg liczb całkowitych dodatnich. Teraz chciałby znaleźć w tym ciągu dwie najdalej od siebie położone różne liczby. Zakładamy, że odległość między sąsiednimi liczbami to 1, między liczbami posiadającymi wspólnego sąsiada to 2 itd.
WejściePierwszy wiersz wejścia zawiera jedną liczbę całkowitą "n" (1≤n≤500000), oznaczającą długość sekwencji liczb zapisanej przez Jasia na taśmie. Drugi wiersz zawiera ciąg "n" liczb całkowitych ai(1≤ai≤1000000000), oddzielonych spacjami.
WyjścieJeżeli w podanym na wejściu ciągu nie ma żadnej pary różnych liczb, to "i"-ty wiersz powinien zawierać jedno słowo „BRAK”. W przeciwnym przypadku w "i-tym" wierszu powinna znajdować się jedna liczba całkowita, równa odległości między najdalszą parą różnych liczb w ciągu. __________________________________________________________
Przykład Dla danych wejściowych: 8 2 5 4 7 3 4 5 2 poprawnym wynikiem jest: 6
Wyjaśnienie do przykładu: Najdalszymi różnymi liczbami w sekwencji są m.in. pierwsza (czyli 2) i siódma (czyli 5).
Natomiast dla danych wejściowych: 3 7 7 7 poprawnym wynikiem jest: BRAK |
Wcześniej omawiane kwestie: zawiesza się - zwraca komunikat
bool przesuniecia[ d ]; po tej operacji czy na petli while | "Program działa bez zarzutu"...
Wiem, że ten działanie jest złe, ale nie znam się jeszcze na dynamicznej alokacji, więc tak zostało z mojej "zieloności". |
jak rozumiesz optymalizację programu ? | Zrobienie coś z nim by zwrócił on prawidłowy wynik w krótszym czasie. |
//EDIT: (drobne podpowiedzi dostałem) hm, ciężko coś poradzić nie mówiąc rozwiązania od razu, bo rozwiązanie jest generalnie bardzo proste... tylko wymaga jednej obserwacji
generalnie trzeba zauważyć, że jedna liczba z tej wynikowej pary będzie "jakaś szczególna" |
|
|
pekfos |
» 2014-12-11 17:12:09 Użyj i/o z C, a nie C++. |
|
NopeDotAvi |
» 2014-12-11 17:19:01 cin >> dlugosc_sekwencji; int liczby[ dlugosc_sekwencji ]; tak się nie tworzy tablic. możesz użyć vectora. czemu tablicy nie przekazujesz przez wskaźnik i długości sekwencji przez referencje? |
|
Rashmistrz Temat założony przez niniejszego użytkownika |
» 2014-12-11 19:37:16 ??? tak się nie tworzy tablic. |
Wcześniej omawiane kwestie: | Wiem, że te działanie jest złe, ale nie znam się jeszcze na dynamicznej alokacji, więc tak zostało z mojej "zieloności". |
Zobaczę co da się z tym zrobić. czemu tablicy nie przekazujesz przez wskaźnik |
A noż nie umiem... i długości sekwencji przez referencje? |
Ma to jakieś znaczenie przy "inline"? //EDIT: Modyfikator register "daje do zrozumienia" kompilatorowi, że zależy nam na szybkim dostępie do zmiennej, gdyż będziemy jej używać dużo razy i należy ją umieścić w rejestrze procesora. Nie możemy się odwoływać do zmiennej z modyfikatorem register o jej adres. Rejestr nie jest adresem pamięci, gdy usilnie próbujemy dowiadywać się jednak o jej adres, kompilator umieści zmienną w pamięci (gdzie może nam podać adres). |
Moje pytanie jest takie: Jak przy zagnieżdżonych pętlach wyjść z nich wszystkich na raz? |
|
akwes |
» 2014-12-11 19:54:12 Zmień algorytm. O(N^2) to za dużo. Wygląda, że łatwo to zrobić w O(2N) |
|
Rashmistrz Temat założony przez niniejszego użytkownika |
» 2014-12-11 20:10:03 Zmień algorytm. O(N^2) to za dużo. |
Tyle obliczeń wykona tylko wtedy kiedy są wszystkie sobie równe... Można by więc na początku sprawdzić czy wszystkie sobie są równe? Wygląda, że łatwo to zrobić w O(2N) |
Właśnie nie mam żadnej innej koncepcji jak to łatwo wykonać. :C |
|
NopeDotAvi |
» 2014-12-11 20:11:25 "Jak przy zagnieżdżonych pętlach wyjść z nich wszystkich na raz?"
goto jest dobrym rozwiązaniem lub return jeżeli jesteś w funkcji jakiejś |
|
akwes |
» 2014-12-11 20:14:08 Tyle obliczeń wykona tylko wtedy kiedy są wszystkie sobie równe... Można by więc na początku sprawdzić czy wszystkie sobie są równe?
|
Ile wykona? O(N^2)? To jest złożoność a nie wzór na ilość wykonań. Poczytaj co oznacza złożoność. Mówiąc prościej: kiedy nie są sobie równe i tak wykona dużo. Właśnie nie mam żadnej innej koncepcji jak to łatwo wykonać. :C
|
Czyli nie masz żadnej koncepcji, teraz robisz to siłowo sprawdzając wszystkie kombinacje. W tych zadaniach nie chodzi o to, aby zakodować coś, ale aby wymyślić algorytm. Jak ktoś Ci poda rozwiązanie, to nic z tego zadania. Sama złożoność już tutaj jest dużą podpowiedzią. Pomyśl jak wykonać to zadanie tylko dwa razy przeglądając tablicę. // goto jest dobrym rozwiązaniem
|
Oczywiście, że nie jest. Pętlą sterujemy przez continue , break , return oraz dobrze skonstruowany warunek pętli. |
|
« 1 » 2 3 |