2024
2023
2022
2021
2020
2019
2018
2017
Алгоритмы сортировки
(0.3 балла) Написать программу. Программа получает на вход файл, в котором в одну строку записаны числа через пробел (проверять соответствие файла формату не требуется). Программа сортирует массив алгоритмом быстрой сортировки и пишет элементы массива на экран в порядке возрастания.
(1 балл) Напишите программу. Программа получает на вход файл, в котором в одну строку записаны числа через пробел (проверять соответствие файла формату не требуется). Программа реализует сортировку двумя алгоритмами из списка: пузырьком, слиянием, быстрой сортировкой. Программа измеряет время для сортировки входного массива каждым из реализованных алгоритмов, проверяет, что обе сортировки выдали один и тот же результат, и пишет на экран отсортированный в порядке возрастания элементов массив и получившиеся времена работы. Для оценки времени используйте большие массивы (подберите размер массива так, чтобы была разница между разными алгоритмами сортировки!)
(1.2 балла) Напишите программу. Программа генерирует наборы входных массивов разной длины разными методами: полностью упорядоченный массив, массив, в котором только один элемент стоит не на месте, массив, состоящий из нескольких кусков, каждый из которых упорядочен, массив, в котором элементы идут примерно по возрастанию, – все те же методы для элементов по убыванию, и массив из полностью случайных элементов. Программа реализует сортировку тремя алгоритмами: пузырьком, слиянием, сортировкой. Программа генерирует каждым методом массивы длины 500, 1000, ... 100000 и для каждого типа массивов для каждой длины пишет время, которое требуется каждому алгоритму сортировки для того, чтобы отсортировать массив. Программа должна иметь параметры командной строки, которые позволяют выбирать диапазоны, в которых меняются длины массивов, выбирать типы массивов, алгоритмы сортировки.
Структуры данных
(0.3 балла) Написать программу, реализующую двусвязный список чисел. Реализовать процедуру добавления, удаления элемента из списка, а также поиска.
(0.7 балла) Написать процедуру сортировки двусвязного списка.
(1 балл) Написать программу, "переворачивающую" односвязный список за линейное время с постоянной памятью (первый элемент становится последним, второй - предпоследним и т.д.)
Подсказки
Для работы со временем в питоне есть модуль datetime. Пример работы с этим модулем:
1 from datetime import datetime
2 # класс datetime в модуле datetime можно использовать напрямую,
3 # но проще создавать объекты этого класса, используя функцию datetime.now()
4 t1 = datetime.now() # запоминаем нынешнее время в переменную t1
5 x = range(100500) # долго думаем
6 t2 = datetime.now() # время после того, как подумали
7 print t1 # печатаем время начала
8 print t2 # время конца
9 print t2 - t1 # печатаем разность между временем начала и конца