回帖精选:游戏常用算法问题——小明过桥问题

精选原贴回复作者:laojke

小明家必须要过一座桥。小明过桥最快要1秒,小明的弟弟最快要3秒,小明的爸爸最快要6秒,小明的妈妈最快要8秒,小明的爷爷最快要12秒。每次此桥最多可过两人,而过桥的速度依过桥最慢者而定。过桥时候是黑夜,所以必须有手电筒,小明家只有一个手电筒,而且手电筒的电池只剩30秒就将耗尽。小明一家该如何过桥,请写出详细过程。

要求:go语言实现,并带测试代码及结果


laojke:

  1package main
  2
  3import "fmt"
  4
  5func main() {
  6
  7        m := make(map[string]int)
  8
  9        m["小明"] = 1
 10        m["小明弟弟"] = 3
 11        m["小明爷爷"] = 12
 12        m["小明爸爸"] = 6
 13        m["小明妈妈"] = 8
 14
 15        sortMap(m)
 16}
 17
 18//排序
 19func sortMap(mp map[string]int) {
 20
 21        var newMp = make([]int, 0)
 22        var newMpKey = make([]string, 0)
 23
 24        for k, v := range mp {
 25                newMp = append(newMp, v)
 26                newMpKey = append(newMpKey, k)
 27        }
 28
 29        lens := len(newMp)
 30        for i := 0; i < lens; i++ {
 31                for j := i + 1; j < lens; j++ {
 32                        if newMp[i] > newMp[j] {
 33                                temp := newMp[i]
 34                                newMp[i] = newMp[j]
 35                                newMp[j] = temp
 36
 37                                temp2 := newMpKey[i]
 38                                newMpKey[i] = newMpKey[j]
 39                                newMpKey[j] = temp2
 40                        }
 41                }
 42        }
 43
 44        for i := 0; i < len(newMpKey); i++ {
 45                fmt.Println(newMpKey[i], newMp[i])
 46        }
 47
 48        fmt.Println("================排序完成,开始送人====================")
 49
 50        /*
 51                1、先把1号和2号送过去,
 52                2、1号回来
 53                3、然后把时间最长4、5位的送过去,
 54                4、2号回来
 55                5、1号和2号过去,
 56                6、1号回来
 57                7、1号和3号过去
 58        */
 59
 60        total(newMp, newMpKey)
 61
 62}
 63
 64func total(valueSlice []int, keySlice []string) {
 65        var sum int = 0
 66        var lens int = len(valueSlice)
 67
 68        //1、先把1号和2号送过去,
 69        sum += valueSlice[1]
 70        fmt.Printf("%s送%s(%d)总耗时%d\n", keySlice[0], keySlice[1], valueSlice[1], sum)
 71
 72        //把1号送回
 73        sum += valueSlice[0]
 74        fmt.Printf("%s(%d)回总耗时%d\n", keySlice[0], valueSlice[0], sum)
 75
 76        //2、把时间最长4、5位的送过去,
 77        sum += valueSlice[lens-1]
 78        fmt.Printf("%s送%s(%d)过去总耗时%d\n", keySlice[lens-2], keySlice[lens-1], valueSlice[lens-1], sum)
 79        //3、把2号送回去
 80        sum += valueSlice[1]
 81        fmt.Printf("%s(%d)回去总耗时%d\n", keySlice[1], valueSlice[1], sum)
 82
 83        //var zuida int = 0
 84
 85        //然后1号把剩余的都送过去
 86
 87        for j := 1; j < lens-2; j++ {
 88                sum += valueSlice[j]
 89                fmt.Printf("%s把%s(%d)送过去总耗时%d\n", keySlice[0], keySlice[j], valueSlice[j], sum)
 90
 91                if j == lens-3 {
 92
 93                        break
 94                }
 95                sum += valueSlice[0]
 96                fmt.Printf("小明(%d)回总耗时%d\n", valueSlice[0], sum)
 97        }
 98
 99        fmt.Println("送完了总耗时", sum)
100
101}
102
103
104网上搜索搜索资料,终于搞好了 ,

测试结果 小明 1 小明弟弟 3 小明爸爸 6 小明妈妈 8 小明爷爷 12 ================排序完成,开始送人==================== 小明送小明弟弟(3)总耗时3 小明(1)回总耗时4 小明妈妈送小明爷爷(12)过去总耗时16 小明弟弟(3)回去总耗时19 小明把小明弟弟(3)送过去总耗时22 小明(1)回总耗时23 小明把小明爸爸(6)送过去总耗时29 送完了总耗时 29


版权申明:内容来源网络,版权归原创者所有。除非无法确认,我们都会标明作者及出处,如有侵权烦请告知,我们会立即删除并表示歉意。谢谢。

原文发布于微信公众号 - Golang语言社区(Golangweb)

原文发表时间:2019-05-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券