Лабораторная работа №3. Структуры и алгоритмы обработки данных. 2022

Лабораторная работа №3. Структуры и алгоритмы обработки данных. 2022


Задание 1
Реализовать методы поиска подстроки в строке. Добавить возможность ввода строки и подстроки с клавиатуры. Предусмотреть возможность существования пробела. Реализовать возможность выбора опции чувствительности или нечувствительности к регистру. Оценить время работы каждого алгоритма поиска и сравнить его со временем работы стандартной функции поиска, используемой в выбранном языке программирования.

Задание 2
Пятнашки - популярная головоломка, придуманная в 1878 году Ноем Чепмэном. Головоломка представляет собой набор из 15 одинаковых квадратных костяшек с нанесёнными на них числами, лежащих в квадратной коробке. Длина стороны коробки в четыре раза больше длины стороны костяшки, поэтому в коробке остаётся незаполненным одно квадратное поле. Цель игры - упорядочить костяшки по возрастанию номеров, перемещая их внутри коробки, желательно сделав как можно меньше перемещений.
Написать программу, определяющую, является ли данное расположение «решаемым», то есть можно ли из него за конечное число шагов перейти к правильному. Если это возможно, то необходимо найти хотя бы одно решение - последовательность движений, после которой числа будут расположены в правильном порядке.
Входные данные: массив чисел, представляющий собой расстановку в порядке «слева направо, сверху вниз». Число 0 обозначает пустое поле. Например, массив [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0] представляет собой «решенную» позицию элементов.
Выходные данные: если решения нет, то функция должна вернуть пустой массив []. Если решение есть, то необходимо представить решение — для каждого шага записывается номер передвигаемого на данном шаге элемента.


Вывод
В ходе лабораторной работы мы научились искать подстроку в строке, используя алгоритм Кнута-Морриса-Пратта и упрощенный алгоритм Бойера-Мура, а также реализовали возможность ввода строки и подстроки с клавиатуры и возможность выбора опции чувствительности или нечувствительности к регистру, предусмотрели возможность существования пробела, а также сравнили с работой встроенного поиска. Также реализовали известную игру Пятнашки.

2022