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

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

Условие.

К § 36 «Размещения»

Как сформировать весь набор размещений по $k$ элементов для заданного множества из $n$ элементов?

Решение.

Чтобы сформировать весь набор размещений по $k$ элементов из множества, содержащего $n$ элементов, необходимо сгенерировать все возможные упорядоченные наборы длины $k$, в которых все элементы различны.

Размещением из $n$ элементов по $k$ называется любой упорядоченный набор из $k$ различных элементов, выбранных из исходного множества. Число таких размещений обозначается $A_n^k$ и вычисляется по формуле:

$A_n^k = \frac{n!}{(n-k)!} = n \cdot (n-1) \cdot \dots \cdot (n-k+1)$

Для генерации всех размещений наиболее нагляден и удобен в реализации рекурсивный алгоритм с возвратом (также известный как backtracking или поиск в глубину).

Алгоритм формирования всех размещений

Алгоритм последовательно строит каждое размещение, добавляя по одному элементу за шаг. Если на каком-то шаге построение заходит в тупик или завершается, алгоритм "возвращается" на шаг назад и пробует другой вариант.

Процесс можно описать следующими шагами:

1. Начинаем с пустого текущего размещения и полного набора доступных элементов из исходного множества.
2. Определяем рекурсивную функцию, которая будет выполнять основной шаг генерации.
3. Базовый случай рекурсии: Если длина текущего размещения стала равна $k$, это означает, что одно полное размещение успешно сформировано. Мы сохраняем его в итоговый список и прекращаем дальнейшее углубление (возвращаемся из рекурсии).
4. Шаг рекурсии: Мы перебираем все элементы исходного множества. Для каждого элемента мы проверяем, не был ли он уже использован в текущем формируемом размещении.
   • Если элемент еще не использован:
     1. Добавляем его в конец текущего размещения.
     2. Вызываем рекурсивную функцию для следующего шага (для построения оставшейся части размещения).
     3. После того как рекурсивный вызов завершился (т.е. все возможные "продолжения" с этим элементом были найдены), мы удаляем этот элемент из конца текущего размещения. Этот "откат" позволяет на следующем шаге цикла попробовать другой неиспользованный элемент на этой же позиции.

Пример: генерация размещений из n=3 по k=2

Пусть дано множество $M = \{1, 2, 3\}$. Мы хотим найти все размещения по 2 элемента.

• Шаг 1: Начинаем с пустого размещения `[]`.
  • Берем первый элемент из $M$ — это `1`. Добавляем его. Текущее размещение: `[1]`. Рекурсивно ищем второй элемент.
    • Пробуем добавить `1`. Нельзя, уже использован.
    • Пробуем добавить `2`. Можно. Текущее размещение `[1, 2]`. Длина равна 2. Найдено размещение (1, 2). Возвращаемся.
    • Пробуем добавить `3`. Можно. Текущее размещение `[1, 3]`. Длина равна 2. Найдено размещение (1, 3). Возвращаемся.
    • Больше элементов нет. Возвращаемся на уровень выше.
  • Берем второй элемент из $M$ — это `2`. Добавляем его. Текущее размещение: `[2]`. Рекурсивно ищем второй элемент.
    • Пробуем добавить `1`. Можно. Текущее размещение `[2, 1]`. Длина равна 2. Найдено размещение (2, 1). Возвращаемся.
    • Пробуем добавить `2`. Нельзя, уже использован.
    • Пробуем добавить `3`. Можно. Текущее размещение `[2, 3]`. Длина равна 2. Найдено размещение (2, 3). Возвращаемся.
    • Больше элементов нет. Возвращаемся на уровень выше.
  • Берем третий элемент из $M$ — это `3`. Добавляем его. Текущее размещение: `[3]`. Рекурсивно ищем второй элемент.
    • Пробуем добавить `1`. Можно. Текущее размещение `[3, 1]`. Длина равна 2. Найдено размещение (3, 1). Возвращаемся.
    • Пробуем добавить `2`. Можно. Текущее размещение `[3, 2]`. Длина равна 2. Найдено размещение (3, 2). Возвращаемся.
    • Пробуем добавить `3`. Нельзя, уже использован.
• Шаг 2: Все варианты перебраны.

В результате мы получили полный набор из $A_3^2 = \frac{3!}{(3-2)!} = 6$ размещений: (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2).

Ответ: Весь набор размещений по $k$ элементов из множества, содержащего $n$ элементов, можно сформировать с помощью рекурсивного алгоритма с возвратом (backtracking). Алгоритм пошагово строит упорядоченные наборы, на каждом шаге добавляя один из еще не использованных элементов, пока длина набора не достигнет $k$. После нахождения одного полного размещения или захода в тупик, алгоритм делает "шаг назад", чтобы исследовать другие варианты.