Лабораторная работа № 4. Алгоритмы поиска
Перед началом работы, cкачайте файл с заданиями, выполняемыми без компьютера.
Теоретические сведения
Линейный поиск
Реализация линейного поиска подразумевает последовательный перебор элементов последовательности и проверку требуемого условия для каждого элемента. Мы можем искать конкретное значение или подходящее под любое другое условие - максимальное, минимальное, чётное, нечётное и т.д.
Алгоритм обязательно включает в себя цикл и ветвление.
Бинарный поиск
Алгоритма работает для отсортированных последовательностей. Суть алгоритма состоит в последовательном разделении области поиска и приближении к искомому значению путём деления последовательности пополам. Поиск продолжается в той половине в которой может находится значение, а другая половина последовательности отбрасывается.
Кликните по изображению, чтобы перейти к интерактивной визуализации бинарного поиска.
Блок-схема алгоритма показана на Рисунке 1.
Задания для самостоятельной работы
Задания обозначенные значком выполняются на распечатках или в тетради, обозначенные - на компьютере в среде программирования.
Задание 1. Заполнение списка с клавиатуры
Составьте программу для заполнения списка lst числами, вводимыми с клавиатуры. Количество элементов в списке n также вводится с клавиатуры. Выведите содержимое списка lst на экран.
Задание 2. Заполнение списка случайными числами
Составьте программу для заполнения списка lst случайными целыми числами из отрезка [-15, 15]. Количество элементов в списке n вводится с клавиатуры. Выведите содержимое списка lst на экран.
Для решения задачи необходимо импортировать функцию randint() из модуля random.
Задание 3. Линейный поиск (sam03.py)
С клавиатуры вводится количество элементов n в списке lst. Значения вводятся с клавиатуры и добавляются в список.
Используйте код из Задания 1 и следующий фрагмент блок-схемы для поиска индекса и значения элемента списка lst, который соответствует условию задачи вашего варианта.
В блоке, выделенном зелёным цветом, замените прочерк на необходимое условие.
Список lst заполняется числами.
Найти индекс и значение первого числа из списка, которое делится нацело на 9.
Список lst заполняется числами.
Найти индекс и значение первого числа из списка, которое больше последнего элемента списка lst.
Список lst заполняется числами.
Найти индекс и значение первого числа из списка, которое делится нацело на количество элементов в списке lst.
Список lst заполняется числами.
Найти индекс и значение первого числа из списка, которое меньше первого элемента списка lst.
Список lst заполняется числами.
Найти индекс и значение первого числа из списка, которое меньше первого элемента списка lst.
Список lst заполняется числами.
Найти индекс и значение первого числа из списка, которое после возведения в квадрат меньше количества элементов списка lst.
Список lst заполняется числами.
Найти индекс и значение первого числа из списка, которое не делится нацело на количество элементов в списке lst.
Список lst заполняется числами.
Найти индекс и значение первого числа из списка, которое делится нацело на 9.
Список lst заполняется числами.
Найти индекс и значение первого числа из списка, которое больше последнего элемента списка lst.
Список lst заполняется числами.
Найти индекс и значение первого числа из списка, которое делится нацело на количество элементов в списке lst.
Список lst заполняется числами.
Найти индекс и значение первого числа из списка, которое меньше первого элемента списка lst.
Список lst заполняется числами.
Найти индекс и значение первого числа из списка, которое меньше первого элемента списка lst.
Список lst заполняется числами.
Найти индекс и значение первого числа из списка, которое после возведения в квадрат меньше количества элементов списка lst.
Список lst заполняется числами.
Найти индекс и значение первого числа из списка, которое не делится нацело на количество элементов в списке lst.
Задание 4. Бинарный поиск
Дан отсортированный массив целых чисел: {5, 6, 12, 21, 22, 23, 27, 46, 47, 58, 59, 62, 68, 70, 72, 84, 88, 95, 96, 99}.
Запишите в таблицу значения границ поиска и условия цикла для поиска числа из вашего варианта.
Поиск числа 12.
Поиск числа 20.
Поиск числа 23.
Поиск числа 91.
Поиск числа 96.
Поиск числа 50.
Поиск числа 88.
Поиск числа 65.
Поиск числа 46.
Поиск числа 71.
Поиск числа 70.
Поиск числа 24.
Поиск числа 48.
Поиск числа 27.
Задание 5. Реализация алгоритма бинарного поиска (sam05.py)
Используйте шаблон кода и блок-схему на Рисунке 1 чтобы оформить функцию для поиска в отсортированном массиве целых чисел.
Для записи решения задачи, используйте следующий шаблон кода:
# импорт генератора случайных целых чисел
from random import randint
# после комментария объявите функцию binarySearch(lst, key)
# запишите её реализацию по блок-схеме
# после комментария запишите алгоритм заполнения
# списка lst случайными числами (см. задание № 2)
# не редактируйте код после этого комментария
# сортируем элементы списка lst
lst.sort()
# выводим элементы списка на экран
print(lst)
# ввод значения, индекс которого нужно найти в списке lst
k = int(input("Значение для поиска: "))
ind = binarySearch(lst, k) # сохраняем результат работы функции в переменной ind
print("Ответ:", ind) # вывод ответа на экранЗадание 6 (sam06.py)
Решите задачу вашего варианта. Список заполняйте случайными числами из отрезка [-10, 40]. Количество элементов в списке вводится с клавиатуры.
Выведите из списка целых случайных чисел четные положительные элементы.
Найдите номер первого элемента списка, который больше количества отрицательных элементов.
Найдите среднее арифметическое элементов списка, больших 10.
Найдите сумму тех элементов списка, которые одновременно имеют четные и отрицательные значения.
В списке найдите минимальный и максимальный элементы. Вычислите их разность.
Найдите номер первого элемента списка, который больше количества отрицательных элементов.
Найдите среднее арифметическое положительных и отрицательных элементов списка.
Выведите из списка целых случайных чисел четные положительные элементы.
Найдите номер первого элемента списка, который больше количества отрицательных элементов.
Найдите среднее арифметическое элементов списка, больших 10.
Найдите сумму тех элементов списка, которые одновременно имеют четные и отрицательные значения.
В списке найдите минимальный и максимальный элементы. Вычислить их разность.
Найдите номер первого элемента списка, который больше количества отрицательных элементов.
Найдите среднее арифметическое положительных и отрицательных элементов списка.
Задание 7 (sam07.py)
Решите задачу вашего варианта. Значения элементов списка вводите с клавиатуры.
Дан список. Определить количество элементов, больших суммы всех элементов массива, и вывести их индексы на экран.
Дан список. Найти количество элементов, значение которых больше среднего арифметического минимального и максимального элементов списка и вывести на экран их индексы.
Количество осадков (в мм), выпавших за каждый день января, хранится в списке. Определить количество дней, в которые выпало осадков больше, чем за первый день месяца и напечатать их дату - число месяца.
В списке записаны оценки учеников по информатике. Определите количество учеников, оценка которых меньше средней оценки по классу и выведите номера элементов списка, соответствующие таким ученикам.
Найдите элемент, наиболее близкий к среднему значению всех элементов списка.
В списке записана информация о стоимости товаров. Определите стоимость двух самых дорогих видов товаров.
В списке хранится о среднедневной температуре за каждый день февраля. Определите даты двух самых холодных дней.
Найдите элемент, наиболее близкий к среднему значению всех элементов списка.
В списке записана информация о стоимости товаров. Определите стоимость двух самых дорогих видов товаров.
В списке хранится о среднедневной температуре за каждый день февраля. Определите даты двух самых холодных дней.
В списке записаны оценки учеников по информатике. Определите количество учеников, оценка которых меньше средней оценки по классу и выведите номера элементов списка, соответствующие таким ученикам.
Количество осадков (в мм), выпавших за каждый день января, хранится в списке. Определить количество дней, в которые выпало осадков больше, чем за первый день месяца и напечатать их дату - число месяца.
Дан список. Найти количество элементов, значение которых больше среднего арифметического минимального и максимального элементов списка и вывести на экран их индексы.
Дан список. Определить количество элементов, больших суммы всех элементов массива, и вывести их индексы на экран.