首页 > 试题广场 >

剪绳子

[编程题]剪绳子
  • 热度指数：259956 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（ m 、 n 都是整数， n > 1 并且 m > 1 ， m <= n ），每段绳子的长度记为 k[1],...,k[m] 。请问 k[1]*k[2]*...*k[m] 可能的最大乘积是多少？例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18 。

数据范围：
进阶：空间复杂度 ，时间复杂度

输入描述:
输入一个数n，意义见题面。


输出描述:
输出答案。
示例1

输入

8

输出

18

说明

8 = 2 +3 +3 , 2*3*3=18
示例2

输入

2

输出

1

说明

m>1，所以切成两段长度是1的绳子
算法知识视频讲解
添加回答
推荐
C/C++
天命剑主头像 天命剑主 
//
// Created by yuanhao on 2019-9-3.
//

#include <iostream>
#include <cmath>

using namespace std;

/**
 * 题目分析：
 * 先举几个例子，可以看出规律来。
 * 4 ： 2*2
 * 5 ： 2*3
 * 6 ： 3*3
 * 7 ： 2*2*3 或者4*3
 * 8 ： 2*3*3
 * 9 ： 3*3*3
 * 10：2*2*3*3 或者4*3*3
 * 11：2*3*3*3
 * 12：3*3*3*3
 * 13：2*2*3*3*3 或者4*3*3*3
 *
 * 下面是分析：
 * 首先判断k[0]到k[m]可能有哪些数字，实际上只可能是2或者3。
 * 当然也可能有4，但是4=2*2，我们就简单些不考虑了。
 * 5<2*3,6<3*3,比6更大的数字我们就更不用考虑了，肯定要继续分。
 * 其次看2和3的数量，2的数量肯定小于3个，为什么呢？因为2*2*2<3*3，那么题目就简单了。
 * 直接用n除以3，根据得到的余数判断是一个2还是两个2还是没有2就行了。
 * 由于题目规定m>1，所以2只能是1*1，3只能是2*1，这两个特殊情况直接返回就行了。
 *
 * 乘方运算的复杂度为：O(log n)，用动态规划来做会耗时比较多。
 */
long long n_max_3(long long n) {
    if (n == 2) {
        return 1;
    }
    if (n == 3) {
        return 2;
    }
    long long x = n % 3;
    long long y = n / 3;
    if (x == 0) {
        return pow(3, y);
    } else if (x == 1) {
        return 2 * 2 * (long long) pow(3, y - 1);
    } else {
        return 2 * (long long) pow(3, y);
    }
}

//给你一根长度为n的绳子，请把绳子剪成m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
//
//输入描述:
//输入一个数n，意义见题面。（2 <= n <= 100）
//
//
//输出描述:
//输出答案。
//示例1
//输入
//8
//输出
//18
int main() {
    long long n = 0;
    cin >> n;
    cout << n_max_3(n) << endl;
    return 0;
}

编辑于 2021-07-06 10:46:45 回复(61)
Javascript
十味一心头像 十味一心 
//暴力 超时
function back_track(n){
    if (n <= 4) return n;
    let ret = 0;
    for(let i=1;i<n;i++){
        ret = Math.max(ret, i*back_track(n-i));
    }
    return ret;
}
function cutRope(number)
{
    // write code here
    if(number == 2) return 1;
    else if(number == 3) return 2;
    return back_track(number);
}

//
function cutRope(number)
{
    // write code here
    if(number == 2) return 1;
    else if(number == 3) return 2;
    
    var f = new Array(number+1).fill(-1);
    for(let i=1;i<=4;i++){
        f[i]=i;
    }
    for(let i=5;i<=number;i++){
        for(let j=1;j<i;j++){
            f[i]= Math.max(f[i],j*f[i-j]);
        }
    }
    return f[number]
}

发表于 2021-09-02 15:59:05 回复(0)
Javascript
牛客822067661号头像 牛客822067661号 
function cutRope(number)
{
    if(number == 2){
        return 1;
    } else if(number == 3){
        return 2;
    } else{
        let a = Math.floor(number / 3);
        let b = number % 3;
        if(b == 0){
            return Math.pow(3 , a)
        }else if(b == 1){
            return Math.pow(3 , (a - 1))*4
        }else if(b == 2){
            return Math.pow(3 , a)*2
        }
    }
}

发表于 2021-08-10 08:43:54 回复(0)
Javascript
牛比特兰克斯头像 牛比特兰克斯
这是js的解法，首先可以明确的是，最大值必由2和3相乘得出。 
function cutRope(number)
{
    // write code here
    var result=[];
    if(number<=4) return number;
    var num_2=Math.floor(number/2);
    for(var i=0;i<=num_2;i++){
        if((number-2*i)%3==0){
            result.push(Math.pow(2,i)*Math.pow(3,(number-2*i)/3));
        }
    }
    return Math.max(...result);
}
module.exports = {
    cutRope : cutRope
};


发表于 2021-07-26 15:55:59 回复(0)
JavaScript
别卷啦！头像 别卷啦！
拷贝力扣：
dp[i] 表示正整数 i 拆分成的整数的最大乘积
前面的代码中的正整数 n 变成了这里的正整数 i，用指针 j 去划分 i，分成了 j 和 i - j。
遍历所有的 jj，i-ji−j 可以选择拆或者不拆，不拆就是 i-ji−j ，拆就是 dp[i - j]dp[i−j]，其实就是对 i - ji−j 调用的结果（子问题的解）。

作者：xiao_ben_zhu
链接：https://leetcode-cn.com/problems/integer-break/solution/shou-hua-tu-jie-di-gui-ji-yi-hua-di-gui-dong-tai-g/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
function cutRope(n)
{
    // write code here
      const dp = new Array(n + 1);
  dp[1] = 1;  
  dp[2] = 1; 
  for (let i = 3; i <= n; i++) {
    dp[i] = 0;
    // 对于数字 i，它可以分为两份：j 和 i-j，j 的范围是 1 到 i-j
    for (let j = 1; j <= i - j; j++) {
      // 对于 i-j 这部分可以拆或不拆，不拆就是 i-j，拆就是 dp[i-j]
      dp[i] = Math.max(dp[i], j * (i - j), j * dp[i - j]);
    }
  }
  return dp[n];
}


发表于 2021-07-04 21:35:55 回复(0)
JavaScript
IPzzzi头像 IPzzzi 
function cutRope(number)
{
    // write code here
    var arr = [2,3,4,6,9,12];
    var a = Math.floor((number - 2) / 6);
    var b = number - a * 6 - 2;
    if(a == 0){
        return arr[b];
    }
    var sum = arr[b];
    for(var i = 0;i < a;i++){
        sum *= 9;
    }
    return sum;
}
找规律，2-7是[2,3,4,6,9,12]，接下来的数以6为一个周期循环，每个周期对应数组里面的数乘上9，例如15，是第3排，第2个数，对应第一排的3，就等于3 * 9 * 9 = 243
发表于 2021-03-19 16:13:43 回复(0)
JavaScript
🐵201908151737683头像 🐵201908151737683
JS会有大数精度缺失的问题，只能用node拯救以下 
function cutRope(number){
    if(isNaN(number)) return
    if(number > 60) return
    if(number === 0) return 0
    if(number === 1) return 0
    if(number === 2) return 1
    if(number === 3) return 2
    if(number % 3 === 0) return BigInt(Math.pow(3, number / 3)).toString()
    if(number % 3 === 1) return BigInt(Math.pow(3, (number / 3 | 0) - 1) * 4).toString()
    if(number % 3 === 2) return BigInt(Math.pow(3, number / 3 | 0) * 2).toString()
}
module.exports = {
    cutRope : cutRope
};


发表于 2020-10-28 18:00:04 回复(0)
JavaScript
待看云开头像 待看云开
注意：VScode调试没问题，牛客网调试显示通过率为0，不知道为啥。。。 
function cutRope(number){
    if(number <= 1) return 0;
    if(number == 2) return 1;
    if(number == 3) return 2;
    else {
        return cutRopeCore(number);
    }
    function cutRopeCore(number) {
        if(number < 4) return number;
        let max = 0;
        for(let i = 1; i < number; ++i){
            max = Math.max( cutRopeCore(i)*cutRopeCore(number - i), max );
        }
        return max;
    }
}


编辑于 2020-07-22 11:27:38 回复(0)
JavaScript
牛客676777060号头像 牛客676777060号
function cutRope(number)
{
    if(number == 2) return 1;
    if(number == 3) return 2;
    let sqrt = Math.ceil(Math.sqrt(number));
    return Math.max(cutRope(number-sqrt)*sqrt,(number-sqrt)*sqrt);
}
凭感觉做的😂
发表于 2020-06-18 00:43:35 回复(0)
JavaScript
牛客76713017号头像 牛客76713017号 
此题分为三种情况，当n等于2和3时只有一种解，当大于3时，最大总长sum又分为三种情况，
n除以3取余，当余数为0时，sum = Math.pow(3, parseInt(number/3))
当余数为1时，sum = Math.pow(3, parseInt(number/3) - 1)*4
当余数为2时，sum = Math.pow(3, parseInt(number/3))*2
（以上公式推导过程不太清晰）
function cutRope(number)
{
    // write code here
    if(number === 2) return 1
    if(number === 3) return 2
    let sum = 0
    switch (number % 3) {
        case 0:
            sum = Math.pow(3, parseInt(number/3))
            break;
        case 1:
            sum = Math.pow(3, parseInt(number/3) - 1)*4
            break;
        case 2:
            sum = Math.pow(3, parseInt(number/3))*2
    }
    return sum
}

发表于 2020-06-05 10:29:07 回复(0)
JavaScript
gemone头像 gemone 
function cutRope(number)
{
    // write code her
    if (number < 4) {
        return number - 1;
    }
    let tmp = number % 3;
    let res = 1;
    let i = Math.floor(number / 3);

    if (tmp == 1) {
        res = 4;
        i--;
    }
    if (tmp == 2) {
        res = 2;
    }
    
    res = res * Math.pow(3.0, i);
    
    return res;
}
module.exports = {
    cutRope : cutRope
};

归纳法，几乎所有最大的整数都和3有关，则对于3进行分类。
如上。
发表于 2020-06-03 21:57:58 回复(0)
JavaScript
没有感情的菠萝头头像 没有感情的菠萝头 
  function cutRope(number)
  {
    // write code here
    var o = [0,1,1,2,4,6,9]
    for (let i = 7; i <= number; i++) {
      o[i] = 3 * o[i - 3]
    }

    return o[number]
  }


发表于 2020-05-18 18:06:17 回复(0)
提交观点

问题信息

基础数学
上传者：小小
难度：
12条回答 69495浏览

热门推荐

通过挑战的用户

查看代码

相关试题

剪绳子

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号