锐客网

  1. 首页 > 睿知 > it技术 > >

#|算法理论——快速幂思想（附例题）

算法#职场和发展Python后端动态规划算法理论


文章目录

  • 例题引入
    • 题目要求
    • 示例
  • 快速幂解释及相应题解
    • 解释
    • 题解
  • 进阶题目
    • 题目要求
    • 示例
    • 题解

例题引入 题目要求 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。
示例
  • 示例 1：
输入：x = 2.00000, n = 10 输出：1024.00000
  • 示例 2：
输入：x = 2.10000, n = 3 输出：9.26100
  • 示例 3：
输入：x = 2.00000, n = -2 输出：0.25000 解释：2-2 = 1/22 = 1/4 = 0.25
快速幂解释及相应题解 「快速幂算法」的本质是分治算法。
解释
  • 举个例子，如果我们要计算 x^64，我们可以按照：
    x→x^2 → x4→x8→x16→x32→x^64 的顺序，从 x 开始，每次直接把上一次的结果进行平方，计算 6 次就可以得到 x^64 的值，而不需要对 x 乘 63 次 x。
  • 再举一个例子，如果我们要计算 x^77 ，我们可以按照：
    x — x^2 — x^4 —x^9 — x^19 —x^38 — x^77的顺序
    在 x —x2，x2 —x^4x ，x^19 — x^38这些步骤中，我们直接把上一次的结果进行平方 而在
    x^4 —x^9 ，x^9 — x19，x38 —x^77，这些步骤中，我们把上一次的结果进行平方后，还要额外乘一个 x。
直接从左到右进行推导看上去很困难，因为在每一步中，我们不知道在将上一次的结果平方之后，还需不需要额外乘 xx。但如果我们从右往左看，分治的思想就十分明显了：
当我们要计算 x^n时，我们可以先递归地计算出 y=x ^?n/2?
，其中 ?a? 表示对 a 进行下取整；
根据递归计算的结果，如果 n 为偶数，那么 x^n = y^2
；如果 n 为奇数，那么 x^n = y^2 *x
递归的边界为 n = 0，任意数的 0 次方均为 1。
由于每次递归都会使得指数减少一半，因此递归的层数为 O(log n)，算法可以在很快的时间内得到结果。
题解
class Solution: def myPow(self, x: float, n: int) -> float: def quickMul(N): if N == 0: return 1.0 y = quickMul(N // 2) return y * y if N % 2 == 0 else y * y * xreturn quickMul(n) if n >= 0 else 1.0 / quickMul(-n)

进阶题目 题目要求 你的任务是计算 ab 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。
示例
  • 示例 1：
输入：a = 2, b = [3] 输出：8
  • 示例 2：
输入：a = 2, b = [1,0] 输出：1024
  • 示例 3：
输入：a = 1, b = [4,3,3,8,5,2] 输出：1
  • 示例 4：
【#|算法理论——快速幂思想（附例题）】输入：a = 2147483647, b = [2,0,0] 输出：1198
题解
class Solution: def superPow(self, a: int, b: List[int]) -> int: r = 1 a%=1337 for i in b: r = pow(r, 10) * pow(a, i) % 1337 return

    推荐阅读


    上一篇：#|Python基础——强制类型转换及字符串

    下一篇：#|Leetcode每日一题——三个无重叠子数组的最大和