Перейти к содержимому
10 класс
НОВОЕ
Новости
Новости сайта
Тарифы
Информатика 10 класс · § 5.4

5.4. Решение задач с использованием алгоритма линейного поиска

Содержание
Главное за минуту

Линейный поиск применяют к задачам, где нужно выделить элементы по заданному условию: найти первый подходящий результат, подсчитать совпадения, вывести связанные с ними данные или проверить более сложное свойство. Примеры включают сравнение координат точек с радиусом окружности, отбор подходящих по вместимости ящиков, проверку спортивного норматива и поиск чисел Смита.

Что нужно понять

  • Для координат точек используют два связанных массива X и Y; принадлежность кругу проверяют через квадраты координат и радиуса.
  • При подсчёте точек внутри и снаружи окружности используют два счётчика с начальным значением ноль.
  • В задаче о ящиках подходят вместимости, кратные массе одной упаковки; подсчитывают число таких ящиков и суммарную массу.
  • Для отбора учащихся по спортивному нормативу используют параллельные массивы фамилий и результатов.
  • Если результат бега превышает норматив, выводят соответствующую фамилию и увеличивают счётчик.
  • Для проверки чисел Смита применяют вспомогательные функции: одну для суммы цифр, другую для проверки свойства числа.
  • В массиве строк можно находить предложения с нечётным числом слов, вычисляя количество слов отдельной функцией.
  • В задаче на существование подходящего элемента достаточно остановиться после первой находки; при подсчёте всех требуется полный просмотр.

Видео

Превью видео по теме «5.4. Решение задач с использованием алгоритма линейного поиска» - Информатика, 10 класс
Видео доступно после бесплатной регистрации.

Скачать к теме

Материалы по теме доступны после бесплатной регистрации.

Главное по теме

Условие задачи преобразуют в проверку для каждого элемента, затем собирают нужный результат: наличие, количество, значения или изображение.

Ключевые понятия

Линейный поиск по условию Последовательная проверка элементов массива на выполнение свойства, заданного задачей.
Число Смита Составное число, сумма цифр которого равна сумме цифр всех его простых множителей с учётом повторений.
Параллельные массивы Массивы, элементы с одинаковым индексом которых описывают один объект.
Кратность Делимость одного числа на другое ненулевое число без остатка.
Счётчик Переменная для подсчёта числа элементов, удовлетворяющих условию.

Формулы

Принадлежность точки кругу
X[i] * X[i] + Y[i] * Y[i] <= R * R
  • X[i] абсцисса точки
  • Y[i] ордината точки
  • R радиус окружности
Отбор вместимости, кратной массе упаковки
a[i] mod x = 0
  • a[i] вместимость ящика
  • x масса одной упаковки
Подсчёт выбранных значений
k := k + 1
  • k количество подходящих элементов

Как это работает

Точка удовлетворяет условию для круга Квадраты её координат сравнивают с квадратом радиуса Точку относят к внутренней области, включая границу.
Вместимость ящика кратна массе одного пакета Кратность проверяют по остатку и увеличивают счётчик и сумму Подсчитывают подходящие ящики и общую вместимость.
Результат бега учащегося больше допустимого времени Сравнивают значения массива результатов с нормативом Выводят связанную фамилию и учитывают невыполнение норматива.
Необходимо проверить сложное свойство числа Для элемента вызывают функцию проверки и вспомогательную функцию суммы цифр Отбор числа выполняется в ходе общего просмотра массива.

Что нужно запомнить

  • Определите заранее, нужен ли первый результат или все подходящие элементы.
  • Связанные фамилии и результаты, а также координаты точек, должны иметь одинаковые индексы.
  • В задаче о круге точки на окружности относятся к внутренней области согласно условию.

Проверь себя

Вопрос 1 из 5

Как проверить принадлежность точки с координатами X[i], Y[i] кругу радиуса R с центром в начале координат?

Сравнение суммы квадратов координат с квадратом радиуса учитывает расстояние до центра.
Вопрос 2 из 5

Как в задаче о ящиках установить, что вместимость кратна массе упаковки x?

Нулевой остаток при делении на ненулевое x означает полную кратность.
Вопрос 3 из 5

Почему результаты бега и фамилии хранят в связанных массивах?

Общий индекс связывает числовой результат с фамилией.
Вопрос 4 из 5

Какое свойство определяет число Смита в приведённых задачах?

В определении числа Смита сопоставляют сумму его цифр и суммы цифр простых множителей.
Вопрос 5 из 5

Как поступить, если задача требует вывести всех учащихся, не выполнивших норматив?

Для полного списка нужно проверить все значения и сохранить связь с фамилиями.