Примерный состав заданий:
1. Стеки и очереди - знать основные определения и алгоритмы (на описательном уровне), повторить процедуры и функции работы со стеком и очередью.
2. Строки - решение задачи на Паскале (можно за компьютером).
3. Графы - применение алгоритма Дейкстры для поиска кратчайшего пути.
4. Деревья - обход дерева, построение дерева арифметического выражения.
5. Динамическое программирование - задача о количестве решений.
Примерные задачи к пунктам 2 и 5:
Разобранные задания смотрим еще раз здесь и здесь.
Задачи по строкам.
В вузе проводится предварительное тестирование абитуриентов по двум предметам, по каждому предмету абитуриент может набрать от 0 до 100 баллов. При этом к сдаче экзаменов в первом потоке допускаются абитуриенты, набравшие по результатам тестирования не менее 30 баллов по каждому из двух предметов. На вход программы подаются сведения о результатах предварительного тестирования. Известно, что общее количество участников тестирования не превосходит 500.
В первой строке вводится количество абитуриентов, принимавших участие в
тестировании, N. Далее следуют N строк, имеющих следующий формат:
<Фамилия> <Имя> <Баллы>
Здесь
<Фамилия> – строка, состоящая
не более чем из 20 символов; <Имя>
– строка, состоящая не более чем из 15 символов; <Баллы> – строка, содержащая два целых числа, разделенных
пробелом, соответствующих баллам, полученным на тестировании по каждому из двух
предметов. При этом <Фамилия> и
<Имя>, <Имя> и <Баллы>
разделены одним пробелом. Примеры входных строк:
Ветров Роман 68 59
Анисимова Екатерина 64 88
Напишите
программу, которая будет выводить на экран фамилии и имена абитуриентов,
потерпевших неудачу, то есть не допущенных к сдаче экзаменов в первом потоке.
При этом фамилии должны выводиться в алфавитном порядке.
2) Напишите программу, которая выведет на экран лучший по сумме баллов результат.
Задачи динамического программирования.
1) У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 1
2. умножь на 4
Сколько есть программ, которые число 1 преобразуют в число 32? (15)
2) У исполнителя Калькулятор три команды, которым присвоены номера:
1. прибавь 1
2. умножь на 2
3. умножь на 3
Сколько есть программ, которые число 1 преобразуют в число 18? (96)
3) У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 1
2. увеличь число десятков на 1
Например: при помощи команды 2 число 23 преобразуется в 33. Если перед выполнением команды 2 вторая с конца цифра равна 9, она не изменяется.
Сколько есть программ, которые число 11 преобразуют в число 27? (8)
4) У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 1
2. увеличь каждый разряд числа на 1
Например, число 23 с помощью команды 2 превратится в 34, а 29 в 39 (так как младший разряд нельзя увеличить). Если перед выполнением команды 2 какая-либо цифра равна 9, она не изменяется. Сколько есть программ, которые число 24 преобразуют в число 46? (14)
5) У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 1
2. умножь на 1,5
Первая из них увеличивает на 1 число на экране, вторая увеличивает это число в 1,5 раза, если число чётное. К нечётным числам вторая команда неприменима. Сколько есть программ, которые число 1 преобразуют в число 20? (32)
Комментариев нет:
Отправить комментарий