原题
一根绳子,长度为n米。将其切成几段,每一段的长度都是整数。请给出一种切法,使得切成的各段绳子之间的乘积是最大的。注意,最少要切一下的。
问题分析:由经验可得,n的拆分有三种情况
(1)n<4时,拆分的最大乘积比原来小,2拆分成(1,1,)乘积为1,3拆分成(1,2)乘积为2;
(2)n=4时,拆分最大乘积与原来相等,4拆分成(2,2),乘积为4,;
(3)n>4时,拆分后最大乘积比原来大,如10拆分成(5,5)乘积为25,若拆分成(4,6)乘积为24,综合其他情况可得,拆分的两个数的差越小,乘积就越大,所以若n为偶数就拆分成(n/2,n/2),若n为奇数就拆分成(n/2,n/2+1)
解决方案:(1)对于长度为n的绳子,若n>=4,将n拆分成差尽可能小的两段a,b,再分别对a,b进行拆分,若任意一段小于4则不再拆分。
(2)若n<4,因为题目要求至少要切一下,所以当n=2时,乘积为1,当n=3时,乘积为2;
代码:
优化方案:由问题的分析可得,所有大于4的绳子经过递归式拆分之后最终都变成长度为2或3的小绳子,可得n=2*x+3*y,且y要尽可能大,总乘积为2^x*3^y,所以:
若n%3==2,y=n/3,x=1;
若n%3==1,剩下的不够被2整除,应该再抽出一个3,y=n/3-1,x=2;
若n%3==0,y=n/3,x=0