和积最大

1 剪绳子

问题描述

  • 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m - 1] 。请问 k[0]k[1]…*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

  • 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

链接

问题分析

问题分类

  • 贪心思想
  • 数值问题
  • 无数据结构

策略选择

  • n尽可能多的包含因子3

算法设计

  1. 如果 n == 2，返回1，如果 n == 3，返回2，两个可以合并成n小于4的时候返回n - 1
  2. 如果 n == 4，返回4
  3. 如果 n > 4，分成尽可能多的长度为3的小段，每次循环长度n减去3，乘积res乘以3；最后返回时乘以小于等于4的最后一小段；每次乘法操作后记得取余就行
  4. 以上2和3可以合并

算法分析

  • 时间复杂度O(logn)
  • 空间复杂度O(1)

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
int cuttingRope1(int n) {
    //果然是数学问题
    // 这东西由3和2的组成。3越多值越大。也就是存在三种情况。
    // n能被3整除。则全为3
    // n被3整除余数为1，则减掉两个2后，全为3
    // n被3整除余2，减掉1个2后，全为3
    if(n==2){
        return 1;
    }
    if(n==3){
        return 2;
    }

    if(n%3==0){
        return multi(3,n/3);
    }
    else if(n%3==1){
        return (4*multi(3,(n-4)/3))%1000000007;
    }
    else if(n%3==2){
        return (2*multi(3,(n-2)/3))%1000000007;
    }
    return 0;
}
//数学类题目。使用快速幂
long long multi(long long x,int n){
    if(n == 0) return 1;
    if(n == 1) return x;
    long long half = multi(x, n / 2);
    long long mod = multi(x, n % 2);
    return (half * half * mod)%1000000007;
}

int cuttingRope(int n) {
    if(n < 4){
        return n - 1;
    }
    long res = 1;
    while(n > 4){
        res  = res * 3 % 1000000007;
        n -= 3;
    }
    return (int) (res * n % 1000000007);
}