编程题 【问题描述】 给你一根长度为n的绳子，请把

class Solution{

public:

    int get_max(int n){

        if(n<1)

            return 0;

        // 特殊情况

        if(n==2)  return 1;

        if(n==3 ) return 2;

        // 用3来进行分割可以使得乘积变得最大

        // 要分析特征情况：比如n=4的时候，就不能分割成1*3，而必须是2*2

        int sum = 1;

        while(n>4){

                n -= 3;

                sum *= 3;

            }

        // 这里包括最后n=2和n=4,结果都是乘以自身最大

        return sum*n;

    }

};

public int integerBreak(int n) {
if (n == 2) return 1;
if (n == 3) return 2;
int ans = 1;
while (n > 4) {
ans *= 3;
n -= 3;
}
return ans * n;
}

package Wangben;

import java.util.Scanner;

public class Main {
public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	int n=sc.nextInt();
	int m=n/3;
	if( n % 3 ==0){
		System.out.println(Math.pow(3, n));
	} else if(n % 3 ==1){
		System.out.println(Math.pow(3, m-1)*4);
	}else {
		System.out.println(Math.pow(3, m) * (n % 3));
	}
}
}

class Solution:
    def maxProductAfterCutting(self, n):
        # write code here
        if n<=3:
            return 1*(n-1)
        if n%3==1:
            num3=n//3-1
            num2=(n-3*num3)//2
        elif n%3==2:
            num3=n//3
            num2=(n-3*num3)//2
        else:
            num3=n//3
            num2=0
        return pow(3,num3)*pow(2,num2)

def cut(num):
    nsqrt = int(num // 2) + 1 # 向上取整   
​    mmax = 1  for x in range(2, nsqrt):
        y = num - x 
​        if y not in multis.keys():
            multis[y] = cut(y)
        mx = max(multis[x], x)
        my = max(multis[y], y)
        temp = mx * my 
​        if temp > mmax:
            mmax = temp 
​    return mmax 
​    pass
​   
​if __name__ == '__main__': 
​    # N = int(input().strip())  
​    N = 9   
​    if N < 2: 
​        print('N must be not less than 2!')
    multis = {2: 1, 3: 2}
    mmax = cut(N) 
​    print(mmax)  
​    pass 

直接求解法，递归方式：

每一段长度都根据已有的长度进行划分和计算，比如：

绳长为2米时，最大乘积为1，记为multis[2]=1；此时的拆分形式为1+1；

绳长为3米时，最大乘积为2；记为multis[3]=2；此时的拆分形式为1+2；

绳长为4米时，最大乘积为4；

其中4可拆分为1+3，2+2，3+1；

以1+3为例，因为multi[3]multis[3]，此时乘积为1x3=3）；

按照这种方式，分别计算每种拆分方式下的乘积，直到拆分组合N/2+1与N-(N/2+1)；

然后找出其中的最大值，即为当前绳长下的最大乘积。

#include<iostream>
#include<math.h>
using namespace std;
int x(int m)
{
    int a=2,k=m;
    while( k < pow( m / a , a-1 ) * ( m - m/a * (a-1) ) )
    {
        k = pow( m / a , a-1 ) * ( m - m/a * (a-1) ) ;
        a++;    
    }
    for(int i=1;i<a-1;i++)
    printf("%d*",m/(a-1));
    printf("%d=", m - m/ (a-1) * (a-2) );
    return k;
}
int main()
{
    int m;
    cin>>m;
    cout<<x(m)<<endl;    
} 

class Solution:
    def maxProductAfterCutting(self, n):
        # write code here
        if n < 2 :
            return 0
        elif n == 2:
            return 1
        # elif n == 3:
        #     return 2
        max_list = [0,1,2]
        for i in range(3,n+1):
            if i < n :
                max = i
            else:
                max = 0
            for j in range(1,i//2+1):
                tmp = max_list[j]*max_list[i-j]
                if tmp > max:
                    max = tmp
            max_list.append(max)
        return max_list[n]