剪绳子

题目描述

---

给你一根长度为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 <= 60）

输出描述:

输出答案。

package test;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
       Scanner in=new Scanner(System.in);
       System.out.println("请输入绳长：");
       int length=in.nextInt();
       //length=2,1*1
       //length=3,1*2
       //length=4,2*2|3*1
       //length=5,1*4|1*2*2|1*3*1|2*3
       //length=6,1*5|1*2*3|2*2*2|3*3
       //当length>=4之后，只有2,3，因为2*2=4,2*3>5,3*3>6,3*2*2>7,2*3*3>8,3*3*3>9
       //2的数目肯定小于3个---》2*2*2<3*3,其余均为3
     if(length==2)
         System.out.println(1);
    if(length==3)
        System.out.println(2);
    if(length%3==1)
        System.out.println(Math.pow(3, length/3-1)*2*2);
        else
            if(length%3==0)
                 System.out.println(Math.pow(3, length/3));
            else
                System.out.println(Math.pow(3, length/3)*2);


            }

}

自己的不足：

（1）看到题，无从着手。

（2）做题时，当length为length%2==1时，输出结果错误，未仔细查看3的个数，依旧将其写成：Math.pow(3,length/3)*2*2，导致每次都多乘一个3

（3）当我读完题时一直在想，不清楚分几段，也不清楚每段多少，还要求最佳。一开始的方向就错了。

以后改进：

（1）当看到题无思路可解时，可根据题意，写出几个例子，按照你的思维先去计算，然后在站到计算机的角度去设计实用算法。

牛客其他人的解答：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        System.out.println(cutRope(n));
    }
   private static int cutRope(int target) {
        int a = 0;
        int c = 0;
        int maxValue = 2;

        //输入参数范围验证
//        if (2 > target || 60 < target) {
//            return -1;
//        }
       if (target == 2) {
           return 1;
       }
       if (target == 3) {
           return 2;
       }
       if (target % 3 == 0) {
            maxValue = (int)Math.pow(3, target / 3);
       } else{
            a = target - 2;
            c = a % 3;

            maxValue = maxValue * (int)Math.pow(3, a / 3);
            if (0 != c) {
                maxValue = maxValue * c;
            }
       }


        return maxValue;
    }
}

package test;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
      Scanner sc=new Scanner(System.in);
      System.out.println("请输入绳长");
      int length=sc.nextInt();
      int[] m=new int[length+1];
      //length=0|1----0
      //length=2-----2
      //length=3-----3
      //length=4-----4
      for(int i=2;i<5;i++) {
          m[i]=i;
      }
      //length=5----->1*4|2*3
      //length=6---->1*5|2*4|3*3
      //length=7--->1*6--1*3*3|2*5--->2*2*3|3*4--->3*2*2
      //length=8----1*7-->1*12|2*6-->2*3*3|3*5--->3*2*3|4*4
      for(int i=5;i<length+1;i++) {
          for(int j=1;j<=i/2;j++) {
              int temp=m[j]*m[i-j];
              m[i]=(m[i]<temp)?temp:m[i];
          }
      }
      System.out.println(m[length]);
    }


}

第二种做法，在我思考的时候，就是按那个步骤来的，但却没把他转化成编程语言。