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

Полезные ссылки:

• Список обучающихся
• Мини-руководство по SSH

~~~~~~~~~~~~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+
Задание:     |01|02|03|04|05|06|07|08|09|
Ученик ------+--+--+--+--+--+--+--+--+--+
Баландин     | +| +| +| +|  | +| +| +|  |
Бельков      |  |+ |+ |+ |  |  |+ |+ |  |
Бланков      | +| +| +| +|  |  |  |  |  |
Боровских    |+ |+ |+ |+ |  |  |  |  |  |
Гречин       | +| +| +| +|  |  |  |  |  |
Давыдов      |  |  |  |  |  |  |  |  |  |
Зотов        | +|  |  | +|  |  | +|  |  |
Ключников    |+ |+ |+ |+ |  |  |  |+ |  |
Мягких       | +| +| +| +|  |  |  |  |  |
Нечепоренко  |+ |+ |+ |+ |+ |  |+ |  |  |
Решетников   |  |  |  |  |  |  |  |  |  |
Прокофьева   |+ |+ |+ |+ |  |  |  |  |  |
Шевченко     |  |  | +| +|  |  |  |  |  |
Якушков      |+ |  |+ |+ |  |  |  |  |  |
-------------+--+--+--+--+--+--+--+--+--+
Антонов      |  |  |  |  |  |  |  |  |  |
Аушев        |+ |+ |+ |+ |  |+ |+ |+ |+ |
Белов        | +|  | +| +|  |  |  |  |  |
Громова      |+ |+ |+ |+ |+ |+ |+ |+ |  |
Карбышев     | +| +| +| +|  | +|  |  |  |
Картушин     |+ |+ |+ |+ |  |  |  |  |  |
Климов       |  |  |  |  |  |  |  |  |  |
Коваленко    |  |  |  |  |  |  |  |  |  |
Кодинцев     | +| +|  | +|  | +|  |  |  |
Королёв      |  |  |  |  |  |  |  |  |  |
Краснова     | +| +| +| +|  |  |  |  |  |
Линьков      |+ |+ |+ |+ |+ |  |  |  |  |
Пименов      | +|  | +| +| +|  |  |  |  |
Чернев       |+ |+ |  |+ |  |  |  |  |  |
-------------+--+--+--+--+--+--+--+--+--+
Задание:     |01|02|03|04|05|06|07|08|09|
~~~~~~~~~~~~~+~~+~~+~~+~~+~~+~~+~~+~~+~~+

Расшифровка номеров заданий. 01: возвратное уравнение. 02: подсчёт. 03: вставка. 04: пузырёк. 05: Lomuto vs Hoare. 06: merge sort. 07: угадай-K. 08: системы счисления. 09: палиндромы.

Формулировки заданий

Написать программу, которой на вход с клавиатуры вводится 5 коэффициентов многочлена степени 4. Программа должна определять, является ли этот многочлен возвратным (имеющим вид p(x) = Ax⁴ + Bx³ + Cx² + λBx + λ²A), и коли это так, находить (вещественные, хотя можно и комплексные) решения уравнения p(x) = 0.

Написать программу, сортирующую вводимый с клавиатуры массив методом подсчёта (количества элементов, сравнимых с данным).

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

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

Как мы выяснили, характерные для быстрой сортировки алгоритмы разделения (partition) Хоара и Ломуто отличаются в два раза по количеству операций сравнения. Поэтому хотелось бы понять, реализации быстрой сортировки, использующие эти алгоритмы, действительно отличаются по быстродействию в два раза или это не так?

Из обсуждавшегося также следует, что асимптотика N*log(N) для быстрой сортировки достигается лишь в среднем, деградируя до N² при некоторых входных данных; при этом «деградантные множества» различных алгоритмов и реализаций не обязаны совпадать.

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

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

Написать программу, которая на отрезке [a, b] ищет целое число, задуманное пользователем, задавая вопросы, на которые пользователь отвечает yes/no. Если пользователь вводит «quit», программа завершается. Ответы пользователя могут быть в любом регистре букв (скажем, «yEs» вполне может встретиться).

Значения a и b пользователь вводит сначала самостоятельно. Программа должна работать оптимально. Пользоваться библиотечными функциями для работы с символами/строками (кроме scanf()/getchar()) запрещается.

Пользователь вводит целое неотрицательное число (в десятичной системе счисления) и основание системы счисления p (2≤p≤36). Программа выводит введённое пользователем число в p-ичной системе счисления. Использовать массивы и библиотечные функции по преобразованию/выводу чисел в произвольных системах счисления запрещается.

Написать программу, распознающую палиндромы среди

1. (последовательно) всех своих аргументов командной строки;
2. конкатенации всех аргументов командной строки.

Запрещается использовать стандартные функции из набора ctype/string (необходимые для этой программы части несложно реализовать самостоятельно).

Всё прочее

В остальном —