Jako, że na pewno wiele osób z tego portalu startowało w olimpiadzie informatycznej, to mam pytanie.
Uczę się od całkiem niedawna na poważnie do olimpiady, jestem w 2 liceum, więc to jest ostatnia szansa - dlatego intensywnie się uczę (lub przynajmniej się staram, gdy szkoła nie pozwala na niewiele poza nią).
Znam na razie tylko strukturalnie Pascala (na razie jeszcze bez implementacji dynamicznych struktur danych) i uczę się algorytmów (na razie podstawowe, będę przechodził do coraz trudniejszych).
Tutaj właśnie rodzi się pytanie, czy na OI bardziej przyda się jeżeli się nauczę C++ (oczywiście ciągle ucząc się algorytmów, poza tym znając programowanie strukturalne w pascalu to powinno mi łatwiej iść w C++), w którym można implementować biblioteki STL, czy czas ten lepiej poświęcić na naukę większej ilości algorytmów? Bo np. jeżeli mamy zadanie, to często bez znajomości odpowiednich algorytmów nie da się dojść do rozwiązania przynajmniej bliskiemu wzorcowi, na zadanie jest 2,5h, jeżeli umie się odpowiednie algorytmy i ćwiczyło się z niebieskich książeczek, to można o wiele więcej zdziałać niż z mniejszą znajomością algorytmów, a ze znajomością biblioteki STL (przynajmniej mi się tak wydaje).
Wiadomo - czas jest ważny (w 2 i 3 etapie), można by było implementować szybko struktury danych, ale czy nauka większej ilości algorytmów nie przyda się bardziej. Poza tym ile zajmuje implementacja bardziej zaawansowanych struktur danych (tj. graf, lista dwukierunkowa itp.) w pascalu zakładając ich dobrą znajomość ?
Chciałem sobie kupić książkę "Algorytmy + struktury danych = programy", gdzie są pokazane dokładnie programy z implementacjami algorytmów i struktur danych (oczywiście to jedna z wielu, które zamierzam kupić), ale jeżeli pisanie w Pascalu na OI to jest taką katorgą, to wtedy by się bardziej opłacało "Symfonię C++".
Zależy mi na odpowiedzi, ponieważ chcę wybrać najbardziej optymalne rozwiązanie, a nie mam dużo czasu (mam nadzieję uwinąć się z algorytmami do tej pory, jeszcze ponad pół roku, trochę już umiem, na wakacjach dużo czasu, a do tego na OI nie trzeba pamiętać wszystkich algorytmów jakie są w książkach, tylko te najmniejszą złożonością obliczeniową z każdej dziedziny).
Oczywiście C++ się nauczę (pewnie na najdłuższych wakacjach w życiu), ale na razie chcę się uczyć tak, żeby mieć jak największe szanse dostać się do finału OI.
Pascal jest zbyt wolny wg mnie. Weź Cormena (Tytuł: Wprowadzenie do algorytmów) do ręki i czytaj. Na początku się przerazisz, ale im wcześniej się za niego zabierzesz tym lepiej. Ja kupiłem Cormena chyba ze 2 - 3 miesiące przed OI i generalnie nie zdążyłem wtedy prawie niczego z niego zrozumieć. Poszukaj ewentualnie kogoś kto umie trochę algorytmów i niech ci pomoże z Cormenem.
Operacje na plikach/ konsoli/ etc olej całkowicie. Generalnie jedyne funkcje wbudowane z jakich będziesz korzystał na OI to printf/ scanf. Reszta to algorytmy i struktury danych. Dane są podawane na standardowe wejście, wypisywane na standardowe wyjście. Jeżeli program odpalisz za pomocą:
program < plik_wejściowy > plik_wyjściowy
to zawartość pliku plik_wejściowy zostanie wrzucona na standardowe wejście (tak jakbyć wpisywał ten plik ręcznie), a wyniki zostaną zapisane do pliku plik_wyjściowy z pominięciem wyświetlania na konsoli.
Algorytmy z najmniejszą złożonością są zwykle najtrudniejsze do zrozumienia, te wolniejsze można za to wymyślić na poczekaniu.
Pascal jest zbyt wolny wg mnie.
Jeżeli wolny w sensie działania programów, to wątpię, żeby to miało wpływ - liczy się prędkość wyrażona za pomocą notacji O.
Weź Cormena (Tytuł: Wprowadzenie do algorytmów) do ręki i czytaj. Na początku się przerazisz, ale im wcześniej się za niego zabierzesz tym lepiej. Ja kupiłem Cormena chyba ze 2 - 3 miesiące przed OI i generalnie nie zdążyłem wtedy prawie niczego z niego zrozumieć. Poszukaj ewentualnie kogoś kto umie trochę algorytmów i niech ci pomoże z Cormenem.
Oczywiście wiem o tym - mam ją wypożyczoną z biblioteki (mam pecha, bo książki tej nie ma w żadnej bibliotece tu gdzie mieszkam - jest tylko jedna biblioteka, która wypożycza z UMCSu lub KULu, ale tylko na pewien czas i przez to muszę co miesiąc nosić nosić w plecaku tą biblię i wypożyczać na nowo). Trochę już czytałem z matematyki głównie i nawet zrozumiałem o co chodzi (chociaż nie potrafiłbym np. dobrać odpowiednich stałych do notacji asymptotycznej). Na razie czytam głównie Algorytmy Sysło, która to książka zawiera opis podstawowych algorytmów, które często się również przydają. Ogólnie z literaturą nie ma problemów - dużo czytałem jakie książki są najlepsze. Na to, że mi ktoś pomoże również nie liczę - nie znam żadnego informatyka, nie licząc mojego nauczyciela, któremu się nawet nie chce kółka zrobić.
Algorytmy z najmniejszą złożonością są zwykle najtrudniejsze do zrozumienia, te wolniejsze można za to wymyślić na poczekaniu.
Ale jednak o tych ze większą można przeczytać, ale pamiętać dokładnie (wiadomo - algorytmy trzeba nie tylko zrozumieć, ale często wiele rzeczy również zapamiętać) i potrafić zaimpletować wg mnie tylko te z jak najniższą złożonością, ponieważ te kilka punktów na OI za efektywność może zaważyć o przejściu dalej.
W twoim poście nie ma dokładnej odpowiedzi na moje główne pytanie, czyli czy lepiej nauczyć się C++ z bibliotekami STL, czy większej ilości algorytmów i pisać w pascalu, ale z sensu twojej wypowiedzi wnioskuję iż ty postawiłbyś na to drugie rozwiązanie.
W C++ masz gotowe kolekcje, sporo prostych algorytmów, jeżeli umiesz to wykorzystać to jesteś ładne kilka minut do przodu w porównaniu do konkurencji klepiącej w Pascalu...
Moim zdaniem C++. Bo algorytm swoją drogą, ale jak sie nagle okaże że potrzebujesz jakąś głupią listę, mapę albo coś tego typu to w pascalu stracisz pół godziny na implementowanie struktur zamiast skorzystać z gotowych. Ale Symfonia ci się do tego nie przyda ;) Prędzej Cormen.
A programy na OI są puszczane na sprawdzarkę tak jak ta ze spoja i one liczą czas wykonania programu, ale limity są tak dobrane żeby algorytm o odpowiedniej złożoności przeszedl, a o wyzszej już nie.
Nikt tam nie liczy teoretycznej złożoności w notacji O, choćby dlatego że czasami trudno ją po prostu wyliczyć.
JumpSmerf:
Przecież jak korzystasz z STLa to nikt ci nie broni nauczyć się zasady działania tych struktur danych. Kopiec, drzewo czerwono-czarne, tablice asocjacyjne itd w ogóle struktury STLa to podstawy, nie wiem jak ty chcesz uczyć się czegoś skomplikowanego jeżeli nie wiesz co się kryje pod maską. Zresztą często będziesz musiał np wzbogacać jakieś struktury danych, np drzewa zrównoważone. Używanie STLa w takich przypadkach jest czasami niemożliwe albo nieefektywne. Np w drzewach czerwono-czarnych (chyba te są używane w STLu jako drzewa samo-równoważące się) w dowolnej operacji (np wstawianie, usuwanie) mamy stałą liczbę rotacji (tzn ograniczoną przez stałą). Można ten fakt wykorzystać do trzymania jakichś danych w węzłach trochę bardziej kosztownych do aktualizowania niż O(1).
Pascal jest zbyt wolny wg mnie.
Jeżeli wolny w sensie działania programów, to wątpię, żeby to miało wpływ - liczy się prędkość wyrażona za pomocą notacji O.
Jednak mierzony jest czas, a nie jakieś O. A źle wygenerowany kod wykonywalny może spowolnić program o rzędy wielkości.
Przykładowo, dość niewinny kod
struct Foo { };
struct Bar {
virtual void func(Foo param) {};
};
int main() {
Bar *bar = new Bar();
Foo foo;
for ( int i = 0 ; i < 100000000 ; i++ )
bar->func(foo);
delete bar;
}
kompilowany przez Visual C++ z parametrem /clr (czyli generowanie kodu dla .Net) działa u mnie około trzech minut, podczas gdy program natywny - pół sekundy.
Nie znaczy to, że .Net jest aż tak powolny - ot, błąd projektowy kompilatora. Który da się ominąć - jednak jeśli ktoś nie zna przyczyny problemu, może się naciąć.
Optymalizacje przeprowadzane przez kompilator (np. inline'owanie odpowiednich funkcji) lub ich brak mogą w pewnych sytuacjach mieć ogromny wpływ na czas działania programu - zwłaszcza w syntetycznych nieżyciowych testach, do których sprowadzają się wszelkie te olimpiady.
A kompilator Free Pascala, mimo że mam do niego duży sentyment, jest dość słaby w te klocki w porównaniu z tym, co potrafi GCC.
Chyba za bardzo się rozpisałem i nie zrozumieliście mnie dobrze. :/
A więc tak: znam (w większości) pascala, ale nie znam w ogóle C++.
Pytanie w takim razie:
Czy bardziej mi by się opłacało już tylko uczyć algorytmów i struktur danych (i na OI pisać w pascalu), czy uczyć się jeszcze do tego języka C++ (dzięki czemu mógłbym używać biblioteki STL, ale musiałbym się go nauczyć od podstaw, bo go nie umiem), ale w tej drugiej opcji musiałbym sporo czasu poświęcić na naukę C++, przez co umiałbym mniej algorytmów.
Poza tym wątpię, żeby język miał wpływ na limity - takowe są tak dobrane, że niezależnie od języka liczy się tylko wybrany algorytm (np. w niebieskich książeczkach jako programy wzorcowe są nie tylko te z C++, ale też te z Pascala - co już świadczy o tym, że liczy się algorytm).
Moim zdaniem C++. Bo algorytm swoją drogą, ale jak sie nagle okaże że potrzebujesz jakąś głupią listę, mapę albo coś tego typu to w pascalu stracisz pół godziny na implementowanie struktur zamiast skorzystać z gotowych. Ale Symfonia ci się do tego nie przyda Prędzej Cormen.
Właśnie o to mi chodzi, czy bardziej opłaca się nauczyć C++ (którego nie umiem) i oprócz tego uczyć się algorytmów i struktur danych, czy cały czas uczyć się tylko algorytmów i struktur danych i implementować je w Pascalu. Tutaj właśnie piszesz, że się oszczędza sporo czasu i właśnie czy jeżeli będę lepiej umiał algorytmy i struktury danych (i potrafił je całkiem szybko implementować), to czy straciłbym tak dużo czasu - tyle, że tak jak pisałem wcześniej bez nauki C++ poświęcę więcej czasu na algorytmy i struktury danych, a jeżeli trafiłby się taki, którego jeszcze nie przerobiłem to na pewno opcja z Pascalem o wiele bardziej się sprawdzi niż ta w C++.
Chodzi mi o to, kiedy będę miał większe szanse czy:
- przy znajomości pascala (przy czym nauczyłbym się też całkiem szybko implementować struktury danych) i większej znajomości algorytmów i struktur danych;
- przy znajomości C++ (którego obecnie nie umiem i na pewno sporo czasu by mi zajęła nauka go od podstaw), lecz nieco mniejszej algorytmów (bo część czasu musiałbym przeznaczyć na naukę języka).
Którą opcję byście wybrali na moim miejscu?
Na razie myślę bardziej o pierwszej opcji (mogę się nauczyć całkiem szybko i sprawnie implementować struktury danych, a algorytmy to najczęściej klucz do sukcesu, dodatkowo czytając niebieskie książeczki można nauczyć się uwijać z tymi programami szybciej niż jest w czasie), ale nie jestem pewien, bo czytałem opinie, iż pisanie w pascalu to masochizm i bardzo zły wybór, ale na pewno było dużo osób (szczególnie kiedyś), co korzystały z pascala na olimpiadzie - w końcu gdyby nikt z niego nie korzystał kto przechodzi dalej, to nie byłoby go już do wyboru jako jeden z języków na OI.
Mam nadzieję, że teraz rozumiecie o co się pytam. ;)
@JumpSmerf my cały czas rozumiemy o co pytasz. To ty nie rozumiesz odpowiedzi.
Nauczenie się C++ na poziomie potrzebnym do pisania algorytmów, jeśli umiesz już Pascala, to jest kwestia kilku dni. Razem z opanowaniem korzystania ze struktur danych to jest może z tydzień. No ale jeśli uważasz że wolisz pisać struktury sam w pascalu to zrób sobie mały test. Przypuśćmy że potrzebujesz w swoim rozwiązaniu drzewko czerwono-czarne. Spróbuj je sobie napisać samodzielnie, a następnie pomyśl że w C++ to by było mniej więcej
map<cośtam> treeMap;
Albo że potrzebujesz wyciągnąć z tablicy k-ty w kolejności element (ale tylko jeden, więc sortowanie się nie opłaca). W Pascalu będziesz się głowił jak tu wykorzystać magiczne piątki i szukanie mediany (jako ćwiczenie polecam sprawdzić ile czasu ci to zajmie), a w C++ napiszesz
nth_element (tablica,tablica+k,tablica+n);
I voila, mamy element k-ty na odpowiedniej pozycji.
@JumpSmerf my cały czas rozumiemy o co pytasz. To ty nie rozumiesz odpowiedzi.
Nauczenie się C++ na poziomie potrzebnym do pisania algorytmów, jeśli umiesz już Pascala, to jest kwestia kilku dni. Razem z opanowaniem korzystania ze struktur danych to jest może z tydzień. No ale jeśli uważasz że wolisz pisać struktury sam w pascalu to zrób sobie mały test.
Jeśli tak, naprawdę to kwestia kilku dni, to spoko - wtedy nie ma problemu.
Tylko właśnie czy wystarczy do nauki np. kurs ze strony main.edu.pl?
Później bym kupił Symfonię (lub wypożyczył z biblioteki, niestety na razie wiem, że mój znajomy z klasy ją posiada) i tylko bym sobie ją uzupełnił wiedzę (w końcu na main'ie jest wszystko co potrzebne do algorytmów), a jeśli ktoś myśli czemu się pascala uczyłem, zamiast C++ (niektórzy tak mogą myśleć patrząc na opinię na temat tego archaicznego języka), to pascal się na pewno przydaje do czytania książek algorytmicznych, gdzie pseudokod jest najczęściej wręcz bliźniaczo podobny do pascala).