Номер 1.3, страница 422 - гдз по алгебре 10 класс учебник Мерзляк, Номировский

1.3.!* Функция задана таблично. Запишите алгоритм для определения того, является ли эта функция возрастающей либо убывающей. Какую структуру данных изучаемого языка программирования вы используете для табличного представления функции?

Запишите алгоритм для определения того, является ли эта функция возрастающей либо убывающей.

Для начала определим, что значит возрастающая и убывающая функция применительно к набору табличных данных. Функция $y = f(x)$ называется:

• Возрастающей (неубывающей), если для любых двух аргументов $x_1$ и $x_2$ из области определения, таких что $x_1 < x_2$, выполняется неравенство $f(x_1) \le f(x_2)$.
• Убывающей (невозрастающей), если для любых двух аргументов $x_1$ и $x_2$ из области определения, таких что $x_1 < x_2$, выполняется неравенство $f(x_1) \ge f(x_2)$.

Если неравенства строгие ($<$ и $>$), то функция называется строго возрастающей или строго убывающей соответственно. Алгоритм ниже проверяет на нестрогое возрастание/убывание.

Предположим, что функция задана набором из $n$ пар $(x_i, y_i)$, где $y_i = f(x_i)$. Для осмысленной проверки необходимо, чтобы в таблице было как минимум две точки ($n \ge 2$).

Алгоритм:

1. Подготовка данных. Упорядочить все пары $(x_i, y_i)$ по возрастанию аргумента $x_i$. Если значения $x$ уже отсортированы, этот шаг можно пропустить. В результате мы получаем последовательность значений функции $y_1, y_2, \ldots, y_n$, соответствующих отсортированным значениям $x_1 < x_2 < \ldots < x_n$.
2. Инициализация. Создать две логические (булевы) переменные-флага. Пусть первая, `is_increasing`, помечает, может ли функция быть возрастающей, а вторая, `is_decreasing`, — может ли она быть убывающей. Изначально присвоить обеим переменным значение "истина" (`true`).
   `is_increasing = true`
   `is_decreasing = true`
3. Проверка в цикле. Пройти в цикле по всем значениям функции, начиная со второго. То есть для $i$ от 2 до $n$. В каждой итерации сравнивать текущее значение $y_i$ с предыдущим $y_{i-1}$.
   • Если обнаружено, что $y_i < y_{i-1}$, это нарушает условие возрастания. Следовательно, функция не является возрастающей. Устанавливаем флаг `is_increasing` в значение "ложь" (`false`).
   • Если обнаружено, что $y_i > y_{i-1}$, это нарушает условие убывания. Следовательно, функция не является убывающей. Устанавливаем флаг `is_decreasing` в значение "ложь" (`false`).
4. Вывод результата. После завершения цикла проанализировать значения флагов:
   • Если `is_increasing` остался `true`, значит, на всем протяжении не было нарушено условие возрастания. Функция является возрастающей.
   • Если `is_decreasing` остался `true`, значит, не было нарушено условие убывания. Функция является убывающей.
   • Если оба флага `is_increasing` и `is_decreasing` равны `true` (это возможно только если все значения $y_i$ равны), функция является и возрастающей, и убывающей (является постоянной).
   • Если оба флага стали `false`, функция не является ни возрастающей, ни убывающей (немонотонная).

Ответ: Алгоритм состоит из сортировки данных по аргументу $x$, последующего однократного прохода по значениям функции $y$ с проверкой выполнения условий $y_i \ge y_{i-1}$ и $y_i \le y_{i-1}$ и обновлением двух логических флагов для определения итогового характера монотонности.

Какую структуру данных изучаемого языка программирования вы используете для табличного представления функции?

Для табличного представления функции, которое по сути является набором пар «аргумент-значение» $(x, y)$, можно использовать несколько подходящих структур данных. Выбор зависит от конкретного языка программирования и особенностей задачи.

Наиболее распространенные и удобные варианты:

• Два параллельных массива (или списка). Один массив хранит значения аргументов ($x$), другой — соответствующие значения функции ($y$). Например, в языке Python это могли бы быть два списка: `x_values = [1, 2, 3, 5]` и `y_values = [2, 4, 6, 10]`. Связь между $x_i$ и $y_i$ устанавливается по общему индексу `i`. Это простой и эффективный по памяти способ.

• Массив (список) пар или объектов. Более структурированный подход, где каждый элемент массива представляет собой единую сущность — точку функции. Пара $(x, y)$ хранится вместе.

  • В Python это может быть список кортежей: `points = [(1, 2), (2, 4), (3, 6)]`.
  • В C++ — вектор пар: `std::vector> points;`.
  • В Java — массив или `ArrayList` объектов специального класса `Point`, имеющего поля `x` и `y`.
  Этот способ лучше отражает логику данных и упрощает операции, такие как сортировка.
• Ассоциативный массив (словарь, хэш-таблица, карта). В этой структуре аргументы $x$ выступают в роли ключей, а значения функции $y$ — в роли значений.
  • В Python — словарь: `function_data = {1: 2, 2: 4, 3: 6}`.
  • В C++ — `std::map` или `std::unordered_map`.
  Преимущество `std::map` в C++ (или аналогичных упорядоченных словарей в других языках) заключается в том, что ключи в нем уже хранятся в отсортированном виде, что избавляет от необходимости выполнять шаг 1 в предложенном выше алгоритме.

Ответ: Для табличного представления функции удобно использовать массив (список) пар/объектов, где каждый объект хранит пару $(x, y)$, или ассоциативный массив (словарь), где ключами являются значения $x$, а значениями — $y$. Упорядоченный ассоциативный массив (например, `map` в C++) является особенно подходящим, так как он автоматически поддерживает данные отсортированными по аргументу функции.