Постановка задачи
1) Разработать и реализовать алгоритм, который будет искать 3-й минимум и 4-й максимум в массиве, размер которого определяется пользователем (но не более 100).Реализовать следующим образом:
1. Ввод количества элементов
2. Ввод элементов массива
3. Сортировка массива
4. Копирование отсортированного массива в другой, исключая повторяющиеся элементы.
5. Вывод искомых минимумов и максимумов, если они есть с помощью второго массива.
2) Разработать и реализовать программу, которая будет сортировать массив алгоритмом быстрой сортировки.
Блок схема функции определе ния Блок схема функции ввода и про-
Режима заполнения массива верки числа на правильность
Блок схема функции ввода и проверки числа размера массива и поиска максимума и минимума
Блок схема функции быстрой сортировки
Блок схема программы:
Реализация программы на языке Python 3.6
import random # Для случайного заполнения массива
import copy # для копирования массива
def auto(): # Отвечает за режим заполнения массива
x = input('Режим заполнения автомат(0)/Ручной(1)')
if x == '1':
return int(1)
elif x == '0':
return int(0)
else:
print("Неверное значение, попробуйте снова")
return auto()
def start(k = 1, n = 0): # Ввод и проверка чисел для размера массива и поиска
if k == 0: # минимума и максимума
print("Какая длинна массива? ")
elif k == 1:
print("\n", "Какое M-е минимальное число ищем?")
elif k == 2:
print("\n", "Какое N-е максимальное число ищем?")
x = newtypes()
if x > 0 and x <= 100 and k == 0:
return x
elif (x > 0 and x <= n) and (k == 1 or k == 2):
return x - 1
else: #Допустим, что нужен первый минимум, а он с 0-ым индексом
print("Неверное значение, попробуйте снова")
return start(k, n)
def sort(array): # Быстрая сортировка
less = []
equal = []
greater = []
if len(array) > 1:
pivot = array[0]
for i in array:
if i < pivot:
less.append(i)
if i == pivot:
equal.append(i)
if i > pivot:
greater.append(i)
return sort(less)+equal+sort(greater)
else: # Если всего один элемент, то просто вернём его
return array
def newtypes(): # Для ввода и проверки числа
x = input("Введите число: ")
try: # Обработка исключений
return int(x)
except ValueError:
print("Ошибка, повторите корректный ввод")
return(newtypes())
a = [] # Массив для записи с клавиатуры и удаления дубликатов
bub = [] # Соритровка Пузырьком
qu = [] # Быстрая сортировка
temp = 0 # Для сортировки пузырьком
n = start(0) # Отвечает за размер массива
k = auto() # Режим заполнение массива
if k == 1: # Ручной труд
for i in range(n):
i = newtypes() # Ввод и проверка на правильность
a.append(i) # Добавление в массив
elif k == 0: # Автоматика
for i in range(n):
a.append(random.randint(0, 100)) #Случайное число
for i in a: # Удаление повторных вхождений
while a.count(i)!= 1: # Если кол-во вхождений элемента…
a.remove(i) # Удаление первого вхождения элемента в массиве
print("Массив без повторений") # Вывод мссива без повторов
for i in a:
print(i, end=' ') # Пробел как разделитель
bub = copy.copy(a) # Независимая КОПИЯ массива Пузырьком сорт
qu = copy.copy(a) #Быстрая сорт
qu = sort(qu) # Фун-я быстрой сортроовки
# Сортировка Пузыриком по возрастанию
for i in range(len(bub)):
for j in range(len(bub) - 1, i, -1): # от n-1 до i с шагом -1
if bub[j] < bub[j-1]: # len(bub) – длинна массива
bub[j], bub[j - 1] = bub[j - 1], bub[j] # Меняет местами два элемента
print("\n", "Сортировка Пузырьком: ") # Вывод на экран отсортированныхмассивов
for i in bub:
print(i, end=' ')
print("\n", "Быстрая сортировка: ")
for i in qu:
print(i, end=' ')
n = start(1, len(a)) # Ввод и проверка номера MIN значения
print(n+1, "-й минимум равен: ", bub[n])
bub.reverse() # Переворачиваем массив, [4, 1, 6, 0, 3] à [3, 0, 6, 1, 4]
# Что бы не париться с индексами, тк массив был отсортирован по #возрастанию, но теперь он отсортирован по убыванию, те 1-й максимум на 0-м месте
m = start(2, len(a)) # MAX значение
print(m+1, "-й максимум равен: ", bub[m])
Пример работы программы
Вывод
Выполняя лабораторную №16, я научился использовать и реализовывать алгоритмы сортировки, повторил основы языка Python 3.6 и конструкцию исключения ошибок Try-Except. Готовый результат может исключать одинаковые элементы первоначального массива, создавая второй массив и передавая туда неповторяющиеся элементы первого. Также выводить M-й минимум и N-й максимум нового массива, если массив соответствует требованиям.
Используемые источники:
• pythontutor.ru
• pythonworld.ru
• ru.wikibooks.org
• msdn.microsoft.com
• ru.stackoverflow.com