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

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

• список обучающихся;
• список литературы к курсу;
• очень краткое руководство по об(ра)щению с SSH.

• Наглядные и не очень материалы-замечания
• Удалённая сдача заданий
• Е-ГЭ-ГЭ
  • Тренировки
• Оценки, 11 класс
• Домашние задания, 11 класс
• Оценки, 10 класс
• Домашние задания, 10 класс

• Масштабирование растровых изображений, демострация объяснявшегося про векторные/растровые форматы, масштабирование, интерполяцию и растеризацию.
• Начиная с задания 27 необходимо всё сдаваемое оборудовать Makefile, позволяющим (как минимум) собрать программу и подчистить все следы её сборки и работы.
• По многочисленным (15 штук) просьбам родителей, назначен крайний срок сдачи любых шести из восьми заданных в первом полугодии 11 класса заданий (с 24-го по 31-е): 31 декабря 2021 года. Без них (и, конечно, всех сданных за 10 класс заданий) оценка за первое полугодие будет парой.
• В домашнем каталоге каждого есть папка (технически — символическая ссылка) «web». Всё помещаемое в неё (и её подкаталоги) будет доступно, если мы говорим о пользователе 0x14-mn, по адресу http://1189.codelabs.ru/0x14/mn/<путь внутри web>. Все задачи, производящие картинки, видео и прочие материалы, помещают результаты работы куда-то вовнутрь папки «web», чтобы можно было сразу увидеть их в броузере.

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

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

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

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

• вплетание решения разных задач, выпавших в прошлые годы на этом мероприятии,
• некоторые разъяснения в сторону областей (в основном — математики), относящихся к этим задачам и методам их решения,
• решение/разбор олимпиадных задач,
• тренировочные походы.

В конце первого семестра 11 класса Михаил Валентинович любезно опросил всех граждан по поводу их тренированности, участия в олимпиадах и прочего относящегося. Договорились, что все интересующиеся до конца 2021 календарного года пришлют мне и ему на почту примеры задач ЕГЭ (как самих задач, так и их номеров в списке) и олимпиад, которые не получаются, не понятны или вызывают любые другие сложности. По результатам присланного я пойму, на что нужно обращать внимание больше, на что — меньше (ибо все и без меня справляются) и соответственно построю работу во втором семестре. Стало быть, кто не пришлёт списка своих проблем — тот может не получить нужных разъяснений, тренировок и прочего (полезного). Обновление от 12.01.2022: количество приславших договоренное — 2 (прописью: «два»; приславшим — спасибо!), так что начало второго полугодия будет частично потрачено на написание «диагностических вариантов» и выяснение степени (не)подготовленности граждан.

Результаты тренировок оформляются на листочках, которые подписываются текущей датой и фамилией-именем человека. Меня интересуют не только ответы, но и логика решения (фактически, сами ответы менее интересны и это — одна из моих претензий к ЕГЭ). Поэтому все делаемые предположения, их обоснования, логические умозаключения и прочее — им лучше войти в решение каждой задачи. Если в формулировке задачи требуют написать программу, то в решение должен войти её текст (да, увы /?/, написанный на бумажке от руки: есть более-менее обоснованное подозрение, что это поможет вам писать программы с меньшим количеством ошибок/неточностей, в первую очередь алгоритмических и логических). Если у вас под руками есть компьютер, то вдобавок к тексту программы интересны результаты её работы (которые обычно только и требуется приводить в «настоящем ЕГЭ»). Черновики можно прилагать по желанию: на приложенные я посмотрю и использую для анализа происходящего.

Пробный вариант, 12.01.2022.

Пробный вариант, 14.01.2022.

Пробный вариант, 21.01.2022. Поскольку у граждан карантин, то задания делаются дома, на что отведено две пары уроков. В 14:15 тренировка заканчивается, сделанное сканируется/фотографируется (или прямо сразу делается в электронном виде; если это так, то результат экспортируется в формат PDF) и присылается мне по электронной почте. Я ожидаю присланных заданий не позднее 14:33 MSK пятницы, 21 января; время контролируется по~транспортным заголовкам SMTP-сообщений.

~~~~~~~~~~~~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+
Задание:     |24|25|26|27|28|29|30|31|X1|
Ученик ------+--+--+--+--+--+--+--+--+--+
Гусев        |  |  |  |  |  |  |  |  |  |
Гуров        | 3|  |  |  |  |  |  |  |  |
Игнатьев     |5 |4 |5 |5 |5 |5 |  |  |5 |
Константинов | 4| 5| 5| 5| 5|  | 5|  | 5|
Кряженкова   |  |  |  |  |  |  |  |  |  |
Павлов       |  |4 |  |5 |5 |  |  |  |  |
Панкратов    |  |  |  |  |  |  |  |  |  |
Сидорчук     | 5| 4| 5| 5| 5|  | 5|  | 5|
Тихонов      |3 |5 |5 |5 |5 |  |5 |  |5 |
Терехов      |  | 4|  |  |  |  |  |  |  |
-------------+--+--+--+--+--+--+--+--+--+
Бажанов      |3 |  |  |  |  |  |  |  |  |
Гудков       |  |  |  |  |  |  |  |  |  |
Лебедев      |  |  |  |  |  |  |  |  |  |
Меркулов     |  |  |  |  |  |  |  |  |  |
Нефф         |  |  |  |  |  |  |  |  |  |
Савченко     |  |  |  |  |  |  |  |  |  |
Сахин        |3 |4 |5 |5 |5 |  |  |  |  |
Старовойтов  | 3| 4| 5| 5| 5|  |  |  |  |
Ческис       |  |  |  |  |  |  |  |  |  |
-------------+--+--+--+--+--+--+--+--+--+
Герасимов    |4 |5 |5 |5 |5 |5 |5 |  |5 |
Дзебоев      |  |  |  |  |  |  |  |  |  |
Матафонов    |  |  |  |  |  |  |  |  |  |
Мирзоев      |  |  |  |  |  |  |  |  |  |
Никульшин    |  |  |  |  |  |  |  |  |  |
Потошин      | 5| 5|  | 5|  |  |  |  |  |
Рябых        |4 |4 |5 |5 |5 |5 |  |  |5-|
Ходаков      |  |  |  |  |  |  |  |  |  |
Хоронский    |  |  |  |  |  |  |  |  |  |
Цветков      | 5| 4| 5| 5| 5| 5|  |  | 5|
-------------+--+--+--+--+--+--+--+--+--+
Задание:     |24|25|26|27|28|29|30|31|X1|
~~~~~~~~~~~~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+

Расшифровка номеров заданий. 24: ls. 25: reversed file. 26: list sort. 27: Makefile. 28: метод Нью. 29: метод Эй. 30: ферзе-визуализация. 31: методы Ад-Ба.

Используя методы Адамса-Башфорта третьего и четвёртого порядков, численно проинтегрировать следующие задачи:

• математический маятник: тело на нити длины l в поле тяжести в предположении малости амплитуды колебаний или тело на пружине, сила которой следует закону Гука. Параметр задачи — частота колебаний; роль координаты играет либо угол нити с вертикалью, либо отклонение тела;
• линейная RLC-цепочка, у которой в контуре в начальный момент времени известны заряд конденсатора и ток (это, скажем, реализуется выключением в этот момент из контура бывшего в нём ЭДС; но для этой задачи выбор конкретного механизма возникновения начальных условий не принципиален). Параметры задачи — R, L и С; роль координаты играет заряд.

Сравнить результаты обоих методов с точными решениями. Проверить оценку зависимости погрешности от длины шага по времени. Реализовать вычисления при различных (задаваемых) начальных условиях. Для каждой из задач нарисовать следующие зависимости (для обоих методов и точных ответов; три кривых разного цвета для каждой):

1. координаты от времени;
2. производной координаты от времени;
3. производной координаты от координаты (график параметрический, называется фазовым портретом);
4. полной энергии от времени.

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

Размер (в пикселах) квадрата доски задаётся в командной строке наряду с количеством ферзей N.

Используя методы Эйлера («просто раскроем производную») и метод Адамса (второго порядка, «три вторых минус одна вторая») численно проинтегрировать задачу о движении тела в однородном поле тяжести: бросок под заданным углом к горизонту и падение обратно на плоскость, перпендикулярную силе тяжести).

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

Сделать программу, использующую метод Ньютона для нахождения решений уравнения f(x) = 0; процедуры вычисления функции и её производной в заданной точке реализуются аналитически (численного дифференцирования не нужно).

В программе необходимо предусмотреть выбор одной из как минимум трёх различных (и не слишком тривиальных) функций. Основной алгоритм метода Ньютона принимает на вход указатели на функции вычисления f(x) и f′(x), являясь полностью общим для любых используемых функций.

Оборудовать любую (на ваш выбор) из сданных программ Makefile, поддерживающим как минимум следующие стандартные цели:

• all: собирает программу;
• clean: вычищает все промежуточные и исполняемые объекты, оставляя только файлы, необходимые для «чистой» сборки.

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

Реализовать программу, принимающую на вход список имён файлов (или объектов, похожих на файл: для которых работает fopen()) и выводящую все строки каждого из (существующих) файлов в обратном порядке. То есть отдельные строки выводятся так, как они были записаны в файле, но порядок следования строк — обратный.

Для хранения набора строк в памяти воспользоваться связным списком. Работоспособность fseek() для любого из обрабатываемых файлов не предполагать.

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

~~~~~~~~~~~~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+
Задание:     |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| 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| 3|
Меркулов     | 4| 5| 5|  |  | 3| 3| 5|  |  |  |  | 3|  |  |  |  |
Нефф         |5 |5 |5 |5 |  |5 |4 |5 |3 |  |  |4 |3 |  |  |  |  |
Савченко     | 3| 5| 3| 3| 3|  | 3| 3|  | 3|  | 5| 3|  | 3| 3| 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 |3 |3 |3 |5 |3 |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  |3 |  |  |3 |3 |3 |  |  |2|
Гудков       |  |   |   |   |  |  |  |  |  |  |  |  |0|
Лебедев      |3 |3  |3  |3  |4 |  |3 |  |  |3 |3 |  |1|
Меркулов     |  |  3|  3|  3| 4|  |  |  |  |  |  |  |1|
Нефф         |  |5  |5  |5  |  |  |  |  |  |  |  |  |1|
Савченко     |  |  4|  4|  4| 3|  |  |  |  |  |  |  |1|
Сахин        |3 |5  |5  |5  |3 |3 |3 |3 |3 |3 |3 |  |2|
Старовойтов  | 3|  5|  5|  5| 4| 3| 5| 5| 5| 5| 3|  |3|
Ческис       |3 |4  |4  |4  |4 |5 |5 |5 |5 |5 |5 |  |5|
Шильников    |  |   |   |   |  |  |  |  |  |  |  |  |0|
-------------+--+---+---+---+--+--+--+--+--+--+--+--+-+
Герасимов    |3 |4  |5  |5  |5 |3 |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 |3 |3 |5 |5 |3 |  |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: частота.

• 18.12.2020: задание #1 [5 ≤ 29.01.2021, 4 ≤ 05.02.2021] решение кубического уравнения.
• 25.12.2020: задание #2 [5 ≤ 05.02.2021, 4 ≤ 12.02.2021] количества выборок.
• 25.12.2020: задание #3 [5 ≤ 05.02.2021, 4 ≤ 12.02.2021] посчитаем π в первый раз.
• 29.01.2021: задание #4 [5 ≤ 12.02.2021, 4 ≤ 19.02.2021] поиск нуля функции, Больцано + Коши = ?.
• 09.02.2021: задание #5 [5 ≤ 05.03.2021, 4 ≤ 12.03.2021] пол площади круга.
• 19.02.2021: задание #6 [5 ≤ 12.03.2021, 4 ≤ 19.03.2021] НОК/НОД.
• 02.03.2021: задание #7 [5 ≤ 19.03.2021, 4 ≤ 26.03.2021] статистический анализ данных.
• 05.03.2021: задание #8 [5 ≤ 19.03.2021, 4 ≤ 26.03.2021] сортировки подсчётом и вставкой.
• 09.03.2021: не задание, но десятиминутка
• 09.03.2021: задание #9 [5 ≤ 26.03.2021, 4 ≤ 02.04.2021] сортировка «пузырьком» («затоплением»).
• 12.03.2021: задание #10 [5 ≤ 26.03.2021, 4 ≤ 02.04.2021] как размножаются кролики.
• 16.03.2021: задание #11 [5 ≤ 02.04.2021, 4 ≤ 16.04.2021] быстрая сортировка.
• 23.03.2021: задание #12 [5 ≤ 16.04.2021, 4 ≤ 27.04.2021] строковые операции.
• 23.03.2021: задание #13 [5 ≤ 16.04.2021, 4 ≤ 27.04.2021] палиндромы.
• 23.03.2021: задание #14 [5 ≤ 16.04.2021, 4 ≤ 27.04.2021] %d?.
• 26.03.2021: задание #15 [5 ≤ 16.04.2021, 4 ≤ 27.04.2021] сортировка строк.
• 02.04.2021: задание #16 [5 ≤ 27.04.2021, 4 ≤ 14.05.2021] заполнения прямоугольника
• 16.04.2021: задание #17 [5 ≤ 14.05.2021, 4 ≤ 18.05.2021] sizeof.
• 16.04.2021: задание #18 [5 ≤ 14.05.2021, 4 ≤ 18.05.2021] битовые операции.
• 27.04.2021: задание #19 [5 ≤ 18.05.2021, 4 ≤ 25.05.2021] расстановка ферзей.
• 27.04.2021: задание #20 [5 ≤ 18.05.2021, 4 ≤ 25.05.2021] обход доски конём.
• 14.05.2021: задание #21 [5 ≤ 25.05.2021, 4 ≤ MM.DD.YYYY] шифр Цезаря.
• 14.05.2021: задание #22 [5 ≤ 25.05.2021, 4 ≤ MM.DD.YYYY] XOR-кодирование.
• 18.05.2021: задание #23 частота символов.

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

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

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

• режим работы: cipher, decipher;
• ключевое слово;
• входной файл;
• выходной файл.

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

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

• режим работы: cipher, decipher;
• величина сдвига;
• входной файл;
• выходной файл.

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

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

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

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

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

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

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

Поясняющая картинка:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• минимальное значение,
• максимальное значение,
• среднее значение,
• полусумму максимального и минимального,
• стандартное отклонение (среднее квадрата отклонения от среднего значения, найденного ранее).

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

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

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

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

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

Необходимо написать программу, которая методом «зажатия» области расположения какого-либо корня уравнения f(x) = 0, в окрестности этого самого корня x₀: |x₀ - 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(x²)/[x⁴ + 1], в отличие от f(x) = 0, является более-менее нетривиальной. Определением непрерывной функции хорошо бы тоже владеть (знать + уметь пользоваться).

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

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

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

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

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

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

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