ГДЗ: Параграф §3.2 / Информатика 8 класс

• Словесное описание (на естественном языке).
• Построчная запись (полуформальное словесное представление).
• Блок-схема (графический способ).
• Языки программирования (формальные языки, включая Школьный алгоритмический язык и псевдокод).

Разнообразие методов обусловлено различными целями: словесное описание просто для понимания человеком, но неточно; блок-схема обеспечивает наглядность; построчная запись и псевдокод позволяют избежать двусмысленности и стандартизировать запись; языки программирования необходимы для выполнения алгоритма компьютером. Каждый способ имеет свои достоинства и недостатки, что делает целесообразным использование разных методов в зависимости от задачи и исполнителя.

НОК через разложение на простые множители:

• Разложите первое число на простые множители.
• Разложите второе число на простые множители.
• Составьте произведение, взяв все множители из разложения первого числа.
• Добавьте в это произведение недостающие простые множители из разложения второго числа.
• Вычислите произведение.

НОК через НОД:

• Найдите наибольший общий делитель (НОД) двух чисел \( a \) и \( b \) (например, используя алгоритм Евклида).
• Вычислите произведение этих чисел: \( a \cdot b \).
• Разделите полученное произведение \( a \cdot b \) на найденный НОД.
• Результат деления является наименьшим общим кратным (НОК). Формула: \( НОК(a, b) = \frac{ a \cdot b }{ НОД(a, b) } \).

Алгоритм сортировки четырех арбузов по весу с помощью трех взвешиваний (Построчная запись):

• Шаг 1. Обозначить арбузы как \( A \), \( B \), \( C \), \( D \).
• Шаг 2. Взвесить арбузы \( A \) и \( B \). (Сравнение 1)
• Шаг 3. Обозначить меньший из них как \( X \), больший как \( Y \).
• Шаг 4. Взвесить арбузы \( C \) и \( D \). (Сравнение 2)
• Шаг 5. Обозначить меньший из них как \( Z \), больший как \( W \).
• Шаг 6. Взвесить \( X \) и \( Z \). (Сравнение 3)
• Шаг 7. Если \( X < Z \), то самый легкий арбуз — \( X \). Самый тяжелый арбуз — \( W \). Арбузы в порядке возрастания: \( X \), затем \( Z \), \( Y \), \( W \) или \( X \), затем \( Y \), \( Z \), \( W \). Необходимо 4-е взвешивание для определения порядка \( Y \) и \( Z \).
• Шаг 8. Если \( X > Z \), то самый легкий арбуз — \( Z \). Самый тяжелый арбуз — \( Y \). Арбузы в порядке возрастания: \( Z \), затем \( X \), \( W \), \( Y \) или \( Z \), затем \( W \), \( X \), \( Y \). Необходимо 4-е взвешивание для определения порядка \( W \) и \( X \).
• Шаг 9. Вывод: Сортировка четырех элементов с гарантированным результатом невозможна за 3 взвешивания, требуется минимум 5 сравнений (\( \lceil \log_{2}(4!) \rceil = \lceil \log_{2}(24) \rceil = 5 \)). Алгоритм за 3 взвешивания может только найти самый легкий или самый тяжелый, либо расположить три из четырех.

Блок-схема будет иметь следующую логику:

• Начало.
• Действие: Разделить монеты \( M_1 \), \( M_2 \), \( M_3 \) на три группы: \( A = \{ M_1 \} \), \( B = \{ M_2 \} \), \( C = \{ M_3 \} \).
• Действие: Сравнить вес группы \( A \) и группы \( B \) (взвесить \( M_1 \) и \( M_2 \)). (Взвешивание 1)
• Условие: \( M_1 = M_2 \)?
• Если 'Да': Фальшивая монета — \( M_3 \). Вывод: \( M_3 \) — фальшивая.
• Если 'Нет':
• Условие: \( M_1 < M_2 \)?
• Если 'Да': \( M_1 \) — фальшивая (так как она легче). Вывод: \( M_1 \) — фальшивая.
• Если 'Нет' (\( M_1 > M_2 \)): \( M_2 \) — фальшивая (так как она легче). Вывод: \( M_2 \) — фальшивая.
• Конец.

Построение окружности заданного радиуса \( r \) с центром в точке \( A \). Точка \( B \) в данном случае не влияет на построение, если только \( B \) не должна лежать на окружности, но в задаче сказано 'проходящей через заданную \( B \)', что может означать, что \( B \) просто задана. Предположим, что нужно построить окружность с центром \( A \) и радиусом \( r \).

Псевдокод: Построение окружности

• алг Построение_окружности
• нач
• ввод Координаты центра \( A(x_A, y_A) \)
• ввод Заданный радиус \( r \)
• действие Установить циркуль в точку \( A \)
• действие Установить раствор циркуля равным \( r \)
• действие Провести окружность
• кон

Если же точка \( B(x_B, y_B) \) определяет радиус, то:

• алг Построение_окружности_через_точку
• нач
• ввод Координаты центра \( A(x_A, y_A) \)
• ввод Координаты точки на окружности \( B(x_B, y_B) \)
• действие Вычислить радиус \( r \) как расстояние между \( A \) и \( B \): \( r = \sqrt{(x_B - x_A)^2 + (y_B - y_A)^2} \)
• действие Установить циркуль в точку \( A \)
• действие Установить раствор циркуля равным \( r \)
• действие Провести окружность
• кон

Словесное описание алгоритма (страница 92):

Алгоритм предназначен для проверки, является ли заданное натуральное число \( N \) простым или составным. Простое число — это натуральное число, имеющее ровно два различных натуральных делителя: единицу и само себя. Составное число имеет более двух делителей.

• Начало. Вводится число \( N \).
• Переменной \( K \) присваивается начальное значение 2. \( K \) — это возможный делитель \( N \).
• Далее происходит проверка условия: делится ли \( N \) на \( K \) без остатка?
• Если 'Да' (\( N \) делится на \( K \)):
• Если при этом \( N \) равно \( K \), значит, число \( N \) имеет только один делитель, кроме 1 — само себя. Следовательно, \( N \) — простое число.
• Если \( N \) не равно \( K \), значит, \( N \) имеет делитель \( K \), отличный от 1 и самого \( N \). Следовательно, \( N \) — составное число.
• Если 'Нет' (\( N \) не делится на \( K \)):
• Значение \( K \) увеличивается на 1: \( K \leftarrow K + 1 \).
• Проверка делимости повторяется с новым значением \( K \). Этот цикл продолжается до тех пор, пока \( N \) не разделится на \( K \) без остатка.
• Конец.

Основное отличие заключается в формализации и однозначности. Словесное описание на естественном языке неформально и неоднозначно; оно может быть интерпретировано по-разному. Описание же на формальном языке (например, языке программирования или псевдокоде) строго формализовано и однозначно, исключая двойные толкования. Формальный язык использует четко определенные алфавит, синтаксис и семантику, что позволяет исполнителю (человеку или компьютеру) точно знать, какое действие должно быть выполнено на каждом шаге.