Перейти к содержанию
Приглашаем вас участвовать в развитии русской версии! Подробнее здесь.

# 12.6 Упражнения

## 12.6.1 Вопросы для самопроверки

### 1. Какие задачи подходят для метода «разделяй и властвуй»

Ученик хочет решить следующие задачи способом «разделить на две половины, решить каждую отдельно, затем объединить результаты». Для каждой задачи выберите одно из утверждений: «подходит для метода “разделяй и властвуй”», «разделение возможно, но не уменьшает общий объем работы» или «половины нельзя решить независимо». Объясните свой выбор.

1. Отсортировать неупорядоченный массив;
2. найти максимальный элемент массива;
3. последовательно выполнить набор операций стека `push(x)` и `pop()`, выводя элемент, полученный при каждой операции `pop()`.

Ответ

1. Подходит: массив делится пополам, обе половины независимо сортируются, а затем сливаются за \(O(n)\) — именно так работает сортировка слиянием.
2. Разделение возможно, но оно не уменьшит общий объем работы: в обеих половинах в сумме все равно нужно проверить все \(n\) элементов, поэтому, как и при прямом обходе, потребуется \(O(n)\) времени.
3. Половины нельзя решить независимо: содержимое стека в начале второй половины операций зависит от результата первой, поэтому решить их независимо, не зная результатов друг друга, невозможно.

### 2. Как быстрое возведение в степень уменьшает число вычислений

Рекурсивная функция ниже вычисляет \(x^n\) методом «разделяй и властвуй»:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
fast_power.py

    def fast_pow(x: int, n: int) -> int:
        """Быстрое возведение в степень"""
        if n == 0:
            return 1
        half = fast_pow(x, n // 2)
        if n % 2 == 0:
            return half * half
        return half * half * x

fast_power.cpp

    /* Быстрое возведение в степень */
    int fastPow(int x, int n) {
        if (n == 0) {
            return 1;
        }
        int half = fastPow(x, n / 2);
        if (n % 2 == 0) {
            return half * half;
        }
        return half * half * x;
    }

fast_power.java

    /* Быстрое возведение в степень */
    int fastPow(int x, int n) {
        if (n == 0) {
            return 1;
        }
        int half = fastPow(x, n / 2);
        if (n % 2 == 0) {
            return half * half;
        }
        return half * half * x;
    }

fast_power.cs

    /* Быстрое возведение в степень */
    int FastPow(int x, int n) {
        if (n == 0) {
            return 1;
        }
        int half = FastPow(x, n / 2);
        if (n % 2 == 0) {
            return half * half;
        }
        return half * half * x;
    }

fast_power.go

    /* Быстрое возведение в степень */
    func fastPow(x, n int) int {
        if n == 0 {
            return 1
        }
        half := fastPow(x, n/2)
        if n%2 == 0 {
            return half * half
        }
        return half * half * x
    }

fast_power.swift

    /* Быстрое возведение в степень */
    func fastPow(x: Int, n: Int) -> Int {
        if n == 0 {
            return 1
        }
        let half = fastPow(x: x, n: n / 2)
        if n % 2 == 0 {
            return half * half
        }
        return half * half * x
    }

fast_power.js

    /* Быстрое возведение в степень */
    function fastPow(x, n) {
        if (n === 0) {
            return 1;
        }
        const half = fastPow(x, Math.floor(n / 2));
        if (n % 2 === 0) {
            return half * half;
        }
        return half * half * x;
    }

fast_power.ts

    /* Быстрое возведение в степень */
    function fastPow(x: number, n: number): number {
        if (n === 0) {
            return 1;
        }
        const half = fastPow(x, Math.floor(n / 2));
        if (n % 2 === 0) {
            return half * half;
        }
        return half * half * x;
    }

fast_power.dart

    /* Быстрое возведение в степень */
    int fastPow(int x, int n) {
      if (n == 0) {
        return 1;
      }
      int half = fastPow(x, n ~/ 2);
      if (n % 2 == 0) {
        return half * half;
      }
      return half * half * x;
    }

fast_power.rs

    /* Быстрое возведение в степень */
    fn fast_pow(x: i32, n: i32) -> i32 {
        if n == 0 {
            return 1;
        }
        let half = fast_pow(x, n / 2);
        if n % 2 == 0 {
            return half * half;
        }
        half * half * x
    }

fast_power.c

    /* Быстрое возведение в степень */
    int fastPow(int x, int n) {
        if (n == 0) {
            return 1;
        }
        int half = fastPow(x, n / 2);
        if (n % 2 == 0) {
            return half * half;
        }
        return half * half * x;
    }

fast_power.kt

    /* Быстрое возведение в степень */
    fun fastPow(x: Int, n: Int): Int {
        if (n == 0) {
            return 1
        }
        val half = fastPow(x, n / 2)
        if (n % 2 == 0) {
            return half * half
        }
        return half * half * x
    }

fast_power.rb

    ### Быстрое возведение в степень ###
    def fast_pow(x, n)
      return 1 if n == 0

      half = fast_pow(x, n / 2)
      return half * half if n.even?

      half * half * x
    end

Задайте `x = 3` и `n = 5`, затем вычислите результат с помощью этой функции.

1. Какие значения последовательно принимает параметр `n` при рекурсивных вызовах?
2. Какие значения поочередно возвращаются на каждом уровне, начиная с самого глубокого?
3. Почему результат рекурсии нужно сначала сохранить в `half`, а не вызывать одну и ту же подзадачу по одному разу с каждой стороны умножения?

Ответ

1. Параметр последовательно принимает значения `5 → 2 → 1 → 0`: на каждом шаге показатель степени уменьшается вдвое до достижения условия завершения.

2. При `n = 0` возвращается 1; при `n = 1` возвращается \(1×1×3=3\); при `n = 2` — \(3×3=9\); при `n = 5` — \(9×9×3=243\).

3. Если вызвать одну и ту же подзадачу по одному разу с каждой стороны умножения, два рекурсивных вызова выполнят одинаковые вычисления. Когда результат сохраняется в `half`, на каждом уровне выполняется только один рекурсивный вызов, а глубина рекурсии составляет примерно \(\log n\); два вызова привели бы к множеству повторных вычислений.

### 3. Разделение левого и правого поддеревьев по последовательностям обхода

Двоичное дерево без повторяющихся узлов имеет следующие последовательности прямого и симметричного обходов:

- прямой обход: `[A, B, D, E, C]`
- симметричный обход: `[D, B, E, A, C]`

Выполните только разделение на уровне корневого узла: продолжать рекурсию и рисовать все дерево не требуется.

1. Какой узел является корневым?
2. Какие участки симметричного обхода соответствуют левому и правому поддеревьям?
3. Какие участки прямого обхода соответствуют левому и правому поддеревьям? Какие непосредственные дочерние узлы имеет корень?

Ответ

1. Первый узел прямого обхода является корневым, поэтому корень — `A`.

2. Узел `A` делит симметричный обход на две части: левому поддереву соответствует `[D, B, E]`, правому — `[C]`.

3. Левое поддерево содержит 3 узла, поэтому следующие после корня `A` 3 элемента прямого обхода относятся к левому поддереву: `[B, D, E]`. Оставшийся участок `[C]` относится к правому поддереву. Следовательно, левый дочерний узел корня — `B`, а правый — `C`.

## 12.6.2 Задачи по программированию

### 1. Быстрое возведение в степень

Даны вещественное число `x` и целое число `n`. Вычислите \(x^n\), не используя встроенную функцию возведения в степень. Примените рекурсивный метод «разделяй и властвуй»: каждый раз уменьшайте показатель степени вдвое и повторно используйте уже вычисленный результат подзадачи. В этой задаче \(x^0=1\), в том числе при `x = 0`; если `n < 0`, гарантируется, что `x != 0`, а ответ можно преобразовать к \((1/x)^{-n}\).

Подсказки

1. При n, равном 0, ответ равен 1
2. Вычислив x в степени n // 2, сохраните результат в half и не выполняйте рекурсивный вызов второй раз
3. Если n < 0, сначала замените x на 1 / x, а n — на -n; в C++ или Java предварительно преобразуйте n в 64-битное целое число, чтобы избежать переполнения при смене знака у минимального 32-битного целого

LeetCode

##### Оставляйте свои идеи, вопросы и предложения в комментариях