首页 > 试题广场 >

剪绳子

[编程题]剪绳子
  • 热度指数：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)
Python
牛客549486156号头像 牛客549486156号 
# -*- coding:utf-8 -*-
class Solution:
    def cutRope(self, number):
        # 当number为1~3的时候必须切
        if number<=3:
            return number - 1
        # 贪婪：n>=5时候尽量多切3，剩下的长度为4的时候，取2*2
        remainder = number % 3 
        if remainder == 0:
            return 3**(number // 3)
        elif remainder == 1:
            return 3**(number // 3 - 1) * 4
        else:
            return 3**(number // 3) * 2


编辑于 2021-04-15 23:50:00 回复(0)
Python
牛客541273514号头像 牛客541273514号 
# -*- coding:utf-8 -*-
class Solution:
    def cutRope(self, number):
        # write code here
        res=[0,0,1,2,4,6]
        res1=[]
        if 1<number<=5:
            return res[number]
        else:
            for i in range(6,number+1):
                for j in range(1,i):
                    ##先把绳子一分为二
                    ##两边再次切割
                    res1.append(res[i-j]*res[j])
                    ##两边不再切割
                    res1.append((i-j)*j)
                    ##左边绳子不切割 右边切割
                    res1.append((i-j)*res[j])
                    ##左边切割 右边不切割
                    res1.append(res[i-j]*j)
                res.append(max(res1))
            return res[number]

发表于 2021-04-12 22:52:33 回复(0)
Python
在下小6头像 在下小6

python解法：
已知：如果把整数n分为两部分，那么这两部分的值相差越小乘积越大。同理还可以证明如果分成3部分，4部分……也是相差越小乘积会越大。
根据上面的证明，如果我们把长度为n的绳子分为x段，则每段只有在长度相等的时候乘积最大，具体见下：
图片说明
解法1:由数学公式得：当绳子长度为e(2.71828)时，乘积最大，取不到e，所以取3；但也有例外，当n<=4的时候会有特殊情况，因为2×2>1×3。
思路：如果n大于4，我们不停的把绳子减去3；

'''
class Solution:
    def cutRope(self, number):
        if number == 2 or number == 3:
            return number - 1
        res = 1
        # 注意绳长为4的时候，最大乘积为2，2×2>1×3；
        while number > 4:
            # 如果长度大于4，每次取绳子长度为3；
            number -= 3
            # 计算乘积
            res *= 3
        return number * res

解法2:思路同1，只是写法不同；

class Solution:
    def cutRope(self, number):
        if number == 2 or number == 3:
            res = number - 1
        # 绳长是3的倍数，则绳长全部取3；
        elif number % 3 == 0:
            res = 3 ** (number / 3)
        # 绳长对3求余余1，一个绳长取4，剩下取3；
        elif number % 3 == 1:
            res = 4 * 3 ** (number / 3 - 1)
        # 绳长对3求余余2，一个绳长取2，剩下取3；
        else:
            res = 2 * 3 ** (number / 3)
        return res
发表于 2021-02-20 17:33:15 回复(0)
Python
Hollon头像 Hollon 
# -*- coding:utf-8 -*-
class Solution:
    def cutRope(self, number):
        # write code here
        if number%3==0:
            return 3**(number//3)
        elif number%3==1:
            return 3**(number//3-1)*4
        else:
            return 3**(number//3)*2
        
绳子长度可以剪为长度为整数且要大于1，
长度为3时不剪，
长度为4时，剪则积为2*2=4，与不剪没有区别，
长度为5时，剪为2和3积为6大于5，故要剪，
长度为6时，剪为2*2*2=8，剪为3*3=9积最大，可以看出同样的和，剪为3比剪为2更好，
以此类推，长度大于6时可以剪为长度3的一段则剪，余下为1时可以与一段3一起成为长度4的一段，余下为2时将积乘上即可。
发表于 2020-11-03 16:19:23 回复(0)
Python
火树银花zjl头像 火树银花zjl 
# -*- coding:utf-8 -*-
class Solution:
    def cutRope(self, number):
        # write code here
        if number==2:
            return 1
        if number==3:
            return 2
        if number==4:
            return 4
        if number>4:
            a=number/3
            b=number%3
            if b==0:
                return pow(3, a)
            elif b==1:
                return pow(3, a-1)*4
            else:
                return pow(3, a)*b

发表于 2020-09-11 13:52:52 回复(0)
Python
牛客305994801号头像 牛客305994801号
def cutRope(n):
    x = int(n%3/2)+n%3%2*2
    y = int(n/3)-n%3%2
    return 2**x * 3**y
n = int(input(""))
print(cutRope(n))
'''
思路上可知，n%3有三种情况，0、1、2
    当n%3=0时，最大乘积为n/3个3相乘；
    当n%3=1时，需将一个3和余数1组合拆分成两个2，最大乘积为两个2和（n/3-1）个3相乘
    当n%3=2时，最大乘积为余数2和n/3个3相乘
易推出，绳长为2的个数为n%3/2+n%3%2*2
       绳长为2的个数为n/3-n%3%2
'''
发表于 2020-08-02 12:13:27 回复(0)
Python
DDooo头像 DDooo 
# -*- coding:utf-8 -*-
class Solution:
    def cutRope(self, number):
        # write code here
        dp = [0] * (number+1)
        dp[2] =1
        for i in range(3,number+1):
            for j in range(i):
                dp[i] = max(dp[i],j*dp[i-j],j*(i-j))
        return dp[-1]
注意：dp[0]=0 dp[1]=0 dp[2]=1......所以后面对应的绳子长度n在数组中是dp[n]，故一开始需要将[0]乘以（n+1）倍。
编辑于 2020-07-27 20:36:35 回复(0)
Python
牛客720457535号头像 牛客720457535号

动态规划问题
设绳子长度为n，如果剪下长为m的一段，则剩下的长度为n-m的绳子无论怎么剪，乘积最大的情况为f(n-m)，所以
f(n)=max{f(n-1),2*f(n-2),...,(n-2)*f(2)}

将n从2开始往后推，即可得到长度为n时的结果。

class Solution:
    def listSum(self, a, b):
        c = []
        for x,y in zip(a,b):
            c.append(x+y)
        return c
    def cutRope(self, number):
        # write code here
        # f(n) = max{f(n-1),2*f(n-2),...,(n-1)*f(1)}
        f2 = 1
        all_f = [f2]
        cmpList = []
        for i in range(1, number+1):
            cmpList.append(0)
            cmpList = self.listSum(cmpList, all_f)
            all_f.append(max(cmpList))
        return all_f[-1]
编辑于 2020-07-22 10:36:06 回复(0)
Python
liucr.baozi头像 liucr.baozi

均值不等式定理
均值不等式也可以看成是“对于若干个非负实数，它们的算术平均不小于几何平均“
将绳子n按照x的长度的a段，即，，乘积为，,所以函数目标可以优化为，求最大值
对求导，








求最大值，令，即，，因为e的值在2～3之间，且，所以切绳子的每段最优排序为（可以继续最优分割，所以只能取比3小且为整数的值）

自此，切绳子问题转化成了取余的问题 

    def cutRope(self, number):
        # write code here
        result = []
        if number%3==2:
            return pow(3,(number//3))*2
        if number%3==0:
            return pow(3,(number//3))
        if number%3==1:
            return pow(3,(number//3-1))*2*2


编辑于 2020-07-21 19:17:52 回复(1)
Python
夜晚将会美丽丶头像 夜晚将会美丽丶 
class Solution:
    def cutRope(self, number):
        # write code here
        n = number // 3
        a = number % 3
        if a == 0:return 3**n
        if a == 2:return 3**n*2
        if a == 1:return 3**(n-1)*4
精简代码
发表于 2020-07-10 00:52:00 回复(0)
Python
mykelley头像 mykelley 
# -*- coding:utf-8 -*-
class Solution:
    def cutRope(self, number):
        if number == 0:
            return 0
        if number == 1:
            return 1
        if number == 2:
            return 2
        if number == 3:
            return 3
        if number == 4:
            return 4
        result = [0,1,2,3,4]
        for i in range(5,number + 1):
            max = 0
            for j in range(1,i // 2+1):
                temp = result[j] * result[i-j]
                if temp > max:
                    max = temp
            result.append(max)
        return result[number]

当n < 4时，最大乘积是n本身。

当n > 5时，最大乘积f(n) = f(i) * f(n - i)

通过迭代函数，自下向上地计算f(n)

编辑于 2020-06-24 10:58:40 回复(0)
Python
w_w_头像 w_w_

python动态规划\贪婪算法

# -*- coding:utf-8 -*-
class Solution:
    def cutRope(self, number):
        # write code here
        #动态规划，自下向上解决问题
        if number < 2:
            return 0
        if number == 2:
            return 1
        if number == 3:
            return 2
        #保存结果的数组，
        result = [0,1,2,3]
        for i in range(4, number+1):
            max = 0
            for j in range(1,i/2+1):
                temp = result[j]*result[i-j]
                if temp > max:
                    max = temp
            result.append(max)
        return result[number]

# -*- coding:utf-8 -*-
class Solution:
    def cutRope(self, number):
        # write code here
        #贪婪算法
        if number < 2:
            return 0
        if number == 2:
            return 1
        if number == 3:
            return 2
        if number == 4:
            return 4
        result = [0,1,2,3,4]
        num3 = number/3
        num2 = 1
        if number-num3*3 == 1:
            num3 -= 1
            num2 = 1
        return pow(3,num3) * pow(2,num2)



编辑于 2020-06-22 10:59:35 回复(0)
Python
一直都可以啊头像 一直都可以啊 
class Solution {
public:
    int cutRope(int length) {
        //动态法
//        if(length<2)
//            return 0;
//        if (length==2)
//            return 1;
//        if (length==3)
//            return 2;
//        int* products=new int[length+1];
//        //不分的时候最大，为了后面计算的方便
//        products[0]=0;
//        products[1]=1;
//        products[2]=2;
//        products[3]=3;
//        for(int i=4;i<=length;i++)
//        {
//            for(int j=1;j<=i/2;j++)
//            {
//                products[i]=max(products[i],products[j]*products[i-j]);
//            }
//        }
//        int max=products[length];
//        delete[] products;
//        return max;
        //贪婪算法
        if(length<2)
            return 0;
        if (length==2)
            return 1;
        if (length==3)
            return 2;
        int t3=length/3;
        if(length-t3*3==1)//绳子最后剩4时，最好的办法是2*2，>3*1
            t3-=1;
        int t2=(length-t3*3)/2;
        return (int)(pow(3,t3))*(int)(pow(2,t2));
    }
};
# -*- coding:utf-8 -*-
class Solution:
    def cutRope(self, length):
        #动态法
#        if length<2:
#            return 0
#        if length==2:
#            return 1
#        if length==3:
#            return 2
#        prod=[0,1,2,3]
#        max=0
#        for i in range(4,length+1):
#            for j in range(1,i//2+1):
#                pro=prod[i-j]*prod[j]
#                if max<pro:
#                    max=pro
#            prod.append(max)
#        return prod[length]
        #贪婪法
        if length<2:
            return 0
        if length==2:
            return 1
        if length==3:
            return 2
        if length>=4:
            t3=length//3
            if length-t3*3==1:
                t3-=1
            t2=(length-t3*3)/2
        return 3**t3*2**t2
        # write code here


编辑于 2020-06-16 10:05:33 回复(0)
Python
Kuriyamaaa头像 Kuriyamaaa 
# -*- coding:utf-8 -*-

from math import log, exp


class Solution:
    def chengji(self, list1,n):
        if list1[0] == int(list1[0]):
            p = 1
            for i in range(len(list1)):
                p = p * list1[i]
            return p
        else:
            p = 1
            yushu = n%len(list1)
            for i in range(len(list1)):
                list1[i]=int(list1[i])
            for i in range(yushu):
                list1[i] = list1[i] + 1
            for i in range(len(list1)):
                p = p * list1[i]
            return p

    def cutRope(self, number):
        n = number
        m = exp(log(n) - 1)
        intm=int(m)

        if intm <= 1:
            a = n / 2.0
            if a == int(a):
                return int(a * a)
            else:

                return int((a - 0.5) * (a + 0.5))

        if intm >= 2:
            if m == intm:
                l1 = [n / m for i in range(intm)]
                return int(self.chengji(l1))
            else:
                m = intm
                mm = m + 1
                
                ji = []
                l1 = [n / float(m) for i in range(m)]
                ji.append(self.chengji(l1,n))
                l1 = [n / float(mm) for i in range(mm)]
                ji.append(self.chengji(l1,n))
                if m>=3:
                    mmm=m-1
                    l1 = [n / mmm for i in range(mmm)]
                    ji.append(self.chengji(l1, n))
                return int(max(ji))

    # l1=[n/m for i in range(int(m))]
    # return int((n/float(m+1))**(m+1))

    # write code here
加float()的原因在于python2的真除运算
python3也可以通过

class Solution:
    def cutRope(self, n):
        if n==2:
            return 1
        if n==3:
            return 2
        if n==4:
            return 4
        numsof3=n//3
        modof3=n%3
        if modof3==0:
            return int((3**numsof3)%(1e9+7))
        if modof3==1:
            return int(((3**(numsof3-1))*4)%(1e9+7))
        if modof3==2:
            return int(((3**(numsof3))*2)%(1e9+7))



编辑于 2020-05-28 20:56:46 回复(0)
Python
ssssxt头像 ssssxt 
class Solution:
    def cutRope(self, n):
        # write code here
        dp = [1] * (n + 1)
        for i in range(2, n+1):
            for j in range(1, i):
                dp[i] = max(dp[i], dp[i-j]*j, j*(i-j))
        return dp[n]

发表于 2020-05-24 19:13:26 回复(0)
Python
橘子汽水超人2号头像 橘子汽水超人2号

Python Solution

贪心算法 

# -*- coding:utf-8 -*-
class Solution:    #  贪心算法
    def cutRope(self, number):
        # write code here
        res = 1
        while number>4:
            res*=3
            number-=3
        return res*number if res>1 else 2**(number-2)

动态规划算法： 

# -*- coding:utf-8 -*-
class Solution:  # 动态规划算法
    def cutRope(self, number):
        # write code here
        res=[0]*(number+1)
        for k in range(2,number+1):
            i = 1
            while i <= k-i:
                left = i if i>res[i] else res[i]	# 这两步其实是要判断的
                right = k-i if k-i>res[k-i] else res[k-i]
                tmp = left*right 
                res[k]=tmp if tmp > res[k] else res[k]
                i += 1
        return res[number]




编辑于 2020-05-19 15:00:43 回复(0)
Python
byte~头像 byte~ 
class Solution:
    def cutRope(self, number):
        # write code here
        def numsmup(num,k):
            # 快手笔试灵感,一个数截k段,求最大乘积,平均最大
            s = num // k
            d = num % k
            return (pow(s,k-d)*pow(s+1,d))
        maxnum = 1
        for k in range(2,(number+3)//2):
3                    # 遍历到一半
            if maxnum < numsmup(number,k):
                maxnum = numsmup(number,k)
        return  maxnum

numsmup函数

编辑于 2020-03-31 11:43:30 回复(0)
Python
llfgo4it头像 llfgo4it 
# -*- coding:utf-8 -*-
class Solution:
    def cutRope(self, number):
        # write code here
        if number <= 0:
            return 0
        return self.max(number)

    def max(self, num):
        if num == 1:
            return 1
        mNum = 1
        for k in range(1, num/ 2+1):
            t = self.max(k) * self.max(num - k)
            big = t if t>k*(num-k) else k*(num-k)
            mNum = big if mNum< big else mNum
        return mNum
其实就是一个公式：f(n) =max{ f(1)*f(n-1), f(2)*f(n-2), ..., f(k)*f(n-k), k*(n-k)} 这里引入k*(n-k) 是不再为n=1,2,3等特殊情况做区分。另外，因为 f(k)*f(n-k) 与 f(n-k)*f(k)结果相同，故只计算一半就行，即 0<k <n/2
编辑于 2020-03-21 01:20:01 回复(0)
Python
youGuess-Coder头像 youGuess-Coder
大家都是用动态规划做的好像。
贴一个我的代码。
思路：
第一反应觉得应该是剪的长度越平均乘积会越大。（最近在看行测-数量关系）
然后就尝试，先等分，多的长度分到等分的长度上。之后求乘积。
至于到底分几段，就遍历（这点可能不高效吧），当乘积开始减小的时候，就退出循环，输出当前最大值。 
class Solution:
    def cutRope(self, number):
        # write code here
        if(number == 0) | (number == 1):
            return 0
        if(number == 2):
            return 1
        
        max_mutiply = 1
        flag = False
        for i in range(2, number):
            shang = number / i
            yu = number % i
            table = [shang for m in range(0, i)]
            for j in range(0, yu):
                table[j] += 1
            mutiply = 1
            for each in table:
                mutiply *= each
            if(mutiply > max_mutiply):
                max_mutiply = mutiply
                flag = True
            else:
                if(flag == True):
                    break
        return max_mutiply


发表于 2020-03-12 23:15:10 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

剪绳子

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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