将一个数因式分解为 m 个因子，以最小化其中最大的一个
Factorizing a number into m factors to minimize the largest of them
假设你有一个数字n。
我想将它分解为它的 m 个因子的乘积。
我正在考虑一种算法来做到这一点。
首先，我在其 m th 根下方找到 n 的最大因子 (f1)。
然后，将 n 替换为 n/f1。
现在找到其 (m-1)th root
下 n 的最大因子
重复这个过程，我得到了一系列因素。
你觉得这个算法对吗？或者有什么地方失败了？
您的算法在这种情况下失败：n = 2^3 * 3^2 * 5 = 360 和 m = 3。您的算法执行以下步骤：
- 计算
360^(1/3) = 7.114...并选择小于该值的360的最大因数。因此，选择因子6。
- 将
360 替换为 60。 60的最大因数最多为sqrt(60) = 7.746...是6.
- 最后你的算法选择了最后一个剩余因素，
10。
所以你的算法产生因式分解 n = 6 * 6 * 10。然而，这不是最优的，因为 n = 5 * 8 * 9.
一般来说，您的贪心算法可能会做出使问题在以后变得更糟的选择。这就是本例中发生的情况：第一个因素选择不当，因此后面的选择只会给你次优的解决方案。
假设你有一个数字n。 我想将它分解为它的 m 个因子的乘积。
我正在考虑一种算法来做到这一点。
首先，我在其 m th 根下方找到 n 的最大因子 (f1)。
然后，将 n 替换为 n/f1。
现在找到其 (m-1)th root
重复这个过程，我得到了一系列因素。
你觉得这个算法对吗？或者有什么地方失败了？
您的算法在这种情况下失败：n = 2^3 * 3^2 * 5 = 360 和 m = 3。您的算法执行以下步骤：
- 计算
360^(1/3) = 7.114...并选择小于该值的360的最大因数。因此，选择因子6。 - 将
360替换为60。60的最大因数最多为sqrt(60) = 7.746...是6. - 最后你的算法选择了最后一个剩余因素，
10。
所以你的算法产生因式分解 n = 6 * 6 * 10。然而，这不是最优的，因为 n = 5 * 8 * 9.
一般来说，您的贪心算法可能会做出使问题在以后变得更糟的选择。这就是本例中发生的情况：第一个因素选择不当，因此后面的选择只会给你次优的解决方案。