石家庄站布局图,农业交易平台网站建设,闵行区教育学院,便宜做外贸网站1、题目描述
给你一根长度为 n 的绳子#xff0c;请把绳子剪成整数长度的 m 段#xff08;m、n都是整数#xff0c;n1并且m1#xff09;#xff0c;每段绳子的长度记为 k[0],k[1]…k[m - 1] 。请问 k[0]k[1]…*k[m - 1] 可能的最大乘积是多少#xff1f;例如请把绳子剪成整数长度的 m 段m、n都是整数n1并且m1每段绳子的长度记为 k[0],k[1]…k[m - 1] 。请问 k[0]k[1]…*k[m - 1] 可能的最大乘积是多少例如当绳子的长度是8时我们把它剪成长度分别为2、3、3的三段此时得到的最大乘积是18。 答案需要取模 1e971000000007如计算初始结果为1000000008请返回 1。 示例 1 输入: 2 输出: 1 解释: 2 1 1, 1 × 1 1 示例 2: 输入: 10 输出: 36 解释: 10 3 3 4, 3 × 3 × 4 36 这个题与前一个题的区别是这个题大数运算不能用动态规划
2、VS2019上运行
使用贪心算法 贪心算法
#include iostream
using namespace std;class Solution {
public:int cuttingRope(int n) {// 如果 n 小于等于 3则直接返回 n - 1因为长度为 2 和 3 时不剪切乘积最大。if (n 3) return n - 1;// 如果 n 等于 4则直接返回 4因为长度为 4 时将其剪成 2x2 的乘积最大。if (n 4) return 4;long res 1; // 初始化结果变量为 1用于计算乘积。while (n 4){res * 3; // 每次乘以 3res % 1000000007; // 取模防止溢出n - 3; // n 减去 3}// 最后 n 的值只有可能是2、3、4。// 而 2、3、4 能得到的最大乘积恰恰就是自身值// 因为 2、3 不需要再剪了剪了反而变小// 4 剪成 2x2 是最大的2x2 恰恰等于 4return res * n % 1000000007;}
};int main() {Solution sol;int n;cout Enter the length of the rope: ;cin n;int maxProduct sol.cuttingRope(n);cout Maximum product of the rope after cutting is: maxProduct endl;return 0;
}Enter the length of the rope: 10 Maximum product of the rope after cutting is: 36
3、解题思路
为什么选择剪成长度为 3 的绳子这涉及到一个数学推导假设将绳子剪成长度为 x 和 n - x其中 x 为一段的长度n 为总绳子长度。我们希望求得这种剪法下的乘积最大值。可以证明当 x n/3 时乘积最大。对于长度为 n 的绳子1.当 n 3k 时我们将绳子分成长度为 x n/3 k 的三段此时乘积为 x^3 (n/3)^3。 2.当 n 3k 1 时我们将绳子分成长度为 x n/3 k 和 x 1 k 1 的两段此时乘积为 x * (x 1)^2 (n/3) * ((n/3) 1)^2。 3.当 n 3k 2 时我们将绳子分成长度为 x n/3 k 和 x 2 k 2 的两段此时乘积为 x * (x 2) (n/3) * ((n/3) 2)。 可以观察到在 n mod 3 0, 1, 2 时乘积都可以表示为 x 的形式乘以某个因子。而要使乘积最大我们需要选择 x 为整数因此选择 x 最接近 n/3并且取整数部分即 x floor(n/3)。
