Перечень практических заданий к экзаменационным билетам

Перечень вопросов к экзаменационным билетам

1. Понятие алгоритма. Свойства, способы записи алгоритмов. Базовые алгоритмические структуры: композиция, альтернатива, итерация. Этапы решения задач на ЭВМ. Подходы к формализации понятия «алгоритм».

2. Свойство универсальности алгоритма. Общий вид команды ветвления на алгоритмическом языке и в блок-схеме. Структурная команда ветвления. Структура вложенных ветвлений.

3. Алгоритм циклической структуры. Понятие итерации. Тело цикла. Шаг цикла. Команда цикла с предусловием. Использование цикла с предусловием в задачах. Команда цикла с постусловием. Использование цикла с постусловием в задачах. Команда цикла со счетчиком. Использование цикла со счетчиком в задачах.

4. Формализация понятия алгоритма в теории автоматов на примере машин Поста. Понятие машины Поста. Команды машины Поста. Программа для машины Поста. Примеры программ.

5. Формализация понятия алгоритма в теории автоматов на примере машин Тьюринга. Понятие машины Тьюринга. Команды машины Тьюринга. Программа для машины Тьюринга. Примеры программ.

6. Понятия основного и вспомогательного алгоритмов. Понятие процедуры. Обращение к вспомогательному алгоритму и процедуре из основного алгоритма. Фактические и формальные параметры. Правила соответствия между фактическими и формальными параметрами. Примеры.

7. Этапы изготовления программного продукта. Сложный алгоритм. Способы соединения базовых алгоритмических структур. Глубина вложенности структур.

8. Стандарты изображения блок-схем алгоритмов. Наглядность построения программ. Декомпозиция задачи.

9. Способы построения алгоритма: метод последовательной детализации и сборочный метод. Отладка и тестирование алгоритма.

10. Понятие рекурсии. Прямая и косвенная рекурсия. Рекурсивные вспомогательные алгоритмы. Примеры.

11. Проблема поиска информации. Критерий поиска. Методы полного перебора и перебора без повторений.

12. Проблема поиска информации. Критерий поиска. Метод перебора с возвратом. Задача «Поиск выхода из лабиринта».

13. Последовательный поиск в неупорядоченном массиве: алгоритм последовательного поиска в неупорядоченном массиве, алгоритм поиска минимального элемента в неупорядоченном массиве, эффективный алгоритм поиска в неупорядоченном массиве максимального и минимального элементов одновременно.

14. Алгоритм бинарного поиска в упорядоченном массиве.

15. Понятие сложности алгоритма. Временная сложность. Теоретическая сложность: линейная, квадратичная, кубическая. Эффективность алгоритма.

16. Алгоритм обменной сортировки методом «пузырька». Сортировка выбором.

17. Сортировка вставками. Понятие сортировки данных в массивах.

18. Сортировка слиянием. Понятие сортировки данных в массивах.

19. Понятие сортировки данных в массивах. Сортировка простым включением.

20. Алгоритм быстрой сортировки. Оценка сложности алгоритмов сортировки.

Перечень практических заданий к экзаменационным билетам

1. Составить алгоритм нахождения НОД двух чисел. С помощью этого алгоритма найти НОД (121, 15).
2. Составить алгоритм нахождения НОК двух чисел. С помощью этого алгоритма найти НОК (12, 64).

3. Дано трехзначное число. Составить алгоритм, с помощью которого можно определить кратна ли шести сумма его цифр.

4. Дано трехзначное число. Составить алгоритм, с помощью которого можно определить оканчивается ли это число цифрой 5.

5. Дано трехзначное число. Составить алгоритм, с помощью которого можно определить входят ли в это число цифры 6 и 7.

6. Дано трехзначное число. Составить алгоритм, с помощью которого можно определить больше ли цифра десятков цифры единиц.

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

8. Дано четырехзначное число. Составить алгоритм определения больше ли цифра сотен цифры единиц.

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

10. Даны три вещественных числа a,b,c. Составьте алгоритм, определяющий, могут ли данные числа являться длинами сторон равностороннего треугольника.

11. Дана точка с координатами (x,y), требуется составить алгоритм, определяющий принадлежность точки отрезку четвертям координатной плоскости.

12. Дана точка с координатами (x,y), определите, принадлежит ли точка осям координат. Составьте алгоритм.

13. Дано натуральное число n. Требуется составить алгоритм для подсчёта количества цифр данного числа.

14. Составить алгоритм для вывода всех квадратов натуральных чисел, не превосходящих данного числа N.

1. Составить алгоритм, который определяет максимальное число из последовательности положительных чисел (длина последовательности не ограничена).
2. Дано число. Найти сумму и произведение его цифр. Составить алгоритм.
3. Составить алгоритм, вычисляющий произведение положительных четных чисел до N.
4. Дано целое число N > 0. С помощью операций деления нацело и взятия остатка от деления определить, имеется ли в записи числа N цифра «2». Если имеется, то вывести True, если нет — вывести False. Составить алгоритм.

19. Дано n вещественных чисел. Найти их среднее арифметическое. Составить алгоритм.

1. Дано число. Найти количество его цифр. Составить алгоритм.
2. Дано натуральное число n. Вычислить:

S = 1! + 2! + 3! + … + n! (n>1). Составить циклический алгоритм.

1. Даны два целых числа A и B (A < B). Найти сумму квадратов всех целых чисел от A до B включительно. Составить алгоритм, используя цикл со счётчиком.
2. Дано целое число N> 0. Найти сумму 1 + 1/2 + 1/3 + … + 1/N. Составить алгоритм, используя цикл со счётчиком.
3. Даны целые числа K и N (N > 0). Вывести N раз число K. алгоритм, используя цикл со счётчиком.

25. Составить машину Поста. На ленте задан массив меток. Увеличить длину массива на 3 метки. Каретка находится либо слева от массива, либо над одной из ячеек самого массива. (увеличение числа на 3).

1. Составить машину Поста. Даны два массива меток, которые находятся на некотором расстоянии друг от друга. Требуется соединить их в один массив. Каретка находится над крайней левой меткой первого массива. (сложение двух чисел)
2. Составить машину Поста. На ленте задана последовательность массивов, включающая в себя один и более массивов. При этом два соседних массива отделены друг от друга одной пустой ячейкой. Необходимо на ленте оставить один массив длиной равной сумме длин массивов, присутствовавших изначально. Каретка находится над крайней левой меткой первого (левого) массива.
3. Составить машину Поста. На ленте машины Поста расположено n массивов меток, отделенных друг от друга свободной ячейкой. Каретка находится над крайней левой меткой первого массива. Определить количество массивов.
4. Составить машину Поста. Дано несколько массивов меток. Удалить четные массивы. Каретка находится над первым массивом.
5. Составить машину Тьюринга. Составить алгоритм, прибавляющий единицу к последней цифре заданного числа, расположенного на ленте. Входные данные – слово – цифры целого десятичного числа, записанные в последовательные ячейки на ленту. В первоначальный момент устройство располагается напротив самого правого символа – цифры числа.
6. Составить машину Тьюринга. На ленте машины Тьюринга содержится последовательность символов “*”. Напишите программу для машины Тьюринга, которая каждый второй символ “*” заменит на “@”. Замена начинается с правого конца последовательности. Автомат в состоянии q ₁ обозревает один из символов указанной последовательности. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
7. Дано натуральное число n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1, при этом в выходном слове старшая цифра не должна быть 0. Например, если входным словом было “100”, то выходным словом должно быть “99”, а не “099”. Автомат в состоянии q ₁ обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
8. На ленте машины Тьюринга находится число, записанное в десятичной системе счисления. Умножить это число на 2. Автомат в состоянии q ₁ обозревает крайнюю левую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
9. Составить машину Тьюринга. Прибавление единицы для целых чисел в пятеричной системе счисления.
10. Описать вспомогательный алгоритм TrianglePS (a, P, S), вычисляющий по стороне a равностороннего треугольника его периметр P и площадь S. (a — входной, P и S — выходные параметры; все параметры являются вещественными). С помощью этого вспомогательного алгоритма найти периметры и площади пяти равносторонних треугольников с данными сторонами. Основной алгоритм составить в виде циклического.
11. Описать вспомогательный алгоритм DigitCountSum(K, C, S), находящий количество C цифр целого положительного числа K, а также их сумму S (K — входной, C и S — выходные параметры целого типа). С помощью этого вспомогательного алгоритма найти количество и сумму цифр для каждого из десяти данных целых чисел.
12. Описать вспомогательный алгоритм Swap(X, Y), меняющий содержимое переменных X и Y (X и Y — вещественные параметры, являющиеся одновременно входными и выходными). С его помощью для данных переменных A, B, C, D последовательно поменять содержимое следующих пар: A и B, C и D, B и C и вывести новые значения A, B, C, D.
13. Описать рекурсивный алгоритм DigitSum(K), который находит сумму цифр целого числа K без использования цикла.
14. Вычислить сумму: , используя алгоритм вычисления факториала числа

40. В одномерном массиве X заданы координаты n точек, лежащих на вещественной числовой оси. Точки пронумерованы. Их номера соответствуют последовательности в массиве X. Требуется определить пару точек, расстояние между которыми наибольшее. Составить алгоритм поиска.

41. Дан линейный массив целых чисел осуществить сортировку четных элементов массива методом «пузырька».

42. Дан линейный массив целых чисел осуществить сортировку четных элементов массива методом простого выбора.

43. Дан линейный массив целых чисел осуществить сортировку четных элементов массива методом быстрой сортировки.

44. Дан линейный массив целых чисел осуществить сортировку элементов массива, записанных на нечетных местах, методом «пузырька».

45. Дан линейный массив целых чисел осуществить сортировку элементов массива, записанных на нечетных местах, методом быстрой сортировки.

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

47. Дан линейный массив целых чисел осуществить сортировку отрицательных элементов массива методом быстрой сортировки.

48. Дан линейный массив целых чисел осуществить сортировку отрицательных элементов массива методом «пузырька».

49. Дан линейный массив целых чисел осуществить сортировку отрицательных элементов массива методом простого выбора.

50. Дан линейный массив целых чисел осуществить сортировку положительных элементов массива методом «пузырька».

51. Дан линейный массив целых чисел осуществить сортировку положительных элементов массива методом простого выбора.

52. Дан линейный массив целых чисел осуществить сортировку положительных элементов массива методом быстрой сортировки.

1. В квадратной матрице размером 5х5, заполненной случайными целыми числами из диапазона (–45,+45) найти количество положительных элементов. Составить алгоритм.
2. В квадратной матрице размером 5х5, заполненной случайными целыми числами из диапазона (–40,+40) найти максимальный отрицательный элемент. Составить алгоритм.
3. В квадратной матрице размером 5х5, заполненной случайными целыми числами из диапазона (–40,+40) найти минимальный положительный элемент. Составить алгоритм.