Кружок по информатике, среда с 15:43, 2017-2018

6 сентября 2017 - изучение языка С++.

  • Ввод и вывод
  • Файлы
  • Типы vector, string
  • Передача в функции по ссылке
  • Сортировка и бинпоиск с помощью встроенных функций
  • Решение задачек

13 сентября 2017 - введение в графы.

  • Многомерные массивы
  • Способы задания графов в программах
  • Очередь
  • Поиск кратчайшего пути в невзвешенном графе
  • Решение задачек

20 сентября 2017 - обход в глубину.

  • Обход графа в глубину, свойства дерева обхода в глубину
  • Разбиение на компоненты связности
  • Проверка двудольности
  • Решение задачек

27 сентября 2017 - основы динамического программирования.

  • Одномерная динамика
  • Динамика на таблицах
  • Биномиальные коэффициенты
  • Поиск наибольшей общей подпоследовательности
  • Поиск наибольшей возрастающей подпоследовательности за O(n2)
  • Поиск наибольшей возрастающей подпоследовательности за O(n lon n)
  • Решение задачек
  В жанре подсказки
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;
ifstream fin("input.txt");
ofstream fout("output.txt");

void print(vector <int> &v) {
	int n = v.size();
	string s;
	s = "Vector is sorted:";
	fout << s << ' ';
	for (int i = 0; i < n; i++) {
		fout << v[i] << ' ';
	}
	fout << '\n';
	return;
}

int main()
{
	int n, a, b;
	fin >> n >> a >> b;
	fout << a << " + " << b << " = " << a + b << '\n';
	vector <int> v(n);
	for (int i = 0; i < n; i++) {
		fin >> v[i];
	}
	sort(v.begin(), v.end());
	print(v);
	return 0;
}

Может быть полезно почитать про поиск в ширину, поиск в глубину и динамическое программирование (тему "Динамика и матрица переходов" смело пропускайте). Также можно почитать про префиксные суммы и про разреженные таблицы.

4 октября - мосты и точки сочленения.

  • Мосты и точки сочленения
  • Динамическое программирование по поддеревьем
  • Решение задачек

11 октября - минимумом и сумма на неизменяемом массиве.

Следующее занятие - 18 октября

  • Дерево отрезков
  • Реализация дерева отрезков на массиве
  • Массовые операции в дереве отрезков
  • Решение задачек