数学09--剪绳子

哈客cc lv.2

发布时间：2022-09-23 20:40:20 274

数学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 上重要算法，以及一些经典算法
此处答案仅为参考，不一定是最优解，欢迎感兴趣的读者在评论区提供更优解

文章来源： https://blog.51cto.com/u_15767560/5628780

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。