纵横网站,济南 网站建设公司 医疗,杭州北京网站建设,公众号开发者id在哪里查看目录
##问题描述 ##问题思考
##贪心策略确定
##代码实现
##时间复杂度 ##正确性验证 ##问题描述 给定一个正整数 #x1d45b; #xff0c;将其切分为至少两个正整数的和#xff0c;求切分后所有整数的乘积最大是多少 ##问题思考 假设我们将 #x1d45b; 切分为 …目录
##问题描述 ##问题思考
##贪心策略确定
##代码实现
##时间复杂度 ##正确性验证 ##问题描述 给定一个正整数 将其切分为至少两个正整数的和求切分后所有整数的乘积最大是多少 ##问题思考 假设我们将 切分为 个整数因子其中第 个因子记为 即 本题的目标是求得所有整数因子的最大乘积即 我们需要思考的是切分数量 应该多大每个 应该是多少 ##贪心策略确定 我们假设从n中分出一个最小的因子2则它们的乘积为2 * (n - 2),我们将该乘积与n进行比较得到一个重要结论 当n≥4的时候切分出来一个2后乘积会变大这就说明大于等于4的整数都应该被切分出来。 ##贪心策略1 如果切分方案中包含≥4因子那么它就应该被继续切分。最终的切分方案只应出现123者三种因子。 这是我们就要思考选择什么因子会使结果达到最优解1可以直接舍弃考虑。 当n 6时3*32*2*2说明因子3比因子2更优。 ##贪心策略2 在切分方案中最多出现两个2.因为3个2总可以替换成2个3获得最优的更大乘积。 综上所述可推理出以下贪心策略。 输入整数 从其不断地切分出因子 3 直至余数为 0、1、2 。当余数为 0 时代表 是 3 的倍数因此不做任何处理。当余数为 2 时不继续划分保留。当余数为 1 时由于 2×21×3 因此应将最后一个 3 替换为 2 。 ##代码实现 #python代码示例
import math
def max_product_cutting(n) :if n 3 :return 1 * (n - 1) a n // 3b n % 3if b 1 :return int(math.pow(3,a-1)) * 2 * 2if b 2 :return int(math.pow(3,a)) * 2return int(math.pow(3,a))//c代码示例
int maxProductCutting(int n)
{if (n 3){return 1 * (n - 1) ; } int a n / 3 ;int b n % 3 ;if (b 1){return (int)pow(3,a-1) * 2 * 2 ;}if (b 2){return (int)pow(3,a) * 2 ;}return (int)pow(3,a) ;
} ##时间复杂度 时间复杂度取决于编程语言的幂运算的实现方法。以 Python 为例常用的幂计算函数有三种。 运算符 ** 和函数 pow() 的时间复杂度均为 (log) 。函数 math.pow() 内部调用 C 语言库的 pow() 函数其执行浮点取幂时间复杂度为 (1) 。 变量 和 使用常数大小的额外空间因此空间复杂度为 (1) 。 ##正确性验证 使用反证法只分析 ≥3 的情况。 所有因子 ≤3 假设最优切分方案中存在 ≥4 的因子 那么一定可以将其继续划分为 2(−2) 从而获得更大的乘积。这与假设矛盾。切分方案不包含 1 假设最优切分方案中存在一个因子 1 那么它一定可以合并入另外一个因子中以获得更大的乘积。这与假设矛盾。切分方案最多包含两个 2 假设最优切分方案中包含三个 2 那么一定可以替换为两个 3 乘积更大。这与假设矛盾。
