Информатика, поток 2020-2022 годов

Эта страница будет постепенно наполняться относящимся к обучению граждан информатике, а пока есть только:

Для умеющих считывать (и интерпретировать) QR-коды:
Где-то тут зарыт URL

Удалённая сдача заданий

В моменты удалённого обучения практикуется удалённая сдача заданий. В остальные моменты она может практиковаться, но при моём хорошем понимании, почему её не было в отведённое для этого время в школе.

Я, вообще говоря, задания готов принимать в любой день (когда могу). Удалённо — через Skype. Механика такая: вы мне звоните (лично) и включаете демонстрацию экрана (окна SSH-клиента, которое ведёт на сервер). Дальше мы с вами начинаем обсуждать разное: я — понимать, что вы сделали, вы — разбираться в сути моих вопросов. И итерациями мы, надеюсь, придём к сданной задаче.

Очередь сдачи (особенно удалённой) вы контролируете сами (то есть коллективными силами сдающих граждан), а при сдаче не задерживаете сверх меры других желающих сдать, отключаясь, думая в спокойной обстановке и подключаясь обратно (в рамках живой или какой-либо другой очереди, которую, напомню, контролируете сами).

Оценки, 10 класс

~~~~~~~~~~~~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+
Задание:     |01|02|03|4a|4b|05|06|07|8a|8b|X1|09|10|11|12|13|14|
Ученик ------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Гусев        |3 |3 |  |  |  |3 |  |  |  |  |  |  |  |  |  |  |  |
Гуров        | 4| 5| 5|  |  | 3| 3| 3|  | 3|  | 3| 3| 4|  | 3|  |
Игнатьев     |5 |5 |4 |3 |3 |3 |3 |3 |3 |3 |  |3 |3 |3 |3 |3 |3 |
Константинов | 3| 5| 3| 3| 3| 3| 3| 3| 3| 3|  | 4| 3| 4| 3| 3| 3|
Кряженкова   |5 |5 |5 |3 |3 |3 |3 |3 |3 |3 |  |3 |3 |3 |3 |3 |3 |
Павлов       | 3| 5| 3| 3| 3| 3| 3| 5| 3| 3|  | 3| 3| 3| 4| 3| 5|
Панкратов    |5 |5 |5 |5 |3 |5 |5 |4 |3 |4 |  |5 |5 |3 |5 |3 |5 |
Сидорчук     | 3| 4| 3| 3| 3| 3| 5| 5| 3| 4|  | 4| 3| 3| 3| 3| 3|
Тихонов      |5 |3 |3 |4 |4 |3 |4 |5 |3 |3 |  |3 |3 |3 |3 |3 |3 |
Терехов      | 3| 3| 3| 4| 4| 4| 5| 4| 3| 4|  | 5| 3|  | 3| 3| 3|
-------------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Бажанов      |4 |5 |5 |3 |3 |3 |5 |5 |5 |5 |  |5 |5 |  |3 |3 | 3|
Гудков       |  |  |  |  |  |  | 3| 3|  |  |  |  | 3|  |  |  |  |
Лебедев      |3 |  |3 |  |  |3 |3 |3 |3 |3 |  |3 |3 |  | 3| 3| 3|
Меркулов     | 4| 5| 5|  |  | 3| 3| 5|  |  |  |  | 3|  |  |  |  |
Нефф         |5 |5 |5 |5 |  |5 |4 |5 |3 |  |  |4 |3 |  |  |  |  |
Савченко     | 3| 5|  |  |  |  |  | 3|  | 3|  | 5| 3|  |  |  |  |
Сахин        |5 |5 |5 |3 |3 |5 |5 |5 |5 |5 |  |5 |5 |5 |4 |4 |3 |
Старовойтов  | 5| 5| 5| 3| 3| 3| 5| 5| 5| 5|  | 5| 5| 3| 4| 3| 3|
Ческис       |5 |5 |5 |5 |5 |5 |5 |5 |5 |4 |  |5 |5 |3 |4 |4 |4 |
Шильников    |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
-------------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Герасимов    |5 |5 |5 |3 |3 |5 |4 |5 |4 |4 |  |4 |4 |4 |3 |4 |4 |
Маркин       |  | 5| 5|  |  |  |  |  |  |  |  |  |  |  |  |  |  |
Матафонов    |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
Мирзоев      | 5| 3|  |  |  | 3| 5| 5|  | 3|  | 3| 3|  |  |  | 3|
Никульшин    |3 |5 |3 |3 |3 |3 |4 |5 |3 |3 |  |  |5 |3 |3 |3 |3 |
Потошин      | 4| 5| 5| 5| 4| 3| 3| 3| 3| 3|  | 4| 4| 4| 5| 3| 5|
Рыморенко    |5 |5 |5 |5 |5 |4 |5 |5 |3 |3 |  |4 |4 |3 |3 |3 |3 |
Ходаков      | 4| 5| 5| 4| 3| 5| 5| 5| 5| 5|  | 5| 3| 4| 5| 5| 5|
Хоронский    |4 |5 |5 |  |  |3 |4 |5 |3 |3 |  |3 |4 |  |3 |3 |  |
Цветков      | 3| 3| 3| 3| 3| 3| 3| 3| 3| 3|  | 3| 3| 3| 3| 3| 4|
-------------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Задание:     |01|02|03|4a|4b|05|06|07|8a|8b|X1|09|10|11|12|13|14|
~~~~~~~~~~~~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+

Расшифровка номеров заданий. 01: Кардано. 02: выборки. 03: «пи». 4a: l/2. 4b: хорда. 05: 0.5*круг. 06: НО[К/Д]. 07: stddev. 8a: count. 8b: ins. 09: bubble. 10: fib. 11: qsort. 12: strXXX. 13: палиндромы. 14: %d.

~~~~~~~~~~~~~+~~+~~~+~~~+~~~+~~+~~+~~+~~+~~+~~+~~+~~+~+
Задание:     |15|16a|16b|16c|17|18|19|20|21|22|23|X2|Y|
Ученик ------+--+---+---+---+--+--+--+--+--+--+--+--+-+
Гусев        |  |   |   |   |  |  |  |  |  |  |  |  |0|
Гуров        |  |  3|  3|  3| 5|  |  |  |  |  |  |  |1|
Игнатьев     |3 |3  |3  |3  |4 |  |  |  |5 |  |5 |  |2|
Константинов | 3|  4|  4|  4| 4| 5| 5| 5| 5| 5| 5|  |4|
Кряженкова   |  |3  |3  |3  |4 |  |  |  |  |  |  |  |2|
Павлов       | 3|  3|  3|  3| 5| 5| 5| 5| 5| 5| 5|  |4|
Панкратов    |3 |5  |5  |5  |4 |  |5 |  |5 |  |5 |  |2|
Сидорчук     | 3|  3|  3|  3| 4| 5| 5| 5| 5| 5| 5|  |4|
Тихонов      |3 |3  |3  |3  |4 |5 |5 |5 |5 |5 |5 |  |4|
Терехов      |  |  3|  3|  3| 4| 5|  | 5| 5| 5| 5|  |2|
-------------+--+---+---+---+--+--+--+--+--+--+--+--+-+
Бажанов      |3 |5  |3  |3  |  |  |  |  |  |  |  |  |2|
Гудков       |  |   |   |   |  |  |  |  |  |  |  |  |0|
Лебедев      |3 |3  |3  |3  |4 |  |  |  |  |  |  |  |1|
Меркулов     |  |  3|  3|  3| 4|  |  |  |  |  |  |  |1|
Нефф         |  |5  |5  |5  |  |  |  |  |  |  |  |  |1|
Савченко     |  |  4|  4|  4|  |  |  |  |  |  |  |  |1|
Сахин        |3 |5  |5  |5  |3 |  |  |  |  |  |  |  |2|
Старовойтов  | 3|  5|  5|  5| 4|  | 5| 5| 5| 5|  |  |3|
Ческис       |3 |4  |4  |4  |4 |5 |5 |5 |5 |5 |5 |  |5|
Шильников    |  |   |   |   |  |  |  |  |  |  |  |  |0|
-------------+--+---+---+---+--+--+--+--+--+--+--+--+-+
Герасимов    |3 |4  |5  |5  |5 |  |5 |5 | 5| 5| 5|  |3|
Маркин       |  |   |   |   |  |  |  |  |  |  |  |  |0|
Матафонов    |  |   |   |   |  |  |  |  |  |  |  |  |0|
Мирзоев      |  |  3|  3|  3| 4| 5|  |  | 5| 5|  |  |2|
Никульшин    |3 |3  |3  |3  |4 |  |  |  |  |  |  |  |2|
Потошин      | 3|   |   |   | 4|  |  |  |  |  |  |  |2|
Рыморенко    |  |  3|  3|  3|  |  |  |  |  |  |  |  |2|
Ходаков      |5 |4  |4  |4  |5 |5 |  |  |5 |5 |  |  |2|
Хоронский    |  |   |  3|   |  |  |  |  |  |  |  |  |1|
Цветков      |3 |5  |5  |5  |4 |5 |5 |5 |5 |5 |5 |  |4|
-------------+--+---+---+---+--+--+--+--+--+--+--+--+-+
Задание:     |15|16a|16b|16c|17|18|19|20|21|22|23|X2|Y|
~~~~~~~~~~~~~+~~+~~~+~~~+~~~+~~+~~+~~+~~+~~+~~+~~+~~+~+

Расшифровка номеров заданий. 15: str sort. 16a: horiz. 16b: diag. 16c: улитка. 17: sizeof. 18: битовые О. 19: ферзи. 20: конь. 21: Цезарь. 22: XOR. 23: частота.

Домашние задания, 10 класс

18.05.2021: задание #23, частота символов

Написать программу, выводящую частоту встречи каждого из символов, содержащихся в указанном файле. Выводимая таблица должна быть отсортирована по убыванию частоты символов.

14.05.2021: задание #22, XOR-кодирование

XOR-кодирование: входной поток байтов побитово объединяется с потоком, полученным повторением ключевого слова (пароля) необходимое количество раз. Операция объединения — исключающее «ИЛИ» (exclusive OR, XOR).

Параметры командной строки программы:

14.05.2021: задание #21, шифр Цезаря

Шифр Цезаря — циклический сдвиг всех букв алфавита на указанное количество символов.

Параметры командной строки программы:

27.04.2021: задание #20, обход доски конём

Необходимо найти все возможные пути полного обхода шахматной доски размером MxN конём, начинающим движение с клетки (x, y). Полным обходом называется траектория, проходящая через каждую клетку только единожды. Замкнутой (когда из последней точки можно за один ход попасть в первую) траектория быть не обязана.

Четвёрки параметров M, N, x и y задаются в командной строке.

27.04.2021: задание #19, расстановка ферзей

На шахматной доске размера NxN необходимо найти все варианты расстановки N ферзей так, чтобы ни один из них не бил другого.

Размеры досок, на которых нужно решить задачу, задаются в параметрах командной строки программы.

16.04.2021: задание #18, битовые операции

16.04.2021: задание #17, sizeof

Вывести на экран размеры (в байтах), занимающие переменными всех известным вам типов и указателями на них.

02.04.2021: задание #16, заполнения прямоугольника

Заполнить двумерный массив размерности MxN (M может быть не равно N) последовательными целыми числами от единицы до M*N следующими способами:

  1. по горизонтали, изменяя направление движения на каждой строке (некоторые это называют бустрофедоном, но мы их за это простим; а, быть может, даже и за это);
  2. по диагонали, начиная с верхнего левого угла и двигаясь вдоль диагональных направлений «отскакивая от стенок массива»;
  3. по спирали, закручивающейся вовнутрь массива.

Поясняющая картинка:
...была бы тут, если бы её воспроизвели

26.03.2021: задание #15, сортировка строк

Пользуясь объяснённой идеологией compare/swap для общих алгоритмов сортировки, необходимо лексикографически («в алфавитном порядке») отсортировать массив из N вводимых пользователем строк.

Compare и swap реализуются отдельными функциями, алгоритм сортировки можно выбирать любой (идеологически-соответствующий ;)

23.03.2021: задание #14, %d?

Для вводимого с клавиатуры целого числа нужно распечатать его представление в какой-либо системе счисления (двоичной, десятичной, шестнадцатиричной, шестидесятиричной, …).

Из всех процедур вывода на экран можно использовать только конструкцию «printf("%c", ch)».

23.03.2021: задание #13, палиндромы

Для вводимых строк требуется отличать строки-палиндромы от остальных. Палиндром — фраза, в которой буквенное содержимое является одинаковым при прочтении слева направо и справа налево.

У программы должны быть предусмотрены режимы сравнения симоволов введённой строки с учётом их регистра и без такого учёта.

Программа завершается при вводе строки «end».

23.03.2021: задание #12, строковые операции

Написать программу, проделывающую с вводимыми пользователем двумя строками следующие операции:

  1. подсчёт количества введённых символов (длины строки) в обоих строках;
  2. выяснение, одинаковы ли обе введённых строки или они отличаются друг от друга;
  3. копирование первой введённой строки в отдельный массив;
  4. конкатенация (дописывание в конец) содержимого второй строки с содержимым отдельного массива.

Все манипуляции должны быть оформлены в виде отдельных функций. Пользоваться стандартными процедурами strlen, strncat, strncpy и подобными — нельзя.

16.03.2021: задание #11, быстрая сортировка

Реализовать сортировку массива чисел алгоритмом быстрой сортировки (также известным, как quicksort и алгоритм Хоара).

А то Хоар был в Москве, мы в ней, чего же не напрограммировать сортировку: C.A.R. считает, что она — «still widely used for sorting». Не будем же его огорчать.

12.03.2021: задание #10, числа Фибоначчи

Написать программу, рекурсивным образом вычисляющую заданное количество чисел Фибоначчи, начиная с первого (которое равно второму и оба — единице). Количество чисел задаётся пользователем.

09.03.2021: задание #9, сортировка «пузырьком» («затоплением»)

Предыдущее задание, но используя метод «пузырька».

09.03.2021: не задание, но десятиминутка

Разделились на группы (в-основном) потрое и осиливали это вот.

05.03.2021: задание #8, сортировки подсчётом и вставкой

Для случайно-генерируемого массива необходимо написать программу, которая сортирует его содержимое методами подсчёта и вставки, выводя на экран результаты.

При сдаче неплохо понимать вопросы стабильности и нестабильности сортировок: как общие, так и относящиеся к конкретным реализациям алгоритмов.

02.03.2021: задание #7, статистический анализ данных

Требуется сделать программу, которая заполняет массив заранее известной длины либо вводимыми с клавиатуры, либо генерируемыми случайно числами. А затем ищет следующие характеристики полученного набора данных:

19.02.2021: задание #6, НОК/НОД

Необходимо написать пару программ, вычисляющих

  1. наибольший общий делитель (НОД) и наименьшее общее кратное (НОК) пары вводимых чисел,
  2. наибольший общий делитель трёх вводимых программе чисел.
Разлагать исходные числа на множители категорически не рекомендуется.

09.02.2021: задание #5, пол площади круга

Пользуясь стандартным определением левой и правой интегральных сумм (для неубывающей монотонной функции они — им. товарища Дарбу),

σL = ∑ f(xk) Δk, σR = ∑ f(xk+1) Δk,
посчитать определённый интеграл от функции y(x) = [R2 - x2]½ на отрезке [-R, R].

Изучить зависимость получающихся результатов от количества точек, разбивающих отрезок, и от значения R. Проследить за сходимостью (если она есть) обеих сумм к более-менее общеизвестному ответу — половине площади круга некоторого диаметра.

На сдаче лучше быть способным объяснить, как получаются длина окружности и площадь круга, понимать теорему о «двух милиционерах», уметь брать разные пределы и вообще…

29.01.2021: задание #4, поиск нуля функции, Больцано + Коши = ?

Необходимо написать программу, которая методом «зажатия» области расположения какого-либо корня уравнения f(x) = 0, в окрестности этого самого корня x0: |x0 - X| < e. Здесь X — найденный программой корень, e — точность.

Уравнение решается на отрезке [a, b], на котором выполнено условие f(a) * f(b) ≤ 0. Если такое условие не выполнено, программа должна об этом сообщать.

Программа должна позволять выбирать алгоритмы выбора промежуточной точки как минимум из набора

  1. деление отрезка пополам,
  2. проведение секущей прямой через точки (a, f(a)) и (b, f(b)).
Можно добавить другие способы, по вашему выбору.

При сдаче лучше бы понимать, насколько разные методы отличаются друг от друга (какой быстрее, для каких функций), и как можно оценить точность вычисления нуля самой функции (величину |f(X)| то есть).

Функцию f(x) нужно выбирать непрерывной и более-менее нетривиальной. Скажем, f(x) = cos(x2)/[x4 + 1], в отличие от f(x) = 0, является более-менее нетривиальной. Определением непрерывной функции хорошо бы тоже владеть (знать + уметь пользоваться).

25.12.2020: задание #3, посчитаем π в первый раз

Пользуясь соотношением π2/6 = ∑k = 1 (1/k2) написать программу вычисления числа π с точностью до n первых десятичных знаков (n должно быть по-крайней мере не меньше 5 — 7).

При пособничестве написанной программы необходимо уметь ответить на вопрос «Сколько членов ряда нужно взять, чтобы получить от нуля до максимального (в вашем варианте программы) количества верных десятичных знаков?»

При сдаче (а то и до неё) неплохо бы понимать признаки сходимости знакопостоянных рядов и уметь доказывать сходимость используемого ряда.

25.12.2020: задание #2, количества выборок

Необходимо реализовать программу, вычисляющую количества (уникальных, то есть неразличимых) выборок k предметов из n штук, для случаев, когда все предметы a) различны, б) одинаковы. При этом необходимо реализовать вычисление для максимально широкого диапазона значений n и k, да уметь пояснить, каков именно этот диапазон и почему он именно таков.

18.12.2020: задание #1, решение кубического уравнения

Для заданных значений коэффициентов многочлена p(x) = ax3 + bx2 + cx + d необходимо найти все корни уравнения p(x) = 0.

Если кто-то не слишком хорошо понимает, как быть со случаем комплексных корней — можно искать только вещественные решения. Для остальных (на всякий случай) краткие заметки о комплексных числах.

Необходимо рассмотреть все случаи значений набора коэффициентов.