Golang算法之田忌赛马问题实现方法分析

本文实例讲述了golang算法之田忌赛马问题实现方法。分享给大家供大家参考，具体如下：

【田忌赛马问题】

输入：

输入有多组测试数据。 每组测试数据包括3行：
第一行输入n(1≤n≤1000)，表示马的数量。
第二行有n个整型数字，即渊子的n匹马的速度（数字大表示速度快）。
第三行有n个整型数字，即对手的n匹马的速度。
当n为0时退出。

输出：

若通过聪明的你精心安排，如果能赢得比赛（赢的次数大于比赛总次数的一半），那么输出“yes”。 否则输出“no”。

样例输入

5
2 3 3 4 5
1 2 3 4 5
4
2 2 1 2
2 2 3 1
0

样例输出

yes
no

代码实现（golang）：

package huawei
//date：2015-8-14 15:43:11
import (
    "fmt"
    "io/ioutil"
    "sort"
    "strings"
)
//思路：用自己最强的(半数+1)个马和对手最弱的(半数+1)个马比赛
func test11base() {
    data, err := ioutil.readfile("datafiles/huawei_test11.txt")
    checkerror(err, "reading file")
    strs := strings.split(string(data), "\n")
    index := 0
    for {
        count := strs[index]
        if count == "0" {
            break
        }
        teama := converttointslice(strings.fields(strs[index+1]))
        teamb := converttointslice(strings.fields(strs[index+2]))
        if canwin(teama, teamb) {
            fmt.println("yes")
        } else {
            fmt.println("no")
        }
        index += 3
    }
}
//判断teama是否能够胜利
func canwin(teama []int, teamb []int) bool {
    sort.ints(teama)
    sort.ints(teamb)
    length := len(teama)
    trycount := length/2 + 1
    for i := 0; i < trycount; i++ {
        //a组最强的一半
        speeda := teama[length-(trycount-i)]
        //b组最弱的一半
        speedb := teamb[i]
        if speeda <= speedb {
            return false
        }
    }
    return true
}

希望本文所述对大家go语言程序设计有所帮助。