Номер §27, страница 340 - гдз по алгебре 8 класс учебник Мерзляк, Поляков

Дружим с компьютером - номер §27, страница 340.

Условие.

K § 27 «Деление с остатком. Сравнения по модулю и их свойства»

Запишите алгоритм, входными данными для которого являются два натуральных числа, а выходными — неполное частное и остаток при делении первого числа на второе. Какие отдельные случаи надо рассмотреть? Как надо изменить этот алгоритм, если делимое является целым числом?

* Есть ли в выбранном вами языке программирования операция, позволяющая найти неполное частное и остаток при делении двух натуральных чисел?

27.40, 27.41. Запишите алгоритм для решения этих задач методом перебора.

27.42, 27.43. Благодаря какому свойству деления с остатком эти задачи можно решить методом перебора? Запишите алгоритм для решения одной из них.

Решение.

Запишите алгоритм, входными данными для которого являются два натуральных числа, а выходными — неполное частное и остаток при делении первого числа на второе. Какие отдельные случаи надо рассмотреть? Как надо изменить этот алгоритм, если делимое является целым числом?

Деление с остатком для двух натуральных чисел $a$ (делимое) и $b$ (делитель) — это нахождение таких целых неотрицательных чисел $q$ (неполное частное) и $r$ (остаток), что выполняется равенство $a = b \cdot q + r$ при условии $0 \le r < b$.

Алгоритм для натуральных чисел (метод последовательного вычитания):

1. Получить входные данные: натуральные числа $a$ и $b$.
2. Создать переменную для частного $q$ и присвоить ей значение 0.
3. Создать переменную для остатка $r$ и присвоить ей значение $a$.
4. Пока значение $r$ больше или равно $b$:
   • Вычесть $b$ из $r$: $r \leftarrow r - b$.
   • Увеличить $q$ на 1: $q \leftarrow q + 1$.
5. Вывести результат: неполное частное $q$ и остаток $r$.

Отдельные случаи, которые надо рассмотреть:

• Делитель $b$ равен 0. В натуральных числах (по определению, $1, 2, 3, ...$) этот случай невозможен. Если же рассматривать неотрицательные целые, то деление на ноль является неопределенной операцией, и этот случай должен обрабатываться как ошибка.
• Делимое $a$ меньше делителя $b$. В этом случае тело цикла `while` не будет выполнено ни разу. Алгоритм корректно вернет $q=0$ и $r=a$, что является правильным решением, так как $a = b \cdot 0 + a$ и $0 \le a < b$. Этот случай не требует специальной обработки.

Изменение алгоритма, если делимое является целым числом:

Если делимое $a$ — любое целое число (положительное, отрицательное или ноль), а делитель $b$ — натуральное число, определение деления с остатком остается прежним: найти целые $q$ и $r$, такие что $a = b \cdot q + r$ и $0 \le r < b$.

Алгоритм изменится следующим образом:

1. Получить входные данные: целое число $a$ и натуральное число $b$.
2. Вычислить неполное частное $q$ как наибольшее целое число, не превосходящее частное $a/b$. Эта операция называется «пол» или `floor`. Формула: $q = \lfloor a/b \rfloor$.
3. Вычислить остаток $r$ по формуле: $r = a - b \cdot q$.
4. Вывести результат: частное $q$ и остаток $r$.

Например, для $a = -17$ и $b = 5$:
$q = \lfloor -17 / 5 \rfloor = \lfloor -3.4 \rfloor = -4$.
$r = -17 - 5 \cdot (-4) = -17 + 20 = 3$.
Проверка: $5 \cdot (-4) + 3 = -20 + 3 = -17$. Условие $0 \le 3 < 5$ выполнено.

Ответ: Алгоритм для натуральных чисел заключается в многократном вычитании делителя из делимого. Особый случай — деление на ноль, которое недопустимо. Для целого делимого алгоритм изменяется: частное вычисляется как $q = \lfloor a/b \rfloor$, а остаток как $r = a - b \cdot q$.

* Есть ли в выбранном вами языке программирования операция, позволяющая найти неполное частное и остаток при делении двух натуральных чисел?

Да, в большинстве языков программирования есть такие операции. В качестве примера рассмотрим язык Python.

В Python есть несколько способов найти неполное частное и остаток:

• Оператор целочисленного деления `//` возвращает неполное частное. Например, `17 // 5` вернет `3`.
• Оператор остатка от деления `%` возвращает остаток. Например, `17 % 5` вернет `2`.
• Встроенная функция `divmod(a, b)` является наиболее удобной, так как она выполняет обе операции одновременно и возвращает пару значений (кортеж), состоящую из неполного частного и остатка. Например, `divmod(17, 5)` вернет `(3, 2)`.

Эти операции корректно работают и для целых чисел в соответствии с математическим определением, приведенным в предыдущем пункте. Например, `divmod(-17, 5)` вернет `(-4, 3)`.

Ответ: Да, например, в языке Python для этого существует встроенная функция `divmod(a, b)`, а также операторы `//` (целочисленное деление) и `%` (остаток от деления).

27.40, 27.41. Запишите алгоритм для решения этих задач методом перебора.

В представленном на изображении фрагменте текста отсутствуют формулировки задач 27.40 и 27.41. Без условия этих задач невозможно составить алгоритм для их решения.

Ответ: Записать алгоритм невозможно, так как текст задач 27.40 и 27.41 не предоставлен.

27.42, 27.43. Благодаря какому свойству деления с остатком эти задачи можно решить методом перебора? Запишите алгоритм для решения одной из них.

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

Согласно определению, при делении целого числа $a$ на натуральное число $b$, остаток $r$ всегда находится в строго определенном диапазоне: $0 \le r < b$. Это означает, что количество возможных остатков конечно и равно $b$. Если условие задачи зависит от остатка, то вместо перебора всех возможных чисел можно ограничиться перебором конечного набора вариантов, связанных с возможными остатками, что делает метод перебора эффективным.

Текст задач 27.42 и 27.43 также отсутствует. Ниже приведен алгоритм решения для типичной задачи такого рода.

Пример задачи: «Найти наименьшее натуральное число $x$, которое при делении на 5 дает остаток 4, а при делении на 6 — остаток 5.»

Алгоритм решения методом перебора:

1. Начать перебор натуральных чисел $x$ в порядке возрастания, начиная с 1.
2. Для каждого числа $x$ выполнить проверку двух условий:
   • Первое условие: остаток от деления $x$ на 5 равен 4 (проверяем, верно ли, что $x \pmod 5 = 4$).
   • Второе условие: остаток от деления $x$ на 6 равен 5 (проверяем, верно ли, что $x \pmod 6 = 5$).
3. Если оба условия выполняются одновременно, то число $x$ является решением.
4. Поскольку мы ищем наименьшее число и перебираем кандидатов по возрастанию, первое же найденное число $x$, удовлетворяющее обоим условиям, будет искомым ответом. Следует прекратить перебор и вывести это число.

Применение алгоритма:
...
$x=29$: $29 \pmod 5 = 4$ (верно), $29 \pmod 6 = 5$ (верно). Оба условия выполнены.
Наименьшее такое число — 29.

Ответ: Свойство — ограниченность остатка ($0 \le r < b$). Алгоритм для типовой задачи состоит в последовательном переборе натуральных чисел и проверке их на соответствие заданным условиям по остаткам от деления. Первое число, удовлетворяющее всем условиям, будет наименьшим решением.