Home
- Dla najbardziej zaawansowanych - BFS
- Grupa pracująca nad samochodzikiem - połączenie wszystkich kabelków i zrobienie schematu
- Dla średniozaawansowanych - inny sposób zrobienia zadania akcelerator
- Dla początkujących - totemy
- Miłośnicy grafiki komputerowej - kolejka zdarzeń
- Zadanie klub prawoskrętnych kierowców
Dziś najważniejszym celem jest skończenie montażu samochodu. Wystarczy, by jeździł w przód i zatrzymywał się przed przeszkodą.
Celem drugorzędnym jest zrobienie diagramu połączeń samochodu, podobnego np. do tego diagramu. Odpowiednie narzędzie znajdziecie na stronie fritzing.org.
Pomysł: przetworzenie danej tablicy liczba na tablicę par: (liczba, liczba jej wystąpień) i wyszukiwanie liczb normalnym sposobem.
Struktura danych omawiana podczas zajęć.
struct para
{
int l; // liczba
int w; // liczba wystąpień
};
struct para t[10000];- Zadanie flaga polska
Napisz program, który odczytuję liczbę n a następnie wyświetla flagę polską o szerokości 4n i wysokości 2n.
3
......
......
......
######
######
######- Zadanie helikopter
- Zadanie piramida
- Kolejka zdarzeń
#include <iostream>
using namespace std;
#include <allegro5/allegro.h>
int main(int, char**)
{
ALLEGRO_DISPLAY *display = NULL;
ALLEGRO_EVENT_QUEUE *event_queue = NULL;
ALLEGRO_TIMER *timer = NULL;
if (!al_init() || !al_install_mouse() || !al_install_keyboard()) {
cout << "Inicjalizacja nie powiodła się." << endl; return -1;
}
timer = al_create_timer(1.0);
display = al_create_display(800, 600);
event_queue = al_create_event_queue();
if (!timer || !display || !event_queue) {
cout << "Inicjalizacja nie powiodła się." << endl; return -1;
}
al_register_event_source(event_queue, al_get_display_event_source(display));
al_register_event_source(event_queue, al_get_timer_event_source(timer));
al_register_event_source(event_queue, al_get_mouse_event_source());
al_register_event_source(event_queue, al_get_keyboard_event_source());
al_start_timer(timer);
while (true) {
ALLEGRO_EVENT ev;
al_wait_for_event(event_queue, &ev);
// https://www.allegro.cc/manual/5/ALLEGRO_EVENT
cout << "Event type: " << ev.type << " - ";
switch (ev.type) {
case ALLEGRO_EVENT_KEY_DOWN: cout << "ALLEGRO_EVENT_KEY_DOWN";
cout << " kod klawisza " << ev.keyboard.keycode;
break;
case ALLEGRO_EVENT_KEY_UP: cout << "ALLEGRO_EVENT_KEY_UP"; break;
case ALLEGRO_EVENT_KEY_CHAR: cout << "ALLEGRO_EVENT_KEY_CHAR"; break;
case ALLEGRO_EVENT_MOUSE_AXES: cout << "ALLEGRO_EVENT_MOUSE_AXES"; break;
case ALLEGRO_EVENT_MOUSE_BUTTON_DOWN: cout << "ALLEGRO_EVENT_MOUSE_BUTTON_DOWN";
cout << " współrzędne " << ev.mouse.x << " " << ev.mouse.y;
break;
case ALLEGRO_EVENT_MOUSE_BUTTON_UP: cout << "ALLEGRO_EVENT_MOUSE_BUTTON_UP"; break;
case ALLEGRO_EVENT_MOUSE_ENTER_DISPLAY: cout << "ALLEGRO_EVENT_MOUSE_ENTER"; break;
case ALLEGRO_EVENT_MOUSE_LEAVE_DISPLAY: cout << "ALLEGRO_EVENT_MOUSE_LEAVE"; break;
case ALLEGRO_EVENT_TIMER: cout << "ALLEGRO_EVENT_TIMER"; break;
case ALLEGRO_EVENT_DISPLAY_CLOSE: cout << "ALLEGRO_EVENT_DISPLAY_CLOSE"; break;
}
cout << endl;
}
al_destroy_timer(timer);
al_destroy_display(display);
al_destroy_event_queue(event_queue);
return 0;
}- Napisz program, który wyświetli na ekranie klawiaturę pianina (i jej fragment) i będzie reagował na naciśnięcia klawiszy
#include <MidiFile.h>
#include <Options.h>
#include <vector>
#include <iostream>
#include <iomanip>
#include <fluidsynth.h>
#include <allegro5/allegro.h>
#include <allegro5/allegro_primitives.h>
using namespace std;
class Note
{
public:
int p, k;
int f;
int v;
};
class State
{
public:
int t;
vector<Note> n;
};
int main(int argc, char** argv)
{
if (!al_init() || !al_init_primitives_addon()) {
cout << "Błąd inicjalizacji allegro." << endl; return -1;
}
ALLEGRO_DISPLAY *display = NULL;
display = al_create_display(1000, 600);
// Konfiguracja biblioteki fluidsynth
fluid_settings_t* settings;
fluid_synth_t* synth;
fluid_player_t* player;
fluid_audio_driver_t* adriver;
settings = new_fluid_settings();
synth = new_fluid_synth(settings);
player = new_fluid_player(synth);
fluid_settings_setstr(settings, "audio.driver", "portaudio");
adriver = new_fluid_audio_driver(settings, synth);
// Do prawidłowego działania potrzebny jest Sound Font
fluid_synth_sfload(synth, "fluidr3.sf2", 1);
// Potrzebny jest też plik MIDI
MidiFile midifile;
midifile.read("scott-joplin-peacherine-rag.mid");
midifile.joinTracks();
int e = 0;
int tick = 0;
int start[256];
int v[256];
// Czytanie pliku MIDI i konwersja na nasz wewnętrzny format
State s;
while (e < midifile[0].size()) {
while (e < midifile[0].size() && midifile[0][e].tick <= tick) {
cout << "Tick: " << tick << ". ";
cout << "Event: " << e << ". ";
if ((midifile[0][e][0] & 0xF0) == 0x90 && midifile[0][e][2] > 0) {
cout << " Note ON (track " << midifile[0][e].track << ") " << (int) midifile[0][e][1] << ".";
start[midifile[0][e][1]] = tick;
v[midifile[0][e][1]] = midifile[0][e][2];
} else if ((midifile[0][e][0] & 0xF0) == 0x80
|| ((midifile[0][e][0] & 0xF0) == 0x90 && midifile[0][e][2] == 0)) {
cout << " Note OFF " << (int) midifile[0][e][1] << ".";
Note n;
n.p = start[midifile[0][e][1]];
n.k = tick;
n.v = v[midifile[0][e][1]];
n.f = midifile[0][e][1];
s.n.push_back(n);
} else {
cout << " Event type " << hex << (int) midifile[0][e][0] << " " << (int) midifile[0][e][1] << " " << (int) midifile[0][e][2] << dec;
}
cout << endl;
e++;
}
tick++;
}
// Odegranie utworu
ALLEGRO_EVENT_QUEUE *event_queue = NULL;
ALLEGRO_TIMER *timer = NULL;
timer = al_create_timer(1.0/300.0);
event_queue = al_create_event_queue();
al_register_event_source(event_queue, al_get_display_event_source(display));
al_register_event_source(event_queue, al_get_timer_event_source(timer));
al_start_timer(timer);
vector<Note>::iterator i = s.n.begin();
tick = 0;
bool play = true;
bool redraw = true;
while (play) {
ALLEGRO_EVENT ev;
al_wait_for_event(event_queue, &ev);
if(ev.type == ALLEGRO_EVENT_TIMER) {
redraw = true;
}
bool redraw_now = redraw && al_is_event_queue_empty(event_queue);
play = false;
if (redraw_now) {
al_clear_to_color(al_map_rgb(0,0,0));
}
for (Note n: s.n) {
if (n.p >= tick || n.k >= tick) {
play = true;
}
if (n.p == tick) {
cout << n.p << " -- " << n.k << ": " << n.f << " " << n.v << endl;
fluid_synth_noteon(synth, 0, n.f, n.v);
}
if (n.k == tick) {
fluid_synth_noteoff(synth, 0, n.f);
}
if (redraw_now) {
if (n.p <= tick && n.k >= tick) {
al_draw_filled_rectangle(n.f * 10, n.p - tick, n.f * 10 + 9, n.k - tick, al_map_rgb(0,0,255));
} else {
al_draw_filled_rectangle(n.f * 10, n.p - tick, n.f * 10 + 9, n.k - tick, al_map_rgb(255,255,255));
}
}
}
if (redraw_now) {
al_flip_display();
redraw = false;
}
tick++;
}
delete_fluid_audio_driver(adriver);
delete_fluid_player(player);
delete_fluid_synth(synth);
delete_fluid_settings(settings);
return 0;
}-
Piłeczki i kubeczki
-
Gra w 20 pytań
- Wariant I: komputer wymyśla liczbę
- Wariant II: komputer odgaduje liczbę
-
Obliczanie wartości pierwiastka z 2 (z dowolną dokładnością)
-
Wyszukiwanie wartości w tablicy: zaokrąglenie w górę, czy w dół? Co, gdy liczby nie ma? Co, gdy jest więcej niż jedna?
- Jak szyfrowało się dawniej, jak szyfruje się teraz.
FRJLWRHUJRVXP
-
Szyfr Cezara: jest to szyfr za pomocą którego Juliusz Cezar szyfrował swoje listy do Cycerona. Jako ciekawostkę można podać, że szyfr ten był podobno używany jeszcze w 1915 roku w armii rosyjskiej, gdyż tylko tak prosty szyfr wydawał się zrozumiały dla sztabowców
-
Szyfr RSA: Po co faktoryzacja?
- Testy pierwszości, rozkład na czynniki pierwsze - złożoność.
Zadania: Liczby pierwsze (wysyłanie rozwiązania), [Rozkład] (https://zadania.oig.edu.pl/OIG/stored_files/pdfPreview/4366155) (wcześniej wymagane zalogowanie się na stronie OIG)
- Dodatkowo - zagadka.
HYXVKAZRNXNOFFYXNEFFUFKRMFYXN ERZTQUNRJTRJOTKAISUFUXVUFHYXW ULRZXVYWVFXWIOFKXHZHSTHRBOMTH QSIHKXHJUFZGKZHSEBKNTCWMLKTKV GXESSTHRJOTATRAAFPHRKTVFNWGNR VBKNTVLGHXERRGHZWSEMCYILNTWZH IJGSZJCRFHGCCJMEANXLLXRYQFGHK MBVWXUDSRMLOTKRLMZHSNKIZCVVWW KRJRGXUFHYXEJMWEBWZROKBSTOTKA IJIODHRJDWJMVOCHPXWOAZFGICHCJ BKTTVZLAOTVDRXXUSETQKOFKXKG
- Zadanie z wieloma gwiazdkami - dla tych, którzy się nudzą.
Nauczeni doświadczeniem sprzed tygodnia wracamy do pętli - soli programowania.
Na początek - motywacja: Prime Spirals - Numberphile.
-
Testowanie pierwszości - złożoność? Materiał dodatkowy: sito Eratostenesa.
-
Zadanie Lustro.
-
Zadanie Digit Counting
Do domu: zadanie Liczby pierwsze, Iloczyn liczb pierwszych***
Plan na dziś: 1) powtórzymy pętle i tablice jednowymiarowe; 2) nauczymy się wykorzystywać procedury, by nadawać programowi bardziej modularną strukturę.
Pracujemy z zadaniami ze strony AOAPC II: Beginning Algorithm Contests (Second Edition) (Rujia Liu) :: Chapter 3. Arrays and Strings
-
Wspólnie rozwiążemy zadanie Digit Counting
-
Indywidualnie rozwiążecie zadanie Molar Mass (treść czytamy wspólnie). Rozwiązanie zadania proszę umieścić w katalogu
uva/w plikumolar_mass.cppw swoim katalogu w repozytorium. -
Zadanie domowe: Score. Rozwiązanie zadania proszę umieścić w katalogu
uva/w plikuscore.cppw swoim katalogu w repozytorium.
Dla chętnych - zadania pozostałe.
Wciąż dążymy do implementacji szybkiego algorytmu rozwiązującego zadanie Szachy. Przyda nam się do tego technika znana pod nazwą programowania dynamicznego.
Materiał wstępny: Po co komu te algorytmy? - początek wykładu (do ok. 27 minuty).
Zadanie na zajęcia - rozwiązanie omówionego zadania z matury (porównamy wszystkie trzy implementacje). Źródła: arkusz maturalny (zadanie 5), zestawy danych testowych.
Oczekiwane wyniki: 106, 139, 1342.
W jaki sposób programowanie dynamiczne może przyspieszyć rozwiązanie zadania Szachy?
Zadanie do domu: Helikopter, Trójkąt, Słowa Fibonacciego (gr. złota)
Omówimy:
- Rozwiązanie brute-force zadania szachy.
- Deklaracja zmiennych i odczytanie danych wejściowych
- Czterokrotne zagnieżdżenie pętli
- Rozwiązanie optymalne zadania szachy.
- Jak szybko znaleźć największą liczbę w prostokątnym fragmencie szachownicy?
Zadania dla mniej zaawansowanych chcących poćwiczyć zagnieżdżanie pętli i/lub tablice:
- Grupa złota - Helikopter.
- Grupa złota - Trójkąt.
Omawialiśmy rozwiązania zadań szachy i labirynt.
Omówimy zadanie Park Wodny z XXIII OI.
Ćwiczenia dla początkujących: tablice jednowymiarowe i zadania z części "pętla for i tablice" z kursu programowania.
Zapraszam na konkurs w ramach Godziny Kodowania 2015. Zadania z kategorii dzięcioły powinny być w zasięgu wszystkich.
Dzisiejszym tematem są pętle.
Pętla for wypisująca na ekranie liczby od 1 do 10
int i;
for (i = 1; i <= 10; i++) {
cout << i << " ";
}Zwróć uwagę na trzy instrukcje będące parametrami pętli:
-
i = 1- inicjalizacja, wykonywana jednokrotnie na samym początku. -
i <= 10- warunek sprawdzany przed każdym obrotem pętli. Jeżeli warunek jest fałszywy, to program wychodzi z pętli. -
i++- instrukcja wykonywana po każdym obrocie pętli.
Ćwiczenie: zmodyfikuj powyższy program tak, by wypisywał liczby od 0 do 100.
Ćwiczenie: zmodyfikuj powyższy program tak, by wypisywał liczby od 100 do 0.
Ćwiczenie: zmodyfikuj powyższy program tak, by wypisywał liczby parzyste od 0 do 100.
-
Zadanie: flaga polska
Napisz program, który odczytuję liczbę n a następnie wyświetla flagę polską o szerokości 4n i wysokości 2n.
3
......
......
......
######
######
######-
Project Euler: Multiplies of 3 and 5.
Liczby naturalne mniejsze od 10, które są wielokrotnościami 3 lub 5, to 3, 5, 6 i 9. Ich suma równa jest 23.
Napisz program, który oblicza sumę wielokrotności 3 i 5 mniejszych niż 1000.
Wynik zweryfikuj wysyłając rozwiązanie na stronę http://projecteuler.net (trzeba się zarejestrować).
- Project Euler: Even Fibonacci numbers.
W ciągu Fibonacciego kolejny wyraz obliczamy jako sumę dwóch poprzednich. Jeżeli zaczniemy od jedynki i dwójki, pierwszymi dziesięcioma elementami ciągu będą
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Spośród nich 2, 8 i 34 to elementy parzyste - są to jedyne elementy parzyste, których wartość nie przekracza 50. Ich suma to 2 + 8 + 34 = 44.
Zadanie: oblicz sumę parzystych elementów ciągu, których wartość nie przekracza czterech milionów.
Wynik zweryfikuj wysyłając rozwiązanie na stronę http://projecteuler.net (trzeba się zarejestrować).
Z kursu wstępu do programowania obejrzymy dwa filmy - lekcja nr 3 (instrukcja warunkowa)
Podczas zajęć rozwiążesz i wyślesz do oceny w serwisie MAIN2 rozwiązanie zadania ćwiartka
Tak jak poprzednio korzystamy z kompilatora online.
Następnie rozwiązanie opublikujesz w serwisie GitHub.
Zadanie do domu: maksimum. Rozwiązanie zadania proszę przesłać do oceny w MAIN2 i po zaliczeniu umieścić na GitHubie. Termin: 29 listopada.
--
-
Układ dwójkowy
--
