数学09--剪绳子

数学09--剪绳子-jz67

• ​​题目概述​​
• ​​解析&参考答案​​
• ​​注意事项​​
• ​​说明​​

题目概述

• 算法说明
  给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],…,k[m]。请问k[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
  输入描述:
  输入一个数n，意义见题面。（2 <= n <= 60）
  给一个长度为n的绳子，最多剪m刀。
• 测试用例
  输入： 8
  输出： 18

解析&参考答案

• 解析
  使用贪婪算法，当n>=5的时候，尽可能多地剪长度为3的绳子；当剩下的绳子长度为4的时候，剪为两段长度均为2的绳子。
• 参考答案

vim jz67.go
package main

import (
"fmt"
"math"
)

func CutRope(number int) int {
if number < 2 {
return 0
}
if number == 2 {
return 1
}
if number == 3 {
return 2
}
times3 := number / 3
times2 := 0
if number-times3*3 == 1 {
times3--
}
times2 = (number - times3*3) / 2
if times2 > 0 {
return int(math.Pow(float64(3), float64(times3)) * math.Pow(float64(2), float64(times2)))
} else {
return int(math.Pow(float64(3), float64(times3)))
}
}

func main() {
num := 8
ret := CutRope(num)
fmt.Println(ret)
}

vim jz67_test.go
package main

import "testing"

func TestCutRope(t *testing.T) {
tests := []struct{ num, result int }{
{8, 18},
{15, 243},
}
for _, tt := range tests {
if actual := CutRope(tt.num); actual != tt.result {
t.Errorf("num %d got %d, expected %d", tt.num, CutRope(tt.num), tt.result)
}
}
}

注意事项

to add

说明

当前使用 go1.15.8

参考​​牛客网--剑指offer​​ 标题中jzn(n为具体数字)代表牛客网剑指offer系列第n号题目，例如 jz01 代表牛客网剑指offer中01号题目。

注意!!!

• 笔者最近在学习 golang，因此趁机通过数据结构和算法来进一步熟悉下go语言
• 当前算法主要来源于剑指 offer，后续会进一步补充 LeetCode 上重要算法，以及一些经典算法
• 此处答案仅为参考，不一定是最优解，欢迎感兴趣的读者在评论区提供更优解