Home

Kółko Informatyczne Szkoły Żagle

Rok szkolny 2015/16

8 marca. Algorytmy na liczbach naturalnych: rozkład na czynniki pierwsze

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) (wysyłanie rozwiązania)

Dodatkowo - zagadka.

HYXVKAZRNXNOFFYXNEFFUFKRMFYXN ERZTQUNRJTRJOTKAISUFUXVUFHYXW ULRZXVYWVFXWIOFKXHZHSTHRBOMTH QSIHKXHJUFZGKZHSEBKNTCWMLKTKV GXESSTHRJOTATRAAFPHRKTVFNWGNR VBKNTVLGHXERRGHZWSEMCYILNTWZH IJGSZJCRFHGCCJMEANXLLXRYQFGHK MBVWXUDSRMLOTKRLMZHSNKIZCVVWW KRJRGXUFHYXEJMWEBWZROKBSTOTKA IJIODHRJDWJMVOCHPXWOAZFGICHCJ BKTTVZLAOTVDRXXUSETQKOFKXKG

1 marca. Pętle, pętle, pętle

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.

Pytacie po co?
Zadanie Lustro.
Zadanie Digit Counting

Do domu: zadanie Liczby pierwsze, Iloczyn liczb pierwszych***

22 lutego. AOAPC II: Arrays and Strings

Plan na dziś: 1) powtórzymy pętle i tablice jednowymiarowe; 2) nauczymy się wykorzystywać procedury, by nadawać programowi bardziej modularną strukturę.

Dwa słowa o zawodach ACM ICPC

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 pliku molar_mass.cpp w swoim katalogu w repozytorium.
Zadanie domowe: Score. Rozwiązanie zadania proszę umieścić w katalogu uva/ w pliku score.cpp w swoim katalogu w repozytorium.

Dla chętnych - zadania pozostałe.

26 stycznia. Dwa łyki programowania dynamicznego

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)

19 stycznia. Implementacja rozwiązań - szczegóły techniczne

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.

12 stycznia. Tablice dwuwymiarowe. Algorytmy typu brute-force

Omawialiśmy rozwiązania zadań szachy i labirynt.

15 grudnia. Tablice

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.

8 grudnia. Pętle

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

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.

Zadania

Zadanie N znaków
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
......
......
......
######
######
######

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ą