第9课:算法实例

本节列出几个简单的go语言算法

1.求数组平均值
package main
import (
    "fmt"
)
func main() {
    sum := 0.0
    var avg float64
    xs := []float64{1, 2, 3, 4, 5, 6}
    switch len(xs) {
    case 0:
        avg = 0
    default:
        for _, v := range xs {//下划线表示值舍去
            sum += v
        }
        avg = sum / float64(len(xs))
    }
    fmt.Println(avg)
}

2.经典的冒泡排序
package main
import (
    "fmt"
)
var (
    array = []int{3, 6, 1, 8, 5}
)

func main() {
    for _, v := range sort(array) {
        fmt.Println(v)
    }
}

func sort(array []int) []int {
    for i := 0; i < len(array); i++ {
        for j := 0; j < len(array)-i-1; j++ {
            if array[j] < array[j+1] {
                array[j], array[j+1] = array[j+1], array[j]
            }
        }
    }
    return array
}

3.什么?上面的算法太简单?那来个复杂的
甜品店godeye.org切蛋糕问题
小Y最近在甜品店godeye.org工作,其工作是切蛋糕。已知第i位顾客进店时间,以及购买蛋糕大小,现在有n个顾客来购买蛋糕,并且每个顾客有一个到达的时间,以及需要买的蛋糕的长度ai。由于小Y每次只能服务一个顾客,顾客如果进店没有服务员立刻为他服务,他将离开,所以对于相冲突的顾客没有办法提供服务。问小Y最多能为多少位顾客提供服务

分析:
涉及问题一:大小为n的蛋糕需要多长时间切成单位长度?
f(x)=x*(n-x) 绘制函数草图可以得到:x=1时得到最小值,也就是说每次1单位1单位的切用数学归纳法证明上述的解得到的最终和解也是最小的

涉及问题二:已知各位顾客的进店时间和购买蛋糕大小,如何选出最佳服务对象?
这个问题至少可以使用贪心策略来解决,似乎包含了动态规划

package main  
  
import (  
    "fmt"  
)  
  
/*求最小服务时长,每次1单位1单位的切,得到的是最小解*/  
func smin(n int32) int32 {  
    if n&1 == 0 {  
        return (n / 2) * (n - 1)  
    }  
    return (n - 1) / 2 * n  
}  
  
/*求每个顾客的时间*/  
func serverTime(s, lenght []int32, maxLen int32) {  
    for i := range lenght {  
        s[i] = smin(lenght[i])  
    }  
}  
  
/*求二者最大值*/  
func maxInt32(a, b int32) int32 {  
    if a > b {  
        return a  
    }  
    return b  
}  
  
func dptz(i, t int32, r, s []int32) int32 {  
    if i == 0 {  
        if t >= r[0]+s[0] {  
            return 1  
        }  
        return 0  
    }  
    if t >= r[i]+s[i] {  
        return maxInt32(dptz(i-1, r[i], r, s)+1, dptz(i-1, t, r, s))  
    }  
    return dptz(i-1, t, r, s)  
}  
  
/*求最后结束时间*/  
func endTime(r, s []int32) int32 {  
    var max, tmp int32 = 0, 0  
    for i := range r {  
        tmp = r[i] + s[i]  
        if max < tmp {  
            max = tmp  
        }  
    }  
    return max  
}  
  
func main() {  
    //蛋糕长度、先来后到的时间和服务时间  
    length := []int32{2, 2, 3, 4}  
    r := []int32{5, 5, 6, 10}  
    s := make([]int32, 4)  
    serverTime(s, length, 4)  
    fmt.Println(dptz(3, endTime(r, s), r, s))  
}