43. Силовая функция

Вопрос: Напишите функцию, которая возвращает степень X ^ Y (не используйте встроенные функции).

Например, учитывая 2 ^ 10, вернуть 1024,

Например, учитывая 10 ^ 2, вернуть 100.

Подсказки:

- Вы можете сделать это через рекурсивную функцию,

- Каковы базовые случаи?,

- Что делать, если мощность нечетное число.

Решение:

func power(radix: Int, power: Int) -> Int {
    // 1.
    var memo = [Int: Int]()
    return powerMemo(radix: radix, power: power, memo: &memo)
}

// 2.
func powerMemo(radix: Int, power: Int, memo: inout [Int: Int]) -> Int {
    // 3.
    guard radix != 0 else { return 0 }
    guard power >= 0 else { return 0 }
    guard power != 0 else { return 1 }
    guard power != 1 else { return radix }

    if let value = memo[power] {
        // 4.
        return value
    } else {
        // 5.
        let value = powerMemo(radix: radix, power: power / 2, memo: &memo)
                  * powerMemo(radix: radix, power: power / 2, memo: &memo)
                  * (power % 2 == 0 ? 1 : radix)
        // 6.
        memo[power] = value
        return value
    }
}

Пояснения:

1. Давайте создадим частичный результат для мемоизации и передадим его помощнику функции.

var memo = [Int: Int]()
return powerMemo(radix: radix, power: power, memo: &memo)

2. Это вспомогательная функция, которая является рекурсивной и создает частичные результаты, пока мы не найдем целевой результат.

func powerMemo(radix: Int, power: Int, memo: inout [Int: Int]) -> Int {

3. Это базовые случаи для мощности, основание == 0, мощность ‹= 1 (здесь мы не рассматриваем отрицательную мощность).

guard radix != 0 else { return 0 }
guard power >= 0 else { return 0 }
guard power != 0 else { return 1 }
guard power != 1 else { return radix }

4. Если значения уже рассчитаны, возвращаем сохраненный результат.

if let value = memo[power] {
  return value

5. Поскольку X²N == X^N * X^N, мы можем рекурсивно и уменьшить число мощности (разделить на два и позаботиться о числах степени шансов) до достижения одного из базовых случаев.

let value = powerMemo(radix: radix, power: power / 2, memo: &memo)
            * powerMemo(radix: radix, power: power / 2, memo: &memo)
            * (power % 2 == 0 ? 1 : radix)

6. Сохраним текущий результат и вернем его.

    memo[power] = value
    return value
  }
}

Сложность:

- Временная сложность: поскольку мы каждый раз уменьшаем задачу на два, как при бинарном поиске, временная сложность равна O(log y), где y - мощность,

- Пространственная сложность: стек вызовов и словарь частичных результатов составляют временную сложность O(y).

Тест-кейсы:

public func testPower() {
  assert(power(radix: 2, power: 10) == 1024, "power 1 not equal")
  assert(power(radix: 10, power: 2) == 100, "power 2 not equal")
}

Следовать за:

Сделайте это итеративным или используйте табуляцию (или сделайте и то, и другое!).

‹‹ Структуры данных, алгоритмы и вопросы для интервью ››