海口模板建站平台,wp如何做网站地图,义乌网站建设制作商,wordpress首页排版目录 题目描述
贪心算法
输出结果 题目描述 把一根绳子剪成多段#xff0c;并且使得每段的长度乘积最大。
给定一个正整数 n#xff0c;将其拆分为至少两个正整数的和#xff0c;并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2 输出: 1 解释:…目录 题目描述
贪心算法
输出结果 题目描述 把一根绳子剪成多段并且使得每段的长度乘积最大。
给定一个正整数 n将其拆分为至少两个正整数的和并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2 输出: 1 解释: 2 1 1, 1 × 1 1。 示例 2:
输入: 10 输出: 36 解释: 10 3 3 4, 3 × 3 × 4 36。 说明: 你可以假设 n 不小于 2 且不大于 58。
贪心算法 设n分成k份时乘积最大则要令d (n/k)^k / dk等于零或令d k*log(n/k) / dk等于零。求出来kn/e所以每份应尽量接近e2.7因此尽量凑3。
尽可能多剪长度为 3 的绳子并且不允许有长度为 1 的绳子出现。如果出现了就从已经切好长度为 3 的绳子中拿出一段与长度为 1 的绳子重新组合把它们切成两段长度为 2 的绳子。
证明当 n 5 时3(n - 3) - n 2n - 9 0且 2(n - 2) - n n - 4 0。因此在 n 5 的情况下将绳子剪成一段为 2 或者 3得到的乘积会更大。又因为 3(n - 3) - 2(n - 2) n - 5 0所以剪成一段长度为 3 比长度为 2 得到的乘积更大。
#includeiostream
#includevector
using namespace std;//计算各数位的和
class Solution {
public:int integerBreak(int n) {if (n 2) return 0;if (n 2) return 1;if (n 3) return 2;int T3 n / 3;if (n % 3 1) T3--;int T2 (n - T3 * 3) / 2;return ((int)pow(3, T3)) * ((int)pow(2, T2));}
};int main()
{Solution test;int result test.integerBreak(10);std::cout mian result: result std::endl;return 0;
}输出结果
