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

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

Условие.

К § 29 «Признаки делимости»

Запишите алгоритмы, реализующие признаки делимости на 3, на 9, на 11. Проверяемое число задаётся такими исходными данными: количество цифр в этом числе и запись числа в виде последовательности цифр (массив либо переменная типа «строка»).

Запишите алгоритмы, реализующие признаки делимости на $2n$, $5n$, $10n$.

29.9–29.14. Запишите алгоритм для решения одной из этих задач методом перебора.

Решение.

Запишите алгоритмы, реализующие признаки делимости на 3, на 9, на 11

Входные данные для всех алгоритмов: количество цифр в числе $L$ и само число, представленное в виде последовательности цифр (массив или строка $S$).

Признак делимости на 3

Число делится на 3 без остатка, если сумма его цифр делится на 3.

Алгоритм:

1. Инициализировать переменную для суммы цифр: $Сумма = 0$.
2. В цикле перебрать все цифры числа из последовательности $S$.
3. На каждой итерации цикла прибавлять значение текущей цифры (преобразованной в число) к переменной $Сумма$.
4. После завершения цикла проверить, равен ли остаток от деления переменной $Сумма$ на 3 нулю ($Сумма \pmod 3 = 0$).
5. Если остаток равен 0, число делится на 3. В противном случае — не делится.

Ответ: Алгоритм заключается в вычислении суммы всех цифр числа и проверке делимости этой суммы на 3.

Признак делимости на 9

Число делится на 9 без остатка, если сумма его цифр делится на 9.

Алгоритм:

1. Инициализировать переменную для суммы цифр: $Сумма = 0$.
2. В цикле перебрать все цифры числа из последовательности $S$.
3. На каждой итерации цикла прибавлять значение текущей цифры (преобразованной в число) к переменной $Сумма$.
4. После завершения цикла проверить, равен ли остаток от деления переменной $Сумма$ на 9 нулю ($Сумма \pmod 9 = 0$).
5. Если остаток равен 0, число делится на 9. В противном случае — не делится.

Ответ: Алгоритм заключается в вычислении суммы всех цифр числа и проверке делимости этой суммы на 9.

Признак делимости на 11

Число делится на 11 без остатка, если знакопеременная сумма его цифр (где первая цифра справа берется со знаком «+», вторая со знаком «-» и т.д.) делится на 11.

Алгоритм:

1. Инициализировать переменную для знакопеременной суммы: $Сумма = 0$.
2. Инициализировать переменную для знака: $Знак = 1$.
3. В цикле перебрать все цифры числа из последовательности $S$ справа налево (от последней к первой).
4. На каждой итерации:
   1. Прибавить к переменной $Сумма$ значение текущей цифры, умноженное на $Знак$.
   2. Изменить значение переменной $Знак$ на противоположное ($Знак = -Знак$).
5. После завершения цикла проверить, равен ли остаток от деления переменной $Сумма$ на 11 нулю ($Сумма \pmod{11} = 0$).
6. Если остаток равен 0, число делится на 11. В противном случае — не делится.

Ответ: Алгоритм заключается в вычислении знакопеременной суммы цифр числа и проверке делимости этой суммы на 11.

Запишите алгоритмы, реализующие признаки делимости на 2n, 5n, 10n

В контексте признаков делимости, записи $2n, 5n, 10n$ следует понимать как степени: $2^n, 5^n, 10^n$. Входными данными являются число в виде строки $S$ и целое число $n$.

Признак делимости на $2^n$

Число делится на $2^n$, если число, образованное его последними $n$ цифрами, делится на $2^n$.

Алгоритм:

1. Если количество цифр в числе меньше $n$, то число не делится на $2^n$ (кроме случая, когда само число равно 0).
2. Выделить из строки $S$ подстроку, содержащую последние $n$ цифр.
3. Преобразовать эту подстроку в целое число $X$.
4. Вычислить значение $Y = 2^n$.
5. Проверить, равен ли остаток от деления $X$ на $Y$ нулю ($X \pmod Y = 0$).
6. Если остаток равен 0, исходное число делится на $2^n$. В противном случае — не делится.

Ответ: Алгоритм основан на проверке делимости числа, образованного последними $n$ цифрами, на $2^n$.

Признак делимости на $5^n$

Число делится на $5^n$, если число, образованное его последними $n$ цифрами, делится на $5^n$.

Алгоритм:

1. Если количество цифр в числе меньше $n$, то число не делится на $5^n$.
2. Выделить из строки $S$ подстроку, содержащую последние $n$ цифр.
3. Преобразовать эту подстроку в целое число $X$.
4. Вычислить значение $Y = 5^n$.
5. Проверить, равен ли остаток от деления $X$ на $Y$ нулю ($X \pmod Y = 0$).
6. Если остаток равен 0, исходное число делится на $5^n$. В противном случае — не делится.

Ответ: Алгоритм основан на проверке делимости числа, образованного последними $n$ цифрами, на $5^n$.

Признак делимости на $10^n$

Число делится на $10^n$, если его запись заканчивается на $n$ нулей.

Алгоритм:

1. Если количество цифр в числе меньше $n$, то число не делится на $10^n$.
2. В цикле перебрать последние $n$ символов в строке $S$.
3. Если хотя бы один из этих символов не является '0', то число не делится на $10^n$, и алгоритм завершает работу с отрицательным результатом.
4. Если цикл завершился, и все проверенные символы оказались нулями, то число делится на $10^n$.

Ответ: Алгоритм заключается в проверке того, что последние $n$ цифр числа являются нулями.

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

«Метод перебора» в данном случае означает прямой (не использующий специальные признаки) способ проверки делимости. Для больших чисел, представленных строкой, это реализуется через итеративное вычисление остатка от деления всего числа на заданный делитель, используя свойства модульной арифметики. Продемонстрируем этот метод на примере проверки делимости на 3.

Алгоритм проверки делимости на 3 (методом перебора):

1. Получить на вход число как строку $S$. Задать делитель $m = 3$.
2. Инициализировать переменную для хранения остатка: $Остаток = 0$.
3. В цикле перебрать все цифры числа из строки $S$ слева направо. Для каждой цифры $d$:
   1. Преобразовать символ цифры в число.
   2. Обновить значение остатка по формуле: $Остаток = (Остаток \cdot 10 + d) \pmod m$.
4. После завершения цикла, если итоговое значение переменной $Остаток$ равно 0, то исходное число делится на 3. В противном случае — не делится.

Ответ: Метод перебора (прямого вычисления) заключается в итеративном нахождении остатка от деления всего числа на делитель путем поочередной обработки его цифр слева направо.