Лабораторная №4
.docxМинистерство цифрового развития, связи и массовых коммуникаций Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего образования
«Московский технический университет связи и информатики»
Кафедра «Математическая кибернетика и информационные технологии»
Лабораторная работа №4
по дисциплине «Структуры и алгоритмы обработки данных»
Проверил:
Чайка А.Д.
Москва 2022
Содержание
3.1. Задача 1 4
3.2. Задача 2. 6
3.3. Задача 3. 8
3.4. Задача 4. 9
3.5. Задача 5. 10
3.6. Задача 6. 11
3.7. Задача 7. 12
3.8. Задача 8. 13
1. Цель работы: Изучить реализацию стеков и деков на языке python, организовать чтение и запись информации в .txt файл.
2. Задание:
Отсортировать строки файла, содержащие названия книг, в алфавитном порядке с использованием двух деков.
Дан текстовый файл, содержащий зашифрованное сообщение. Пользуясь деком, расшифровать текст.
Задача на пирамидки
Дан текстовый файл с программой на алгоритмическом языке. За один просмотр файла проверить баланс круглых скобок в тексте, используя стек.
Дан текстовый файл с программой на алгоритмическом языке. За один просмотр файла проверить баланс квадратных скобок в тексте, используя дек.
Дан файл из символов. Используя стек, за один просмотр файла напечатать сначала все цифры, затем все буквы, и, наконец, все остальные символы, сохраняя исходный порядок в каждой группе символов.
Дан файл из целых чисел. Используя дек, за один просмотр файла напечатать сначала все отрицательные числа, затем все положительные числа, сохраняя исходный порядок в каждой группе.
Дан текстовый файл. Используя стек, сформировать новый текстовый файл, содержащий строки исходного файла, записанные в обратном порядке: первая строка становится последней, вторая – предпоследней и т.д.
3. Ход выполнения лабораторной работы
3.1. Задача 1
Отсортировать строки файла, содержащие названия книг, в алфавитном порядке с использованием двух деков.
Код решения задачи представлен на рисунке 1. Результат работы представлен на рисунке 2.
Рисунок 1 – Код решения первой задачи
Рисунок 2 – Результат работы кода
3.2. Задача 2.
Дек содержит последовательность символов для шифровки сообщений. Дан текстовый файл, содержащий зашифрованное сообщение. Пользуясь деком, расшифровать текст.
Известно, что при шифровке каждый символ сообщения заменялся следующим за ним в деке по часовой стрелке через один.
Код решения задачи представлен на рисунке 3. Результат работы представлен на рисунке 4.
Рисунок 3 – Код решения второй задачи
Рисунок 4 – Результат работы кода
3.3. Задача 3.
Даны три стержня и n дисков различного размера. Диски можно надевать на стержни, образуя из них башни. Перенести n дисков со стержня А на стержень С, сохранив их первоначальный порядок. При переносе дисков необходимо соблюдать следующие правила:
- на каждом шаге со стержня на стержень переносить только один диск;
- диск нельзя помещать на диск меньшего размера;
- для промежуточного хранения можно использовать стержень В.
Реализовать алгоритм, используя три стека вместо стержней А, В, С. Информация о дисках хранится в исходном файле.
Код решения задачи представлен на рисунке 5. Результат работы представлен на рисунке 6.
Рисунок 5 – Код решения задачи
Рисунок 6 – Результат работы кода
3.4. Задача 4.
Дан текстовый файл с программой на алгоритмическом языке. За один просмотр файла проверить баланс круглых скобок в тексте, используя стек.
Код решения задачи представлен на рисунке 7. Результат работы представлен на рисунке 8.
Рисунок 7 – Код решения задачи
Рисунок 8 – Результат работы кода
3.5. Задача 5.
Дан текстовый файл с программой на алгоритмическом языке. За один просмотр файла проверить баланс квадратных скобок в тексте, используя стек.
Код решения задачи представлен на рисунке 9. Результат работы представлен на рисунке 10.
Рисунок 9 – Код решения задачи
Рисунок 10 – Результат работы кода
3.6. Задача 6.
Дан файл из символов. Используя стек, за один просмотр файла напечатать сначала все цифры, затем все буквы, и, наконец, все остальные символы, сохраняя исходный порядок в каждой группе символов.
Код решения задачи представлен на рисунке 11. Результат работы представлен на рисунке 12.
Рисунок 11 – Код решения задачи
Рисунок 12 – Результат работы кода
3.7. Задача 7.
Дан файл из целых чисел. Используя дек, за один просмотр файла напечатать сначала все отрицательные числа, затем все положительные числа, сохраняя исходный порядок в каждой группе.
Код решения задачи представлен на рисунке 13. Результат работы представлен на рисунке 14.
Рисунок 13 – Код решения задачи
Рисунок 14 – Результат работы кода
3.8. Задача 8.
Дан текстовый файл. Используя стек, сформировать новый текстовый файл, содержащий строки исходного файла, записанные в обратном порядке: первая строка становится последней, вторая – предпоследней и т.д.
Код решения задачи представлен на рисунке 15. Результат работы представлен на рисунке 16.
Рисунок 15 – Код решения задачи
Рисунок 16 – Результат работы кода
4. Вывод
Я изучила реализацию стеков и деков на языке python, организовала чтение и запись информации в .txt файл.