мета-данные страницы
Это старая версия документа!
Задачи на Январь-Февраль 2020
Занятие 1
Задача №1
Написать программу, которая
- Элемент нумерованного спискасчитывает кодировку из произвольного алфавита А, который является подмножеством латинского (английского), в алфавит Х, который также является подмножеством латинского (английского),
- Элемент нумерованного спискаполучает сообщение в алфавите А
- Элемент нумерованного спискавыводит закодированное указанной кодировкой сообщение
Задача №2
Задача №3
Занятие 2
На этом занятии входящий алфавит – некоторое подмножество латинского, выходной – 0 и 1.
Задача №1
Входящий алфавит А состоит из n первых букв латинского (английского) алфавита.
По числу n, количеству входящих букв, выдать кодировку, удовлетворяющую критерию Фано
Задача №2
Входящий алфавит А состоит из n букв латинского (английского) алфавита.
Кодировка некоторых букв уже задана. Выдать кодировку для всех букв, удовлетворяющую критерию Фано.
Задача №3
Входящий алфавит А состоит из n букв латинского (английского) алфавита.
Известно слово S в алфавите А, которое мы хотим передать. Предложить кодировку в выходящем алфавите {0, 1}, в которой выходящее сообщение самое короткое.
Занятие 3
Задача №1
Для какого имени ложно высказывание:
Первая буква гласная \/ Четвертая буква согласная?
1) Петр
2) Алексей
3) Наталья
4) Елена
Задача №2
Для какого имени ложно высказывание:
(Первая буква имени гласная → Четвертая буква имени согласная).
1) ЕЛЕНА
2) ВАДИМ
3) АНТОН
4) ФЕДОР
Продолжение следует…
Задачи на октябрь 2019
Задача №1
Имеется набор данных, состоящий из пар положительных целых чисел.
Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.
Задача №2
На вход программы поступает последовательность из N целых положительных чисел. Все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен).
Необходимо определить количество пар, для которых произведение элементов делится на 26.
Задача №3
На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4 (разница в индексах элементов пары должна быть 4 или более, порядок элементов в паре неважен).
Необходимо определить количество таких пар, для которых произведение элементов делится на 29.
Задача №4
На вход программы поступают целое число К (0 < К < 10) и последовательность из N целых положительных чисел. Все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен).
Необходимо определить такую пару элементов, что их сумма делится на К и она максимальна среди таких сумм.
З.Ы.
Поскольку предполагается, что N достаточно велико, то Тупой Перебор допустим, но снижает оценку.
Задачи на Ноябрь-Декабрь 2019
Если не указано иное, графы считаются простыми, невзвешенными и неориентированными.
Задача №1
Ввести граф по диаграме (картинке).
Написать программу, определяющую путь между указанными вершинами взвешенного графа, либо его отсутствие.
Оценивание
30 баллов – иногда ошибается
40 баллов – находит путь, но не кратчайший
50 баллов – всегда находит кратчайший путь.
Задача №2
Ввести граф по диаграмме (картинке).
Написать программу, определяющую путь между указанными вершинами орграфа, либо его отсутствие.
Оценивание
30 баллов – иногда ошибается
40 баллов – находит путь, но не кратчайший
50 баллов – всегда находит кратчайший путь.
Задача №3
Программа получает граф в виде файла со списком смежности в формате:
Буква вершины по порядку <пробел> список инцендентных вершин через пробелы <конец строки>.
Данные могут быть повреждены –
Оценивание
30 баллов – может определить число компонент связности в корректноом списке
40 баллов – может определить число компонент связности или некорректность данных
50 баллов – выводит в виде списка все компоненты связности
Задача №4
Программа получает взвешенный граф в виде файла с матрицей смежности.
Построить его минимальное остовное дерево, т.е вывести его матрицу смежности, либо предупредить о несвязности графа.
Оценивание
30 баллов – иногда ошибается
40 баллов – строит, но не минимальное
50 баллов – строит минимальное.