Informatyka w roku szkolnym 2008/09 w semestrze zimowym w klasie matematycznej 1A

Celem tych zajęć jest nauczenie Was wykorzystania komputera do efektywnego rozwiązywania zadań obliczeniowych. Na lekcjach będą omawiane zarówno metody rozwiązywania zadań (algorytmika) jak i narzędzia (język C++ i biblioteka STL dla C++).

Informacje organizacyjne

Terminarz:
  • termin: środa 7:30-9:00 s.214
  • nauczyciel: Paweł Rzechonek
Pomoce dydaktyczne:

Zasady oceniania

Zasady zaliczenia przedmiotu opierają się na systemie punktowym. Punkty można uzyskiwać za:

  • sprawdziany
  • aktywność na zajęciach
  • rozwiązywanie zadań domowych
  • udział w zawodach programistycznych
Surowo będą karane prace niesamodzielne i wszelkie inne oszustwa (do usunięcia z grupy włącznie). Nie należy przez to rozumieć, że zabraniam współpracy, wręcz przeciwnie. Róbcie zadania wspólnie, a więcej i szybciej się nauczycie. Jednak nim rozwiązanie zadania wyślecie, musicie umieć to zadanie samodzielnie rozwiązać (będzie to weryfikowane).

Notatki z lekcji

Spis tematów:

  1. klasy
  2. pliki
  3. grafy
  4. kolekcja vector z STL
  5. grafy skierowane
  6. ścieżki i cykle
  7. drzewa rozpinające
  8. kolejki priorytetowe
  9. grafy ważone
  10. przejście przez szachownicę / pełny przegląd zbioru rozwiązań
  11. kolorowanie grafów / algorytmy z powrotami
  12. problem komiwojażera / metoda podziału i ograniczeń
  13. problem plecakowy / metoda podziału i ograniczeń
  14. dziel i zwyciężaj
  15. programowanie dynamiczne (1)
  16. programowanie dynamiczne (2)
  17. wyszukiwanie wzorca w tekście
  18. automaty skończone
  19. zastosowanie automatów do wyszukiwania wzorców
4.02.2009: klasy
Zagadnienia omawiane na lekcji
  • Operatory new (przydział pamięci) i delete (zwolnienie pamięci).
  • Pojęcie klasy (nowy typ) i obiektu (instancja klasy w pamięci).
  • Definicja klasy i składowych w klasie.
  • Definicja metod poza klasą.
  • Konstruktory i destruktor.
  • Dynamiczne struktury danych - lista jednokierunkowa.
Zadanie

Zdefiniuj listę jednokierunkową z operacjami dodawania i usuwania elementów na jej początku i końcu.

11.02.2009: pliki
Zagadnienia omawiane na lekcji
  • Pojęcie strumienia.
  • Plik jako strumień danych.
  • Otwieranie i zamykanie pliku..
  • Czytanie z pliku danych tekstowych.
  • Zapis do pliku danych tekstowych.
  • Sprawdzanie stanu pliku.
Zadanie

Z pliku a.txt odczytaj liczby i zapisz je w odwrotnej kolejności do pliku b.txt. Wykorzystaj do tego celu listę jednokierunkową zaprogramowaną na poprzedniej lekcji.

18.02.2009: grafy
Sprawdzian

Odczytaj wszystkie liczby całkowite zapisane w pliku a.txt i do pliku b.txt zapisz ich kwadraty.

Wskazówka! Do czytania z pliku wykorzystaj obiekt ifstream a do pisania ofstream.

Zagadnienia omawiane na lekcji
  • Pojęcie grafu.
  • Macierzowa reprezentacja grafu.
  • Listowa reprezentacja grafu.
  • Złożoność podstawowych operacji na grafach w zależności od reprezentacji.
  • Przeglądanie grafu w głąb.
  • Problem istnienia ścieżki łączącej dwa wierzchołki w grafie.
25.02.2009: kolekcja vector z STL
Sprawdzian

Wczytaj liczbę k∈{1,2,...20} i wypisz najmniejszą liczbę naturalną podzielną przez liczby 1,2,...k. Na przykład liczba 2520 jest najmniejszą liczba podzielną przez 1,2,...10.

Wskazówka! Rozważ wszystkie liczby z przedziału {1,2,...20}, które są potęgami jakiejś liczby pierwszej.

Zagadnienia omawiane na lekcji
  • Klasa sparametryzowana vector.
  • Reprezentacja grafu z wykorzystaniem wektorów.
  • Przeglądanie grafu wszerz.
  • Problem najkrótszej ścieżki łączącej dwa wierzchołki w grafie.
4.03.2009: grafy skierowane
Sprawdzian

W pliku tekstowym graf.txt zapisany jest graf G=(V,E) oraz wierzchołek startowy s. Wypisz na standardowym wyjściu najbardziej odległy wierzchołek (w sensie najkrótszych ścieżek) od wierzchołka s.

Wskazówka! Zastosuj przeglądanie grafu wszerz.

Zagadnienia omawiane na lekcji
  • Powtórzenie materiału dotyczącego grafów.
  • Grafy skierowane.
11.03.2009: ścieżki i cykle
Sprawdzian

W pliku tekstowym graf.txt zapisany jest graf skierowany D=(V,E), wierzchołek startowy s i liczba naturalna k. Wylicz i wypisz na standardowym wyjściu ile ten graf zawiera wierzchołków odległych od wierzchołka s o co najwyżej k krawędzi.

Wskazówka! Zastosuj przeglądanie grafu w głąb z ograniczeniem rekurencji.

Zagadnienia omawiane na lekcji
  • Ścieżki w grafie (ścieżki proste).
  • Cyke w grafie (cykle proste).
  • Cykl Eulera.
  • Cykl Hamiltona.
18.03.2009: drzewa rozpinające
Sprawdzian

W pliku tekstowym graf.txt zapisany jest graf G=(V,E). Wyznacz dla tego grafu drzewo rozpinające.

Wskazówka! Zastosuj zmodyfikowaną procedurę przeglądania grafu w głąb.

Zagadnienia omawiane na lekcji
  • Grafy, które są drzewami.
  • Drzewo rozpinające w grafie.
25.03.2009: kolejki priorytetowe
Zagadnienia omawiane na lekcji
  • Kolejka priorytetowa.
  • Realizacja kolejki w STL jako priority_queue<>.
Projekt

Dane są dwie 4-cyfrowe (w zapisie dziesiętnym) liczby pierwsze p i q. Należy znaleźć najkrótszy ciąg liczb, zaczynający się od p i kończący się na q, który składa sie z 4-cyfrowych liczb pierwszych i każde dwie sąsiednie liczby w tym ciągu różnią się tylko jedną cyfrą.

Przykład. Dla liczb p=2011 i q=4409, najkrótszy ciąg liczbowy, który łączy te liczby to (2011, 3011, 3019, 1019, 1009, 1409, 4409).

Wskazówka! Stwórz graf połączeń pomiędzy 4-cyfrowymi liczbami pierwszymi różniącymi się tylko jedną cyfrą. Zastosuj zmodyfikowaną procedurę przeglądania tego grafu wszerz.

1.04.2009: grafy ważone
Zagadnienia omawiane na lekcji
  • Grafy ważone (z wagami na krawędziach).
  • Najkrótsza droga w grafie ważonym (algorytm Dijkstry).
  • Para wartości pair<>.
Projekt

Dany jest graf ważony G=(V,E,w), gdzie w to wagi krawędzi (dodatnie liczby całkowite), oraz wierzchołek startowy s i końcowy f. Napisz program, który znajduje długość najkrótszej ścieżki z s do f.

Wskazówka! Zaimplementuj algorytm Dijkstry z relaksacją.

8.04.2009: przejście przez szachownicę / pełny przegląd zbioru rozwiązań
Zadanie

Dana jest szachownica o wymiarach w×k, gdzie w,k∈{4,...,10}. Należy obejść skoczkiem całą szachownicę odwiedzając każde pole dokładnie raz. Wypisz w⋅k współrzędnych kolejno odwiedzanych przez skoczka pól na szachownicy, albo parę liczb -1 -1 gdy zadanie nie ma rozwiązania.

Wskazówka! Znajdź ścieżkę Hamiltona w grafie połączeń między polami na szachownicy.

Zagadnienia omawiane na lekcji
  • Problem skoczka na szachownicy.
  • Algorytmy naiwne - badają wszystkie możliwe rozwiązania aż do znalezienia rozwiązania optymalnego.
  • Kolorowanie grafów.
15.04.2009: kolorowanie grafów / algorytmy z powrotami
Zagadnienia omawiane na lekcji
  • Kolorowanie grafów.
  • Algorytmy z powotami.
Projekt

Dany jest graf G=(V,E). Napisz program, który znajdzie minimalne pokolorowanie wierzchołków tego grafu.

Wskazówka! Zmodyfikuj przeszukiwanie grafu w głąb i zastosuj metodę z nawrotami.

22.04.2009: problem komiwojażera / metoda podziału i ograniczeń
Zagadnienia omawiane na lekcji
  • Problem komiwojażera.
  • Metoda podziału i ograniczeń.
  • Definiowanie własnych operatorów porównujących.
Projekt

Dany jest graf pełny ważony G=(V,E,w), gdzie w to wagi krawędzi (dodatnie liczby całkowite). Napisz program, który znajduje długość najkrótszej drogi komiwojażera (cykl Hamiltona o najmniejszej wadze) w tym grafie.

Wskazówka! Zastosuj metodę podziału i ograniczeń.

29.04.2009: problem plecakowy / metoda podziału i ograniczeń
Zagadnienia omawiane na lekcji
  • Problem plecakowy.
  • Metoda podziału i ograniczeń.
Projekt

Dany jest plecak o wytrzymałości W<0 oraz zbiór n przedmiotów x0, x1, ...,xn-1, przy czym dla każdego przedmiotu jest określona jego waga wi i wartość pi dla i=0...n-1. Napisz program, który wyznaczy taki podzbiór tych przedmiotów, aby ich sumaryczna wartość była maksymalna przy sumarycznej wadze nieprzekraczającej wytrzymałości plecaka.

Wskazówka! Zastosuj metodę podziału i ograniczeń.

6.05.2009: dziel i zwyciężaj
Zagadnienia omawiane na lekcji
  • Omówienie techniki "dziel i zwyciężaj".
  • Wyszukiwanie binarne.
  • Sortowanie przez scalanie.
  • Sortowanie przez wybór (szybkie).
  • Mnożenie długich liczb.
  • Maksymalny podciąg spójny.
Zadanie

Dany jest ciąg n>1 liczb całkowitych x0, x1, ..., xn-1. Znajdź w tym ciągu taki podciąg spójny xi, xi+1, ..., xj (dla 0≤i≤j<n), w którym suma jego elementów jest maksymalna.

13.05.2009: programowanie dynamiczne (1)
Zagadnienia omawiane na lekcji
  • Omówienie techniki programowania dynamicznego.
  • Liczby Fibonacciego.
  • Dwumian Newtona.
  • Stokrotki.
  • Najdłuższy wspólny podciąg.
  • Triangulacja wielokątawypukłego.
Zadanie

Dany jest zbiór n>3 punktów p0, p1, ..., pn-1, tworzących na płaszczyźnie wielokąt wypukły. Podziel ten wielokąt na trójkąty w taki sposób, aby suma długości przekątnych (tych które dzielą wielokąt na trójkąty) była minimalna.

20.05.2009: programowanie dynamiczne (2)
Sprawdzian

Dane są dwa ciągi A = (a1,a2,...,am) i B = (b1,b2,...,bn) o długościach odpowiednio m i n. Znajdź długość najdłuższego wspólnego podciągu dla A i B oraz wypisz jeden z nich.

Zagadnienia omawiane na lekcji
  • Najdłuższy wspólny podciąg.
  • Najdłuższy podciąg rosnący.
Zadanie

Dany jest ciąg n>1 liczb całkowitych a0, a1, ..., an-1. Znajdź w tym ciągu najdłuższy podciąg rosnący.

27.05.2009: wyszukiwanie wzorca w tekście
Zagadnienia omawiane na lekcji
  • Problem wyszukiwania wzorca w tekście.
  • Algorytm naiwny wyszukiwania wzorca i jego analiza.
  • Algorytm Karpa-Rabina wyszukiwania wzorca.
Zadanie

Zaimplementuj algorytm Karpa-Rabina.

3.06.2009: automaty skończone
Zagadnienia omawiane na lekcji
  • Pojęcie automatu skończonego.
  • Przykłady automatów skończonych.
  • Implementacja automatów skończonych.
  • Strumienie napisowe.
Zadanie

Zaimplementuj automat skończony, który będzie rozpoznawał prawidłowo zapisane (jak w języku C++) liczby rzeczywiste.

10.06.2009: zastosowanie automatów do wyszukiwania wzorców
Zagadnienia omawiane na lekcji
  • Prefiksy i sufiksy.
  • Algorytm wyszukiwania wzorca korzystający z automatu skończonego.
  • Algorytm Knutha-Morrisa-Pratta wyszukiwania wzorca.
Zadanie

Zaimplementuj algorytm Knutha-Morrisa-Pratta.

Zadania domowe

Spis zadań domowych:

  1. podział pliku względem 0
  2. ścieżka w grafie
  3. najkrótsza ścieżka w grafie
  4. drogi powrotne w grafie skierowanym
  5. cykl Eulera w grafie
  6. cykl Hamiltona w grafie gęstym
  7. ciągi liczb pierwszych (projekt)
  8. najkrótsza ścieżka w grafie ważonym (projekt)
  9. kolorowanie grafu (projekt)
  10. problem komiwojażera (projekt)
  11. problem plecakowy (projekt)
  12. maksymalny podciąg spójny
  13. minimalna triangulacja wielokąta wypukłego
  14. najdłuższy podciąg rosnący
Zadanie 1
Zadanie (podział pliku względem 0)
W pliku tekstowym zapisanych jest n>0 liczb całkowitych a0, a1, ..., an-1 (początkowo nie wiemy jaką wartość ma n). Liczby z tego pliku należy podzielić na dwie grupy: mniejsze od 0 oraz większe bądź równe 0. Zapisz je w tym samym pliku, z którego przeczytałeś dane w taki sposób, żeby liczby mniejsze od 0 były zapisane przed liczbami większymi bądź równymi 0. Nie zmieniaj względnej kolejności liczb w obu grupach w stosunku do kolejności pierwotnej.
Wskazówki
  1. Zakładamy, że nazwa pliku z liczbami to liczby.txt.
  2. Wykorzystaj listy, które były omawiane na lekcji.
Rozwiązanie
Rozwiązanie zadania należy przesłać do mnie mailem. W treści listu należy powinny się znaleźć następujące informacje:
  1. imię i nazwisko;
  2. program w języku C++, który dokonuje opisanego przekształcenia danych w pliku.
Wysyłając list wpisz w tytule 14 LO - zadanie 1.
Punkty
Za rozwiązanie tego zadania można otrzymać do 5 punktów.
Termin
Termin nadsyłania rozwiązań upływa w poniedziałek 16 lutego 2009 r. o godzinie 23:59.
Zadanie 2
Zadanie (ścieżka w grafie)
W pliku tekstowym graf.txt zapisany jest graf G=(V,E) oraz dwa wybrane wierzchołki u i v. Sprwadź, czy w tym grafie istnieje ścieżka łącząca te wierzchołki.
Dane
Dane zapisane w pliku mają następujący format. Najpierw zapisane są dwie liczby: n = |V| i m = |E|, przy czym n≤1000. Następnie zapisanych jest m krawędzi w postaci par liczb (każda para oznacza wierzchołki połączone krawędzią w grafie). Na końcu zapisane są numery dwóch wierzchołków, o które pytamy w zadaniu, czy są połącznone jakąś ścieżką.
Wyniki
Rozwiązanie należy wypisać na standardowym wyjściu. Jeśli istnieje ścieżka łącząca wierzchołki u i v to wypisz 1 (albo słowo TAK), a w przeciwnym przypadku wypisz 0 (albo słowo NIE).
Wskazówki
  1. Wykorzystaj macierzową reprezentację grafu.
  2. Napisz osobną funkcję przeglądającą graf w głąb.
Rozwiązanie
Rozwiązanie zadania należy przesłać do mnie mailem. W treści listu należy powinny się znaleźć następujące informacje:
  1. imię i nazwisko;
  2. program w języku C++, który rozwiązuje opisane zadanie.
Wysyłając list wpisz w tytule 14 LO - zadanie 2.
Punkty
Za rozwiązanie tego zadania można otrzymać do 7 punktów.
Termin
Termin nadsyłania rozwiązań upływa w poniedziałek 23 lutego 2009 r. o godzinie 23:59.
Zadanie 3
Zadanie (najkrótsza ścieżka w grafie)
W pliku tekstowym graf.txt zapisany jest graf G=(V,E) oraz dwa wybrane wierzchołki u i v. Oblicz, jaka jest długość najkrótszej ścieżki w grafie łączącej te wierzchołki. W wersji rozszerzonej tego zadania dodatkowo wypisz tą ścieżkę, zaczynając od wierzchołka u i kończąc na v.
Dane
Dane zapisane w pliku mają następujący format. Najpierw zapisane są dwie liczby: n = |V| i m = |E|, przy czym n≤1000. Następnie zapisanych jest m krawędzi w postaci par liczb (każda para oznacza wierzchołki połączone krawędzią w grafie). Na końcu zapisane są numery dwóch wierzchołków, o które pytamy w zadaniu, jak długą ścieżką są połącznone.
Wyniki
Rozwiązanie należy wypisać na standardowym wyjściu. Jeśli istnieje ścieżka łącząca wierzchołki u i v to wypisz długość tej ścieżki, a w przeciwnym przypadku wypisz -1. W wersji rozszerzonej tego zadania dodatkowo wypisz tą ścieżkę, jeśli taka istnieje.
Wskazówki
  1. Wykorzystaj listową reprezentację grafu wykorzystując klasę vector.
  2. Napisz osobną funkcję przeglądającą graf wszerz.
Rozwiązanie
Rozwiązanie zadania należy przesłać do mnie mailem. W treści listu należy powinny się znaleźć następujące informacje:
  1. imię i nazwisko;
  2. program w języku C++, który rozwiązuje opisane zadanie.
Wysyłając list wpisz w tytule 14 LO - zadanie 3.
Punkty
Za rozwiązanie tego zadania można otrzymać do 7 punktów, a w wersji rozszerzonej do 11 punktów.
Termin
Termin nadsyłania rozwiązań upływa w poniedziałek 2 marca 2009 r. o godzinie 23:59.
Zadanie 4
Zadanie (drogi powrotne w grafie skierowanym)
W pliku tekstowym graf.txt zapisany jest graf skierowany D=(V,E) oraz wierzchołek startowy s. Wyznacz wszystkie wierzchołki w tym grafie, do których można dojść z wierzchołka startowego i z których istnieje droga powrotna do s.
Dane
Dane zapisane w pliku mają następujący format. Najpierw zapisane są dwie liczby: n = |V| i m = |E|, przy czym n≤1000. Następnie zapisanych jest m krawędzi w postaci par liczb (każda para oznacza wierzchołki połączone krawędzią w grafie). Na końcu zapisany jest numer wierzchołka startowego s.
Wyniki
Rozwiązanie należy wypisać na standardowym wyjściu. Wypisz wszystkie wierzchołki v, dla których istnieje ścieżka z s do v i ścieżka z v do s. Wierzchołki należy wypisać w sposób uporządkowany (od najmniejszego do największego) razem z wierchołkiem s.
Wskazówki
  1. Wykorzystaj listową reprezentację grafu wykorzystując klasę vector.
  2. Napisz osobną funkcję przeglądającą graf w głąb.
Rozwiązanie
Rozwiązanie zadania należy przesłać do mnie mailem. W treści listu należy powinny się znaleźć następujące informacje:
  1. imię i nazwisko;
  2. program w języku C++, który rozwiązuje opisane zadanie.
Wysyłając list wpisz w tytule 14 LO - zadanie 4.
Punkty
Za rozwiązanie tego zadania można otrzymać do 7 punktów.
Termin
Termin nadsyłania rozwiązań upływa w poniedziałek 9 marca 2009 r. o godzinie 23:59.
Zadanie 5
Zadanie (cykl Eulera w grafie)
W pliku tekstowym graf.txt zapisany jest graf G=(V,E). Sprawdź, czy w tym grafie istnieje cykl Eulera. W wersji rozszerzonej tego zadania dodatkowo wypisz ten cykl.
Dane
Dane zapisane w pliku mają następujący format. Najpierw zapisane są dwie liczby: n = |V| i m = |E|, przy czym n≤1000. Następnie zapisanych jest m krawędzi w postaci par liczb (każda para oznacza wierzchołki połączone krawędzią w grafie).
Wyniki
Rozwiązanie należy wypisać na standardowym wyjściu. Jeśli istnieje cykl Eulera w zadanym grafie to wypisz długość tego cyklu (czyli wartość m), a w przeciwnym przypadku wypisz -1. W wersji rozszerzonej tego zadania dodatkowo wypisz cykl Eulera, jeśli taki istnieje (zacznij od wierzchołka 0 i skończ na tym wierzchołku).
Wskazówki
  1. Wykorzystaj listową reprezentację grafu wykorzystując klasę vector.
  2. Napisz osobną funkcję szukającą cyklu w grafie.
Rozwiązanie
Rozwiązanie zadania należy przesłać do mnie mailem. W treści listu należy powinny się znaleźć następujące informacje:
  1. imię i nazwisko;
  2. program w języku C++, który rozwiązuje opisane zadanie.
Wysyłając list wpisz w tytule 14 LO - zadanie 5.
Punkty
Za rozwiązanie tego zadania można otrzymać do 5 punktów, a w wersji rozszerzonej do 11 punktów.
Termin
Termin nadsyłania rozwiązań upływa w poniedziałek 16 marca 2009 r. o godzinie 23:59.
Zadanie 6
Zadanie (cykl Hamiltona w grafie gęstym)
W pliku tekstowym graf.txt zapisany jest graf G=(V,E). W grafie tym stopień każdego wierzchołka jest ≥n/2, przy czym n=|V|. Wymyśl i zaprogramuj algorytm wyznaczający dla takiego grafu cykl Hamiltona.
Dane
Dane zapisane w pliku mają następujący format. Najpierw zapisane są dwie liczby: n = |V| i m = |E|, przy czym n≤1000. Następnie zapisanych jest m krawędzi w postaci par liczb (każda para oznacza wierzchołki połączone krawędzią w grafie).
Wyniki
Rozwiązanie należy wypisać na standardowym wyjściu. Cykl Hamiltona wypisz zaczynając od wierzchołka 0 i kończąc na tym wierzchołku.
Wskazówka
  1. Wykorzystaj tablicową reprezentację grafu wykorzystując klasę vector.
Rozwiązanie
Rozwiązanie zadania należy przesłać do mnie mailem. W treści listu należy powinny się znaleźć następujące informacje:
  1. imię i nazwisko;
  2. program w języku C++, który rozwiązuje opisane zadanie.
Wysyłając list wpisz w tytule 14 LO - zadanie 6.
Punkty
Za rozwiązanie tego zadania można otrzymać do 11 punktów.
Termin
Termin nadsyłania rozwiązań upływa w poniedziałek 23 marca 2009 r. o godzinie 23:59.
Zadanie 7
Zadanie (ciągi liczb pierwszych)
Dane są dwie 4-cyfrowe (w zapisie dziesiętnym) liczby pierwsze p i q. Należy znaleźć najkrótszy ciąg liczb, zaczynający się od p i kończący się na q, który składa sie z 4-cyfrowych liczb pierwszych i każde dwie sąsiednie liczby w tym ciągu różnią się tylko jedną cyfrą.
Dane
Dane to dwie liczby pierwsze zapisane p i q, takie że 1000<p,q<9999.
Wyniki
Rozwiązanie należy wypisać na standardowym wyjściu. Ma to być ciąg 4-cyfrowych (w zapisie dziesiętnym) liczb pierwszych, zaczynający się od p i kończący się na q, takich że każde dwie sąsiednie liczby w tym ciągu różnią się tylko jedną cyfrą.
Przykład
Dla liczb p=2011 i q=4409 najkrótszy ciąg 4-cyfrowych liczb pierwszych, który łączy te liczby według wyżej opisanej reguły to:
2011 3011 3019 1019 1009 1409 4409
Wskazówki
  1. Wykorzystaj listową reprezentację grafu wykorzystując klasę vector.
  2. Stwórz graf połączeń pomiędzy 4-cyfrowymi liczbami pierwszymi różniącymi się tylko jedną cyfrą.
  3. Zastosuj zmodyfikowaną procedurę przeglądania tego grafu wszerz.
Rozwiązanie
Rozwiązanie zadania należy przesłać do mnie mailem. W treści listu należy powinny się znaleźć następujące informacje:
  1. imię i nazwisko;
  2. program w języku C++, który rozwiązuje opisane zadanie.
Wysyłając list wpisz w tytule 14 LO - zadanie 7.
Punkty
Za rozwiązanie tego zadania można otrzymać do 7 punktów.
Termin
Termin nadsyłania rozwiązań upływa w poniedziałek 30 marca 2009 r. o godzinie 23:59.
Zadanie 8
Zadanie (najkrótsza ścieżka w grafie ważonym)
Dany jest graf zażony G=(V,E,w), gdzie w to wagi krawędzi (dodatnie liczby całkowite), oraz wierzchołek startowy s i końcowy f. Zaprogramuj algorytm Dijkstry znajdujący długość najkrótszej ścieżki z s do f. W wersji rozszerzonej tego zadania dodatkowo wypisz tą ścieżkę, zaczynając od wierzchołka s i kończąc na f.
Dane
Dane zapisane są w pliku tekstowym graf.txt i mają następujący format. Najpierw zapisane są dwie liczby: n = |V| i m = |E|, przy czym n≤1000. Następnie zapisanych jest m krawędzi w postaci trójek liczb (każda trójka oznacza parę wierzchołków połączonych krawędzią w grafie i wagę przypisaną tej krawędzi). Na końcu umieszczone są jeszcze numery dwóch wierzchołków: początkowego s i końcowego f.
Wyniki
Rozwiązanie należy wypisać na standardowym wyjściu. Ma to być długość najkrótszej ścieżki łączącej s i f. W wersji rozszerzonej tego zadania dodatkowo wypisz tą ścieżkę.
Rozwiązanie
Rozwiązanie zadania należy przesłać do mnie mailem. W treści listu należy powinny się znaleźć następujące informacje:
  1. imię i nazwisko;
  2. program w języku C++, który rozwiązuje opisane zadanie.
Wysyłając list wpisz w tytule 14 LO - zadanie 8.
Punkty
Za rozwiązanie tego zadania można otrzymać do 7 punktów, a w wersji rozszerzonej do 11 punktów.
Termin
Termin nadsyłania rozwiązań upływa w poniedziałek 6 kwietnia 2009 r. o godzinie 23:59.
Zadanie 9
Zadanie (kolorowanie grafu)
Dany jest graf G=(V,E). Napisz program, który znajdzie minimalne pokolorowanie wierzchołków tego grafu.
Dane
Dane zapisane są w pliku tekstowym graf.txt i mają następujący format. Najpierw zapisane są dwie liczby: n = |V| i m = |E|, przy czym n≤1000. Następnie zapisanych jest m krawędzi w postaci par liczb (każda para oznacza wierzchołki połączone krawędzią w grafie).
Wyniki
Rozwiązanie należy wypisać na standardowym wyjściu. W pierwszej linii wypisz liczbę użytych kolorów. W następnych n liniach wypisz kolory przypisane kolejnym wierzchołkom - jeśli użyłeś k kolorow, to wierzchołki mają mieć kolory z zakresu 0...k-1.
Wskazówki
  1. Wykorzystaj listową reprezentację grafu.
  2. Zastosuj metodę z nawrotami.
Rozwiązanie
Rozwiązanie zadania należy przesłać do mnie mailem. W treści listu należy powinny się znaleźć następujące informacje:
  1. imię i nazwisko;
  2. program w języku C++, który rozwiązuje opisane zadanie.
Wysyłając list wpisz w tytule 14 LO - zadanie 9.
Punkty
Za rozwiązanie tego zadania można otrzymać do 7 punktów.
Termin
Termin nadsyłania rozwiązań upływa w poniedziałek 20 kwietnia 2009 r. o godzinie 23:59.
Zadanie 10
Zadanie (problem komiwojażera)
Dany jest graf pełny ważony G=(V,E,w) z dodatnimi wagami na krawędziach. Napisz program, który znajdzie trasę komiwojażera w tym grafie (cykl Hamiltona) o minimalnej wadze.
Dane
Dane zapisane są w pliku tekstowym graf.txt i mają następujący format. Najpierw zapisana jest liczba n = |V|, przy czym n≤100. Następnie zapisanych jest n wierszy z n wagami na krawędziach (ważona macierz sąsiedztwa), przy czym wszystkie wagi są liczbami naturalnymi <1000 a na głównej przekątnej są zera.
Wyniki
Rozwiązanie należy wypisać na standardowym wyjściu. W pierwszej linii wypisz koszt minimalnej trasy komiwojażera. W drugiej linii wypisz n kolejno odwiedzanych przez komiwojażera wierzchołków na jego minimalnej trasie (numery wierzchołków pooddzielaj spacjami) zaczynając od wierzchołka o numerze 0.
Wskazówki
  1. Wykorzystaj macierzową reprezentację grafu.
  2. Zastosuj metodę podziału i ograniczeń.
Rozwiązanie
Rozwiązanie zadania należy przesłać do mnie mailem. W treści listu należy powinny się znaleźć następujące informacje:
  1. imię i nazwisko;
  2. program w języku C++, który rozwiązuje opisane zadanie.
Wysyłając list wpisz w tytule 14 LO - zadanie 10.
Punkty
Za rozwiązanie tego zadania można otrzymać do 13 punktów.
Termin
Termin nadsyłania rozwiązań upływa w poniedziałek 27 kwietnia 2009 r. o godzinie 23:59.
Zadanie 11
Zadanie (problem plecakowy)
Dany jest plecak o wytrzymałości W<0 oraz zbiór n przedmiotów x0, x1, ...,xn-1, przy czym dla każdego przedmiotu jest określona jego waga wi i wartość pi dla i=0...n-1. Napisz program, który wyznaczy taki podzbiór tych przedmiotów, aby ich sumaryczna wartość była maksymalna przy sumarycznej wadze nieprzekraczającej wytrzymałości plecaka.
Dane
Dane zapisane są w pliku tekstowym przedmioty.txt i mają następujący format. Najpierw zapisana jest wytrzymałość plecaka W>0. W kolejnej linii zapisana jest liczba przedmiotów n≤1000. Następnie zapisanych jest n wierszy opisujących parametry kolejnych przedmiotów - w każdym wierszu zapisana jest para liczb, gdzie pierwsza liczba jest wartością a druga wagą przedmiotu.
Wyniki
Rozwiązanie należy wypisać na standardowym wyjściu. W pierwszej linii wypisz maksymalną wartość zapakowanego plecaka, w drugiej linii wypisz ciężar optymalnego upakowania a w trzeciej wypisz kolejno numery zapakowanych do plecaka przedmiotów (numery przedmiotów pooddzielaj spacjami).
Wskazówka
  1. Zastosuj metodę podziału i ograniczeń.
Rozwiązanie
Rozwiązanie zadania należy przesłać do mnie mailem. W treści listu należy powinny się znaleźć następujące informacje:
  1. imię i nazwisko;
  2. program w języku C++, który rozwiązuje opisane zadanie.
Wysyłając list wpisz w tytule 14 LO - zadanie 11.
Punkty
Za rozwiązanie tego zadania można otrzymać do 13 punktów.
Termin
Termin nadsyłania rozwiązań upływa w poniedziałek 4 maja 2009 r. o godzinie 23:59.
Zadanie 12
Zadanie (maksymalny podciąg spójny)
Dany jest ciąg n>1 liczb całkowitych x0, x1, ..., xn-1. Napisz program, który znajdzie w tym ciągu taki podciąg spójny xi, xi+1, ..., xj (dla 0≤i≤j<n), w którym suma jego elementów jest maksymalna.
Dane
Dane do programu należy odczytać ze standardowego wejścia. Mają one następujący format. W pierwszej linii podana będzie długość ciągu n, przy czym 1<n≤1000. W drugiej linii podanych będzie n liczb całkowitych pooddzielanych od siebie spacjami.
Wyniki
Rozwiązanie należy wypisać na standardowym wyjściu. W pierwszej linii wypisz maksymalną wartość znalezionego poddciągu, a w drugiej i trzeciej linii wypisz odpowiednio pierwszy i ostatni indeks znalezionego poddciągu.
Wskazówka
  1. Zastosuj metodę dziel i zwyciężaj.
Rozwiązanie
Rozwiązanie zadania należy przesłać do mnie mailem. W treści listu należy powinny się znaleźć następujące informacje:
  1. imię i nazwisko;
  2. program w języku C++, który rozwiązuje opisane zadanie.
Wysyłając list wpisz w tytule 14 LO - zadanie 12.
Punkty
Za rozwiązanie tego zadania można otrzymać do 7 punktów.
Termin
Termin nadsyłania rozwiązań upływa w poniedziałek 11 maja 2009 r. o godzinie 23:59.
Zadanie 13
Zadanie (minimalna triangulacja wielokąta wypukłego)
Dany jest zbiór n>3 punktów p0, p1, ..., pn-1, tworzących na płaszczyźnie wielokąt wypukły. Napisz program, który podzieli ten wielokąt na trójkąty w taki sposób, aby suma długości przekątnych (tych które dzielą wielokąt na trójkąty) była minimalna.
Dane
Dane do programu należy odczytać ze standardowego wejścia. Mają one następujący format. W pierwszej linii podana będzie liczba wierzchołków wielokąta wypukłego n, przy czym 1<n≤100. W następnych n wierszach podane będą współrzędne tych wierzchołków jako pary liczb (xi,yi), dla i=0...n-1. Punkty te będą kolejnymi wierzchołkami wielokąta, czytamymi w kierunku odwrotnym do ruchu wskazówek zegara. Każdy punkt to para liczb rzeczywistych oddzielonych od siebie spacjami.
Wyniki
Rozwiązanie należy wypisać na standardowym wyjściu. W pierwszej linii wypisz wartość minimalnej triangulacji podanego wielokąta a w drugiej linii wypisz numer wierzchołka, z którym połączny będzie wierzchołek 0, albo wartość -1, gdy żadna przekątna nie będzie do niego dochodzić.
Wskazówka
  1. Zastosuj metodę programowania dynamicznego.
Rozwiązanie
Rozwiązanie zadania należy przesłać do mnie mailem. W treści listu należy powinny się znaleźć następujące informacje:
  1. imię i nazwisko;
  2. program w języku C++, który rozwiązuje opisane zadanie.
Wysyłając list wpisz w tytule 14 LO - zadanie 13.
Punkty
Za rozwiązanie tego zadania można otrzymać do 7 punktów.
Termin
Termin nadsyłania rozwiązań upływa w poniedziałek 18 maja 2009 r. o godzinie 23:59.
Zadanie 14
Zadanie (najdłuższy podciąg rosnący)
Dany jest ciąg liczb całkowitych A = (a0, a1, ..., an-1) o długości n. Znajdź w tym ciągu długość najdłuższego podciągu rosnącego i wypisz jeden z nich.
Dane
Dane do programu należy odczytać ze standardowego wejścia. Mają one następujący format. W pierwszej linii podana będzie długość n ciągu A, przy czym 1≤n≤1000000. W drugiej linii zapisany będzie ciąg A. Ciąg będzie się składał z małych liter alfabetu angielskiego.
Wyniki
Rozwiązanie należy wypisać na standardowym wyjściu. W pierwszej linii wypisz długość najdłuższego podciągu rosnącego a w drugiej jeden z takich podciągów, który może być rozwiązaniem.
Wskazówka
  1. Zastosuj metodę programowania dynamicznego.
Rozwiązanie
Rozwiązanie zadania należy przesłać do mnie mailem. W treści listu należy powinny się znaleźć następujące informacje:
  1. imię i nazwisko;
  2. program w języku C++, który rozwiązuje opisane zadanie.
Wysyłając list wpisz w tytule 14 LO - zadanie 14.
Punkty
Za rozwiązanie tego zadania można otrzymać do 7 punktów.
Termin
Termin nadsyłania rozwiązań upływa we wtorek 26 maja 2009 r. o godzinie 23:59.

Ogłoszenia:

25.05.2009
Zapomniałem wcześniej opisać zadanie, o którym rozmawialiśmy na lekcji. Zrobiłem to przed chwilą, dlatego termin jego oddania jest przedłużony do wtorku.
14.05.2009
Dostałem informacje od 5 osób, że pójdą na sparing: Pawła, Agaty, Doroty, Wojtka i Miłosza. Jak ktoś jeszcze chciałby pójść na sparing, zobaczyć jak to wygląda, popróbować swoich sił w C++ i na koniec skonsumować pizzę, to proszę się kontaktować bezpośrednio z opiekunem wycieczki informatycznej lub dyrekcją.
13.05.2009
Junior Spring Challenge - sparing programistyczny w C++. Odbędzie się 15 maja 2009 w Instytucie Informatyki Uniwersytetu Wrocławskiego (obok Mostu Grunwaldzkiego). Udział w zawodach wezmą gimnazjaliści z Wrocławia oraz licealiści, którzy w bieżącym roku szkolnym rozpoczęli naukę programowania w języku C++.
Zawody będą indywidualne, oceniane częściowo. Poziom trudności dostosowany do uczestników OIG - ale wśród zadań na pewno znajdzie się także kilka trochę prostszych.
Spotykamy się w najbliższy piątek, punktualnie o godzinie 12:05, w sali nr 25 (Aula Wielka Wschodnia), w budynku Instytutu Informatyki na ulicy Joliot-Curie. Zawody skończą się po godzinie 17:00.
Ważne! Proszę wszystkie osoby z klasy IA, które chciałyby wziąć udział w sparingu, aby wysłały mi swoje zgłoszenie - sprawa jest pilna, bo jutro rano muszę zgłosić dyrekcji listę uczestników. Do tej pory swój udział zadeklarowały tylko Agata i Dorota. Nie ukrywam, że liczę na większą liczbę zawodników. Przypominam też, że udział w sparingu będzie sowicie nagrodzony punktami...
29.04.2009
Zauważyłem u Was jakąś wiosenną niemoc twórczą. Przedłużam więc termin nadsyłania zad.10 do dnia 4 maja 2009.
7.04.2009
Do końca Świąt Wielkanocnych macie czas na zrobienie lub poprawienie dwóch ostatnich zadań: zad.7 (ciągi liczb pierwszych) i zad.8 (najkrótsza ścieżka w grafie ważonym).
13.02.2009
Proszę się przygotować do klasówki na najbliższe zajęcia. Zadanie będzie dotyczyło operacji na plikach.
1.02.2009
W tym miejscu będą umieszczane różne informacje dotyczące organizacji zajęć. Proszę je czytać na bieżąco.

 

powrót na początek strony