Programowanie - blog

Mój pierwszy SRM ;)

2010-02-20T16:37:00.000+01:00

SRM - single round match, a więc runda stałych zawodów TopCoder. TopCoder jest amerykańską firmą zajmującą się organizacja zawodów programistycznych. W zawodach może wziąć udział praktycznie każdy, wystarczy zarejestrować się na www.topcoder.com i wybrać odpowiednią dla siebie "dyscyplinę". Mnogość konkurencji w jakich można rywalizować, na początku może przyprawić o zawrót głowy, ja jednak trafiłem tam w jedynym konkretnym celu, sprawdzeniu się w konkurencji polegającej na implementacji algorytmów realizujących postawione zadanie. Dlaczego akurat taki wybór? Głównie ze względu na bardzo zróżnicowany poziom zadań. Nie ukrywam, że choć bardzo się staram, moje umiejętności programistyczne nadal są niewielkie, a w konkurencji "Algorithm", każdy znajdzie coś dla siebie. Po odpaleniu appletu Competition Area w dziale Practice ma się do dyspozycji archiwum zadań ze wszystkich meczów, które zostały do tej pory rozegrane. Podczas implementacji rozwiązania z poziomu appletu można sprawdzić działanie programu na przykładach zawartych w opisie zadania. W momencie kiedy uważamy, że algorytm działa poprawnie zgłaszamy swoje rozwiązanie. Liczba przyznanych punktów zależy od tego jak szybko udało nam się wysłać rozwiązanie. Na koniec pozostaje tylko wybrać opcję "System test" aby sprawdzić nasze rozwiązanie na przygotowanym przez organizatorów zestawie testowym. Przed moim pierwszym meczem rozwiązałem tylko około 20 zadań i to zresztą tych najłatwiejszych. Zawody zaczęły się o godzinie 3:00 naszego czasu. Niestety nie mogę ich zaliczyć do udanych, gdyż udało mi się rozwiązać tylko jedno, najłatwiejsze zadanie (najsłabiej punktowane) i to w niezbyt dobrym czasie. Na pewno duży wpływ na wynik miał lekki stres i pora rozgrywki, niemniej jednak jestem bardzo zadowolony z samego faktu, że wziąłem w nich udział. Uważam, że jest to świetny sposób rozwoju swoich umiejętności. Podczas tej rundy popełniłem wiele błędów, jednak równie dużo się nauczyłem. Zdobyłem punkty rankingowe, których ilość plasuje mnie, mniej więcej , w połowie stawki. Aktualnie nadal rozwiązuję zadania z historycznych konkursów i z niecierpliwością czekam na kolejną rundę. W tym miejscu chciałbym ostrzec każdego, kto po przeczytaniu tego tekstu zamierza sprawdzić się w takich zawodach: UWAGA, TO WCIĄGA ;).

Zastosowań wskaźników ciąg dalszy - tablice wielowymiarowe

2010-02-12T13:55:00.004+01:00

W poprzednim poście opisałem sposób dynamicznego przydziału pamięci dla tablicy jednowymiarowej. Przy okazji chciałbym powiedzieć, ze do poprzedniej notki wkradł się błąd dotyczący funkcji calloc, który już poprawiłem. W tej notce również będzie o tablicach, tym razem zajmiemy się jednak tablicami wielowymiarowymi. O ile w przypadku tablicy wielowymiarowej, gdzie znamy jej rozmiar już w trakcie tworzenia programu, nie ma wielkich problemów, to jednak, w momencie kiedy zechcemy przydzielić dla niej pamięć dynamicznie, sprawa nieco się komplikuje. Mam jednak nadzieje, że po przeczytaniu tej notki, wiele się wyjaśni. Na początek zastanówmy się jakie "narzędzia" będą nam potrzebne. Poznane do tej pory "normalne" sposoby tworzenia tablicy oraz wskaźniki niestety nie wystarczą. Tym czego nam potrzeba jest: wskaźnik na wskaźnik. Hmm... zdaje sobie sprawę, że nie brzmi to zbyt zachęcająco, szczególnie, jeżeli nie masz jeszcze dostatecznej wprawy w "żonglowaniu" normalnymi wskaźnikami. Otóż wskaźnik na wskaźnik, jak sama nazwa wskazuje, nie jest normalny wskaźnikiem, którego poznaliśmy do tej pory, i który pokazywał na zmienną. Jest to konstrukcja, która pokazuje na wskaźnik. Tworzenie tablicy dwu-wymiarowej zaczniemy więc od wskaźnika, który będzie pokazywał na jednowymiarową tablicę wskaźników, które to z kolei będą pokazywać na kolejne jednowymiarowe tablice, będące wierszami naszej tablicy dwu-wymiarowej. Aby lepiej to zrozumieć polecam przeanalizować kod:

int wiersze; // tutaj trzeba wczytać ilość wierszy
int kolumny; // tutaj trzeba wczytać ilość kolumn

int **tablica; // tworzymy wskaźnik na wskaźnik

tablica = new int*[wiersze]; // tworzymy tablice wskaźników do wierszy

for(int i = 0; i < wiersze; i++)
{
tablica[i] = new int[kolumny]; // tworzymy kolumny
}

Ja łatwo się domyślić, kasowanie tablicy, również musi przebiegać w nieco odmieniony sposób. Musimy zacząć od kasowania kolumn, a dopiero potem skasować tablicę wskaźników do wierszy. Oto kod:

for(int i = 0; i < wiersze; i++)
{
delete[] tablica[i];
}
delete[] tablica;

Analogicznie postępujemy w przypadku tworzenia tablic o większej liczbie wymiarów. Kody zostały podane w wersjach z wykorzystaniem operatora new. W ramach ćwiczeń polecam samodzielnie przećwiczyć sobie deklarowanie tablic wielowymiarowych z wykorzystaniem malloc, calloc i free.

Ciąg dalszy o dynamicznej alokacj pamięci

2010-02-09T16:16:00.000+01:00

W poprzedniej notce powiedzieliśmy sobie co nieco o funkcjach malloc, calloc oraz free. Jak poprzednio wspomniałem są to funkcje znane z języka C. Nie znaczy to oczywiście, że programiści C++ nie mogą ich używać. Z pewnych względów jednak nie powinni tego robić. Twórcy języka C++ oddają w nasze ręce nowe i lepsze rozwiązanie. Używanie funkcji new i delete ma szczególne znaczenie w przypadku programowania obiektowego, ale o tym jeszcze nie teraz. Zobaczmy jak za pomocą tych funkcji osiągnąć ten sam efekt co poprzednio:

int tablica*;
int rozmiar;
scanf("%d", &rozmiar);
tablica = new int[rozmiar];
...
delete[] tablica;

Jak widać zamiast dość skomplikowanego (przynajmniej na pierwszy rzut oka) wywołania malloc w dodatku z rzutowaniem, mamy tylko jedno słowo kluczowe new. Przy usuwaniu tak utworzonej tablicy trzeba jednak pamiętać aby użyć polecenia delete[] a nie samego delete, które to spowodowało by oddanie do systemu tylko pierwszego elementu (indeksu) tej tablicy. Nieużywanemu wskaźnikowi, podobnie jak w poprzednim przypadku, należy przypisać adres NULL.

Słówko o malloc() calloc() i free()

2010-02-08T10:36:00.000+01:00

W poprzedniej notce opisane zostało wykorzystanie wskaźników i referencji w celu modyfikacji przez funkcję pewnych zmiennych zadeklarowanych wcześniej w programie. Jakkolwiek jest to wiedza bardzo potrzebna, praktyczna i przydatna, nie wyczerpuje jednak możliwości i dziedzin zastosowania "osławionych" wskaźników.
Podczas pisania programu bardzo często wykorzystujemy tablice. Zakładamy, że czytelnik posiada elementarna wiedzę, jak to czym są i do czego one służą. Tablice w programie możemy zadeklarować w bardzo prosty sposób, jeżeli z góry znamy jej rozmiar, np.:

int tablica[10]

W tym wypadku tworzona jest 10 - elementowa tablica zmiennych typu int. Sprawa nieco się komplikuje, w momencie kiedy zależy nam na tym aby rozmiar mógł być zadeklarowany w czasie działania aplikacji, np.: po wprowadzeniu przez użytkownika pewnej liczby. Niestety rozwiązanie przedstawione poniżej nie zadziała:

int rozmiar;
scanf("%d", &rozmiar);
int tablica[rozmiar];

Powodem jest to, iż rozmiar tablicy deklarowanej w ten sposób musi być znany w trakcie kompilacji programu. Nie wnikajmy dlaczego tak się dzieje, gdyż na chwilę obecną z praktycznego punktu widzenia nie jest to aż tak ważne. Pomyślmy lepiej nad rozwiązaniem tej sytuacji. Jako, że miało być coś o wskaźnikach, nie trudno się domyślić, iż to właśnie one są odpowiednim narzędziem, które pozwoli nam rozwiązać ten problem.
To co teraz zrobimy, w przyszłości (nie, wcale nie znaczy to "od jutra", jutro to bardzo pracowity dzień, każdy z nas chyba coś od jutra zaczyna, więc w tym wypadku proponuje zacząć już od teraz) nazywać będziemy dynamiczną alokacją pamięci. Jako, że zdecydowanie wolę objaśniać napisany kod, niż pisać o tym jak go napisać, zacznijmy od kilku linijek programu. Na początek na celownik bierzemy funkcję malloc, znaną z biblioteki języka C.

int* tablica;
int wielkosc;
scanf("%d", &wielkosc);
tablica = (int*)malloc(wielkosc * sizeof(int));
...
free(tablica);
tablica = NULL;

Co my tu mamy... zacznijmy od początku. W pierwszej linijce deklarujemy wskaźnik na zmienną typu int. Druga i trzecia linia, mam nadzieję, nie wymagają wyjaśnień. To co nas najbardziej interesuje, dzieje się w linijce czwartej. Zauważmy, że mamy już wskaźnik na zmienna typu int, ale jak do tej pory nigdzie nie utworzyliśmy zmiennej, na którą mógłby on pokazywać. Czas to zmienić i w tym momencie trzeba sobie powiedzieć kilka słów o funkcji malloc. Jak można się domyślić po tym iż wynik jej działania przypisujemy do naszego wskaźnika, zwraca ona wskaźnik. Nie jest to jednak wskaźnik żadnego konkretnego typu, a konkretnie jest to wskaźnik na void. Niezbędne zatem jest rzutowanie wyniku działania funkcji na wskaźnik interesującego nas typu. Sama funkcja malloc ma za zadanie przydzielić pewien obszar pamięci, którego wielkość określamy jako parametr podczas wywołania funkcji. Zwrócony wskaźnik pokazuje na początek tego obszaru. Jak łatwo się domyślić, w naszym wypadku funkcja przydziela obszar rozmiaru ("wielkosc" * rozmiar zmiennej int) a więc rezerwuje miejsce dla wprowadzonej przez użytkownika ilości zmiennych typu int. Wiedząc, że tablica to nic innego jak ciągły obszar pamięci wielkości wielokrotności rozmiaru pojedynczej zmiennej danego typu, dochodzimy do wniosku, że właśnie utworzyliśmy tablice o zadanym przez użytkownika rozmiarze.
Od tej pory możemy jej używać w identyczny sposób, jak poznane wcześniej tablice. Trzeba jedna pamiętać aby, kiedy tablica nie jest już nam potrzeba, zwolnić przydzieloną jej pamięć. Służy do tego funkcja free, wywołana tak jak w powyższym przykładzie.

Funkcja calloc spełnia podobne zadanie, jednak podczas jej wywołania, przydzielany obszar jest inicjowany zerami. W przypadku funkcji malloc, zawartość obszaru jest nieokreślona, więc jest w nim to, co wcześniej było w tym miejscu pamięci i bynajmniej nie są to zera ;).

Bardzo dobrą, a wręcz wymaganą jest, aby po zwolnieniu pamięci, przypisać wskaźnikowi, który na nią wcześniej wskazywał, wartość NULL. Pomoże to uchronić się przed błędem ochrony pamięci, gdybyśmy przez nieuwagę w dalszej części programu spróbowali odwołać się do tego obszaru pamięci, który przecież już do nas nie należy.

W następnej notce postaram się opisać funkcje new oraz delete.

O funkcjach, wskaźnikach i referencjach słów kilka

2010-02-05T22:01:00.001+01:00

Na początek dość wymuszony post (w końcu wypada coś napisać), ale jakoś w końcu trzeba zacząć. Na pierwszy ogień weźmiemy problem dość banalny... w każdym razie dla każdego kto ma choć niewielkie doświadczenie w programowaniu. Jak sie jednak okazuje dość poważny dla początkujących (w sumie to raczej dla tych bardzo początkujących) programistów. Zaczynajac przygodę z programowaniem w jezyku C, czy też C++, zazwyczaj na początku wszystko wydaje się łatwe i przyjemne. W każdym razie do momentu kiedy przyjdzie się nam spotkać ze wskaźnikami. Zrozumienie działania wskaźników zazwyczaj zabiera trochę czasu, niemniej jednak, jest to bardzo ważny element języka, więc nie tylko powinno się z nim zapoznać, jest to wręcz koniecznością.

Hmm no dobrze, dość już tego gadania... napiszmy troszkę kodu, oto przykładowa funkcja:

double PoleKola(double dPromien)
{
  double dWynik;
  dWynik = 3.14 * dPromien * dPromien;
  return(dWynik);
}

Nie, nie ma tutaj nic, kompletnie nic podchwytliwego. Powyższa funkcja działa poprawnie. Możemy więc użyć ją w programie:

int main()
{
  double dPole;
  double dPromien;

  scnaf("%lf",&dPromien);

  dPole = PoleKola(dPromien);

  printf("Pole kola o promieniu %f wynosi %f.\n", dPromien, dPole);   
}

Funkcja PoleKola zwraca wartość typu double. Aby przypisać tę wartość jakiejś zmiennej musimy użyć konstrukcji zmienna = PoleKola(...). Co jednak zrobić, gdyby okazało się, ze funkcja musi zwracać więcej niż jedną wartość? Załużmy, że chcemy za pomocą jednej funkcji policzyć pole oraz obwód koła. W zaprezentowany powyżej sposób jest to oczywiście niewykonalne. I tutaj przychodzą z pomocą wskaźniki. Zobaczmy więc jak można to zrealizować:

bool PoleKola(double dPromien, double* dPole, double* dObwod)
{
  if( dPromien <= 0.0 )
  {
    return( false );
  }
  *dPole = 3.14 * dPromien * dPromien;
  *dObwod = 6.28 * dPromien;
  return( true );
}

Hmm no tak, teraz wygląda to... troszke inaczej. Zanijmy od wyjaśnienia czym są owe gwiazdki występujące po typie zmiennej. Gwiazdka mówi nam o tym (a raczej za jej pomocą my mówimy to kompilatorowi), że dPole i dObwod nie sa bynajmniej zwyczajnymi zmiennymi. Poprzedzając nazwę zmiennej gwiazdką czynimy z niej zmienna wskaźnikową. Nasza funkcja przyjmuje więc jedną zmienną jako wartość, jest nią dPromien oraz dwa wskaźniki do zmiennych typu double. Fakt iż są to wskaźniki ma tutaj kluczowe znaczenie dla działania funkcji. Zauważmy, że nasza funkcja w żaden sposób nie wypisuje wyniku swojego działania na ekranie. Oczywiście jest to działanie zamierzone. Zadaniem tej funkcji jest modyfikacja zmiennych, które deklarujemy wcześniej w programie. W tym momencie można zadać sobie pytanie... skoro zmienne są deklarowane wcześniej to czemu po prostu zwyczajnie nie przekazać ich do funkcji? Rezultat takiego rozwiązania, dla osoby początkującej może być dość zaskakujący, zresztą aby sie o tym przekonać polecam samodzielnie przetestować taki przypadek. Wróćmy jednak do tematu. W tym wypadku kluczowe znaczenie ma fakt, iż zmienne w C i C++ są przekazywane do funkcji przez wartość. Oznacza to tyle, że w momencie wywołania funkcji tworzone są lokalne kopie zmiennych, które w "normalny" sposób do niej przekazujemy. Co za tym idzie, wszelkie operacje modyfikacji ich wartości odbywają się na tych kopiach a nie na oryginałach zadeklarowanych w programie. W naszym przypadku, nie jest to efekt pożądany. Aby osiągnąć to, czego oczekujemy jestśmy więc zmuszeni użyć wskaźników.Wskaźnik jest tak naprawdę liczbą, konkretnie numerem (adresem) komórki w pamięci, pod którym znajduje się zmienna. Oczywiście wskaźnik sam nie wie na jaką zmienna ma pokazywać, zadanie "powiedzenia" mu o tym spoczywa na nas. Robimy to za pomocą tzw. operatora wyłuskania: &. A konkretnie tak:

double dZmienna;
double* pWskaznik;
pWskaznik = &dZmienna;

Za pomocą operatora wyłuskania uzyskujemy adres zmiennej, na której go użyjemy. W naszym konkretnie przypadku nie musimy jednak tworzyć w programie głównym specjalnych zmiennych wskaźnikowych. Wystarczy, że operator wyłuskania użyjemy w wywołaniu funkcji, przed nazwa zmiennej. Zakładając, że gdzieś w programie mamy zadeklarowane zmienne dPromien, dPole, dObwod, poprawne wywołanie funkcji powinno wygladać tak:

PoleKola(dPromien, &dPole, &dObowd);

Aby w czasie wykonywania funkcji zmodyfikować zmienna dPole a nie wskazanie do niej znowu musimy użyć gwiazdki:

*dObwod = 6.28 * dPromien; // poprawnie
dObwod = 6.28 * dPromien; // blad: zostanie zmodyfikowana wartość wskazania a nie wartość zmiennej!!!

Wartość logiczna zwracaną przez funkcje można użyć, np. tak jak w powyższym przykładzie, do wychwycenia niepożądanego działania użytkownika (podanie zerowego bądź też ujemnego promienia). Na koniec przykładowy program, który czytelnik powinien być w stanie napisać samodzielnie po przeczytaniu tej notki i zrozumiemniu, czym są i do czego, już w początkowej fazie nauki, mogą przydać się wskaźniki.

#include 
#include 

bool PoleKola(double dPromien, double* dPole, double* dObwod);

int main()
{
  double dPromien;
  double dPole;
  double dObwod;
  bool bOK;

  scanf("%lf",&dPromien);
  bOK = PoleKola(dPromien, &dPole, &dObwod);
  if(bOK)
  {
    printf("Promien: %.2f\nPole: %.2f\nObwod: %.2f\n", dPromien, dPole, dObwod);
  }
  else
  {
    printf("Podano nieprawidlowy promien!!!\n");
  }
  system("pause");
  return(0);
}

bool PoleKola(double dPromien, double* dPole, double* dObwod)
{
  if(dPromien <= 0.0)
  {
    return(false);
  }

  *dPole = 3.14 * dPromien * dPromien;
  *dObwod = 6.28 * dPromien;

  return(true);
}