| Nawigacja |
| Strona główna |
| Powrót wyżej |
| Podrozdziały |
| Aktualna edycja |
| Strona główna |
| Aktualny ranking |
| Indywidualne Zawody w Programowaniu |
| Zadania |
| Cele i założenia oraz regulamin |
| Kontakt |
| Kierownik Ligi |
| Webmaster |
| Statystyki |
 |
| Dodatki |
| Wersja do druku |
|
Grzegorz Gembała Kilka uwag o programowaniu w C na Ligę i nie tylko.W celu ułatwienia życia początkującym "ligowcom" napisałem o kilku rzeczach o których nie wiedziałem, gdy zaczynałem pisać programy na Ligę, a których znajomość bardzo ułatwiłaby mi start. Jest też kilka zadań z rozwiązaniami. Jeżeli uważasz, że na tej stronie powinna się znaleźć jakaś informacja napisz do Kierownika Ligi. Powrót Spis treści
Uwagi ogólne czyli jak pisać aby się nie zamęczyćPoniższe dokument dotyczy pisania programów na Ligę i inne konkursy programistyczne. Jedynymi kryteriami oceniania programów na zawodach są: poprawność działania, szybkość i zużycie pamięci. Poprawność działania jest sprawdzana poprzez uruchomienie programu dla pewnych danych testowych i porównaniu wyników z poprawnymi odpowiedziami. Dla każdego zadania jest ustalany limit czasu. Najczęściej jest to czas działania programu wzorcowego dla danych testowych pomnożony przez pewna stałą. Rozmiar pamięci dostępnej dla programu wynosi najczęściej 16 MB. Styl programowania nie jest oceniany. W związku z tym piszemy program jak nam wygodnie, ale czytelnie. Unikamy dynamicznych struktur danych, tam gdzie można stosujemy tablice - programy są kompilowane przy użyciu kompilatorów 32bitowych, więc tablice mogą być większe niż 64kb. Najlepiej pisać krótkie programy - szybko się je pisze i szybko znajduje się w nich błędy. Często lepiej przemyśleć rozwiązanie niż męczyć się z 700 liniowym programem. Dobrym pomysłem jest stosowanie funkcji, można zaoszczędzić czas w przyszłości. We wszystkich zadaniach można przyjąć, że dane wejściowe są poprawne i zgodne ze specyfikacją podaną w treści zadania. W rozwiązaniach nie trzeba sprawdzać poprawności odczytanych danych wejściowych.Początek Kompilatory, edytory, debugery i inne zabawkiJeżeli nie potrzebujemy debugera możemy pisać w Notatniku i kompilować program z linii poleceń. Wtedy nie ma większych problemów z kompilatorem, wystarczy żeby był 32bitowy. W praktyce pisanie w Notatniku jest niewygodne, brak numeracji linii powoduje trudności przy szukaniu błędów. Wygodniej używać jakiegoś edytora z funkcjami programistów (podświetlanie składni, numeracja linii) . Krótka charakterystyka kilku narzędzi:
Początek Kompilacja - kompilator gccProgram kompilujemy poleceniem gcc plik.c. Wykonanie komendy powoduje utworzenie pliku a.exe w systemie Dos lub a.out w systemie Linux. Nazwę pliku wykonywalnego możemy wskazać następująco gcc plik.c -o plik.exe. Dobrze stosować opcje -Wall, powoduje ona wyświetlanie wszystkich ostrzeżeń. Pozwala ona uniknąć prostych błędów: przypisanie zamiast testowania równości, parametr funkcji scanf nie będący wskaźnikiem itp. Osoby korzystające z IDE lub innego kompilatora też mogą włączyć opcje generującą wszystkie ostrzeżenia.Początek Standardowe wejście i wyjścieProgramy na Ligę czytają dane ze standardowego wejścia i wyświetlają wynik na standardowe wyjście. Służą do tego procedury zdefiniowane w pliku nagłówkowym stdio.h. Program powinien czytać dane ze standardowego wejścia tak z pliku. Nie wolno czekać na naciśniecie klawisza. Program wysyła wyniki na standardowe wyjście. Należy wysyłać tylko wyniki, pytania czy chcesz zakończyć działanie programu lub podobne spowodują odesłanie programu z oceną wrong answer, ewentualnie time limit exceeded gdy program będzie czekał na odpowiedź użytkownika. Program nie musi przeczytać wszystkich danych wejściowych przed wypisaniem wyników można przeczytać cześć danych i zacząć wypisywać rozwiązanie. Najczęściej dane testowe są podzielone na zestawy, program czyta zestaw oblicza i wypisuje odpowiedź czyta następny zestaw ... . Standardowe wejście i wyjście są języku C plikami o nazwach: stdio, stdout. Do czytania używamy funkcji getchar scanf ... , a do wyświetlania putchar, puts , printf .... . Aby sprawdzić czy wystąpił koniec danych można używać funkcji feof z parametrem stdin: feof(stdin). Aby ułatwić sobie testowanie dane testowe zapisujemy do pliku. Aby sprawdzić jak działa program dla danych testowych wydajemy komendę plik < dane_testowe.txt . Jeżeli chcemy aby wynik został zapisany do pliku stosujemy polecenie plik < dane_testowe.txt > wynik.txt . Powyższy efekty możemy osiągnąć dopisując następujące linie na początku funkcji main:
freopen("e:\\dane\\dane.txt","rt",stdin);
freopen("e:\\dane\\wynik.txt","wt",stdout);
Oczywiście należy usunąć te linie przed wysłaniem zadania do oceny. W przypadku wątpliwości najlepiej zobaczyć
przykładowe zadania.
Początek Jakich funkcji wolno używaćAby stwierdzić, jakich funkcji można używać należy zapoznać się z regulaminem zawodów. W praktyce zawsze można i wystarczy używać funkcji zdefiniowanych w standardzie ANSI C. W większości help'ów jest napisane, które funkcje należą do standardu ANSI C. Pisząc program zgodny ze standardem ANSI C mamy pewność, że będzie się kompilował na innym kompilatorze. Ponadto na programy są nałożone pewne ograniczenia. W praktyce programowi nie wolno: wykonywać jakichkolwiek operacji na plikach (nie dotyczy standardowego wejścia i wyjścia), używać sieci, tworzyć wątków.Początek Jak łatwo sortować tablice - funkcja qsortDo sortowania tablic w języku C można używać funkcji qsort ze standardowej biblioteki ANSI C. Argumentami funkcji są wskaźnik na tablicę, którą sortujemy, ilość elementów do posortowania, rozmiar elementu tablicy i wskaźnik na funkcje porównującą. Argumentami funkcji porównującej są dwa wskaźniki na elementy tablicy, funkcja zwraca wartość typu int. Zwracana wartość powinna być dodatnia gdy pierwszy element jest większy od drugiego, zero gdy elementy, wartość gdy drugi element jest większy od pierwszego. Funkcja qsort sortuje tablice w porządku rosnącym, aby posortować tablice w porządku malejącym zmieniamy funkcje porównującą. Najlepiej stosować funkcję qsort w następujący sposób:
int tab[1000000],n;
int comp(int *a,int *b)
{
return *a-*b;
}
...
/*Sortowanie n pierwszych elementów tablicy tab w porządku rosnącym*/
qsort(tab,n,sizeof(int),(int(*)(const void *,const void *))comp);
...
Funkcja porównująca jest rzutowana na typ (int(*)(const void *,const void *)), więc kompilator nie sprawdza czy funkcja
porównująca ma prawidłowe argumenty.
Początek Jak szybko zaimplementować stos i kolejkę na tablicyPisząc zadania na Ligę i inne konkursy znamy rozmiar danych wejściowych. Powoduje to, że stosy i kolejki można łatwo zaimplementować na tablicy. Załóżmy że na stos nie zostanie odłożonych więcej niż STACK_SIZE elementów typu int. Operacje na stosie możemy wykonywać w następujący sposób:
int stack[STACK_SIZE+1],*top;
top=stack; /*inicjalizacja*/
*++top=i; /*odłożenie elementu i na stos*/
*++top=i;
x=*top; /*przypisanie zmiennej x wartości elementu z wierzchołka stosu*/
top--; /*zdjecie elementu ze stosu*/
if (top>stack) /*sprawdzenie czy na stosie jest jakis element*/
y=*top--; /*przypisanie zmiennej y wartości elementu z wierzchołka stosu
i zdjęcie elementu ze stosu*/
Podobnie prosto możemy zaimplementować kolejkę. Zakładamy, że do kolejki zostanie włożone najwyżej QUEUE_SIZE elementów.
int queue[QUEUE_SIZE],*front,*back; front=back=queue; /*inicjalizacja*/ *back++=i; /*włożenie elementu do kolejki*/ *back++=i; x=*front; /*odczytanie elementu z początku kolejki*/ front++; /*usunięcie elementu z kolejki*/ if (front<Praktyczne zastosowanie kolejki na tablicy można zobaczyć w zadaniu 2 (patrz punk Przykładowe zadania). Początek TablicowanieW niektórych zadaniach dobrze stablicować pewne dane. W skrajnym przypadku można stablicować odpowiedzi dla wszystkich możliwych danych wejściowych, ale zdarza się to rzadko. Należy pamiętać, że w większości konkursów rozmiar pliku z kodem źródłowym jest ograniczony. Wartości pewnych tablic możemy obliczyć na początku programu (przykładowo współczynniki Newtona, początkowe liczby pierwsze).Początek Trzy słowa o popularnych błędachWiele błędów może zostać wykrytych przez kompilator. W tym celu należy włączyć wszystkie opcje generowania ostrzeżeń (warning). W GCC/DJGPP kompilujemy program z opcja -Wall. Zdarzają się błędy związane z przepełnieniem stosu. Tablice o dużym rozmiarze należy deklarować globalnie, jeżeli je zadeklarujemy w funkcji main to zostaną utworzone na stosie. W skrajnym przypadku program się nie uruchomi. Nie należy przesadzać z głębokością przy rekurencji, tu też stos może się przepełnić. W niektórych konkursach wymagane jest by program zwrócił wartość zero do systemu wiec piszemy tak:
int main()
{
....
return 0;
}
W przypadku braku return 0 można otrzymać ocenę runtime error.Pisząc w języku C lepiej nie stosować komentarzy typu C++ : //. Wysyłając program z takimi komentarzami można otrzymać ocenę Compile Error. Sprawdź czy wyniki obliczeń nie są za duże dla stosowanego przez Ciebie typu danych. Do wykrywania błędów możesz stosować standardowe makro assert. Początek Przykładowe zadania z rozwiązaniamiZamieszczam rozwiązania kilku zadań ligowych.
Początek |