Przygotowanie do OI

0

Witam wszystkich.
Będąc aktualnie w 1 klasie LO i znając podstawy C++ postanowiłem wziąć się z olimpiadę informatyczną, i w związku z tym pytanie od czego zacząć ??

mam w planie zakup "wprowadzenia do algorytmów" Cormena ale nie wiem czy nie lepiej
najpierw podszlifować swojego c++.

podobno przydatna jest umiejętność programowania funkcyjnego,
czy można to wykorzystać w c++ ?

A na koniec ile ok. czasu może zająć solidne przygotowanie do OI-a ?
Wszelkie porady i sugestie bardzo mile widziane ;-)
Pozdrawiam

0

Olimpiada Informatyczna jest ciężkim konkursem. Tutaj język programowania to tylko narzędzie. Żeby brać się za OI musisz mieć świetnie opanowane C++, ale też bogatą wiedzę z zakresu algorytmiki (dlatego ja się za OI nie biorę :P).
Najlepiej spróbuj rozwiązać zadania z którejś z poprzednich edycji i zobacz, czy dasz radę.
Oczywiście najważniejsza jest tu umiejętność analitycznego myślenia.
Jeśli chodzi o programowanie funkcyjne, to oczywiście, że można. I założę się, że Ty go już używasz.
Programowanie funkcyjne w dużym skrócie polega na tym, że każdą operację obsługuje pewna funkcja. Sam program to po prostu odpowiednie wywoływanie tych funkcji.
Ile czasu?
To zależy od tego co już umiesz. Na pewno kilka miesięcy, aby dobrze poznać tajniki c++ i nauczyć się kilku przydatnych algorytmów. Jednak w pierwszej klasie będzie Ci ciężko przez to przebrnąć, bo wiele algorytmów wykorzystuje pojęcia matematyczne, które mogą nie być Ci znane.

0
heux napisał(a)

Jeśli chodzi o programowanie funkcyjne, to oczywiście, że można. I założę się, że Ty go już używasz.
Programowanie funkcyjne w dużym skrócie polega na tym, że każdą operację obsługuje pewna funkcja. Sam program to po prostu odpowiednie wywoływanie tych funkcji.

A ja się założę, że nie używa. Może chodzi Ci o proceduralne? Na OI nie ma na programowanie funkcyjne miejsca, bo nie ma tam żadnego języka funkcyjnego...

To zależy od tego co już umiesz. Na pewno kilka miesięcy, aby dobrze poznać tajniki c++ i nauczyć się kilku przydatnych algorytmów. Jednak w pierwszej klasie będzie Ci ciężko przez to przebrnąć, bo wiele algorytmów wykorzystuje pojęcia matematyczne, które mogą nie być Ci znane.

A daj spokój, nawet nie trzeba znać języka specjalnie. Jak już usiądziesz przy zadaniu na czas, to naprawdę wątpliwe jest żebyś projektował klasy czy odwoływał się do STLa. Programy, które dostają setkę nie są pisane w szczególnie ładny sposób, bo to sam algorytm jest ważny.

Do autora tematu - przejść do 2 etapu nie jest wcale trudno, zwłaszcza, że z roku na rok obniża się pułap (AFAIR). Kolejne etapy wymagają kojarzenia większości znanych algorytmów i umiejętności przeprojektowania ich. A to już wcale nie jest takie łatwe do nauczenia, czasem wydaje mi się, że tego się w ogóle nie można nauczyć jeśli nie urodziłeś się z głową do algorytmów :-D

0

hmm oi mam za soba, poznalem wielu ciekawych ludzi, polecam ten konkurs, ogolnie jezeli myslisz o oi na powaznie to nie skupiaj sie na programowaniu jako takim bo nie tego ta olimpiada dotyczy, przede wszystkim algorytmika i matematyka, a wiec musisz opanowac:

algorytmy i struktory danych
matematyka dyskretna
kombinatoryka
algebra liniowa
geometria analityczna

co do treningu to na poczatek najbardziej rozwijajace beda niebieskie ksiazeczki z poprzednich olimpiad, tyle ze aby z nich korzystac musisz miec juz jakas wiedze
ogolnie zycze powodzenia :)

0

Sorki za offtopa, ale nie zdzierżyłem: ;)

heux napisał(a)

Jeśli chodzi o programowanie funkcyjne, to oczywiście, że można. I założę się, że Ty go już używasz.
Programowanie funkcyjne w dużym skrócie polega na tym, że każdą operację obsługuje pewna funkcja. Sam program to po prostu odpowiednie wywoływanie tych funkcji..

Czy ty mylisz programowanie funkcyjne z proceduralnym, zakładasz, że Jarno pomylił czy chcesz namieszać komuś w głowie? W każdym razie twój opis co prawda pasuje do programowania funkcyjnego, ale znacznie lepiej pasuje do programowania proceduralnego (http://en.wikipedia.org/wiki/Procedural_programming, i nie, procedura != funkcja bez parametrów. Procedura to podprogram, funkcja to pojęcie matematyczne). Programowanie funkcyjne (http://en.wikipedia.org/wiki/Functional_programming) to paradygmat programowania języków takich jak np. Haskell, gdzie praktycznie nie ma czegoś takiego jak stan programu (poza sytuacjami typu I/O), każda funkcja wywołana dwa razy z tymi samymi argumentami daje taką samą wartość (tak jak w matematyce np. 6! zawsze równa się 720) itp. I nie, nie wydaje mi się by tego typu języki były dozwolone na OI (przynajmniej kiedy ostatnio sprawdzałem to były tylko języki typu C++ czy Pascal), choć IMHO powinny, w końcu większość z zadań idealnie wstrzeliwuje się w zakres zastosowań języków funkcyjnych. Ale umiejętność programowanie w tych językach na pewno się przyda, zawsze to nieco inne spojrzenie na programowanie ;)

0

Programowania funkcyjnego warto się nauczyć, chociażby dlatego, że nieźle wyrabia myślenie. No i oczywiście uczy jak korzystać z rekurencji co na pewno przydaje się na OI.

0

Ok. Sorry. Pomyliłem programowanie funkcyjne z proceduralnym. Do IO język znać trzeba, choćby po to, żeby algorytmy odpowiednio zaimplementować. I nie mówię tu o znajomości zaawansowanych bibliotek. Tylko tematy objęte standardem.

0

a jaki język do nauki programowania funkcyjnego byście polecili ?
pod wzg. polskiej dokumentacji chyba naj. jest ocaml lecz pod winXP
nie działa mi jak należy.
może lisp albo haskell ale są chyba po polsku słabo opisane :-/

Dzięki za odpowiedzi dodatkowe sugestie mile widziane :]</ort>

0

Najprostszy jest chyba Scheme, ale na czym polega programowanie funkcyjne dobrze widać na Haskellu ponieważ nie ma naleciałości stylu imperatywnego.

0

Haskell jest o wiele lepszym pomysłem - leniwa ewaluacja niesamowicie ułatwia pisanie funkcyjne, lisp/scheme w porównaniu z tym to wręcz męka.

@cepa - matma na oi przydaje się do zadań numerycznych/geometrycznych.. i tyle.
W tym roku można było przejść do 3 etapu znająć DFS i BFS + odrobina wyobraźni (zadanie BBB... banalne, jak już się zna rozwiązanie :|)
Ilość potrzebnej matmy - 0
(oczywiście trzeba umieć oszacować złożoność algorytmu)

0

mam jeszcze pytanie odnośnie książki Cormena "Wprowadzenie do algorytmów":
czy algorytmy zapisane tam w pseudokodzie łatwo przepisać na C++ ?
i czy ogólnie to dobry wybór na początek przygotowań i czy poziom matmy w niej
użyty nie przeszkadza?

(dodam że z c++ znam na razie głównie pętle, tablice czy to za mało ? czy na OI
przydatne jest programowanie obiektowe?) [same 'czy' w moim poście ;-) ]

a macie może jakieś pozycje nt. złożoności obliczeniowej ?

0

Programowanie obiektowe jest w ogóle nie przydatne. Wystarczy znajomość strukturalnego + wykorzystanie STL ale to też niekoniecznie. W Cormenie na początku jest wyłożona wszelka matma wykorzystywana w ksiące więc w razie czego można sobie doczytać.

0

rnd, dzięki.
a mógłby ktoś odpowiedzieć na resztę pytań z mojego wcześniejszego postu ..

1 użytkowników online, w tym zalogowanych: 0, gości: 1