当前位置：首页 > 文章列表 > Golang > Go问答 > Go 语言的 Bridge 和 Torch 问题涉及"n"个人

Go 语言的 Bridge 和 Torch 问题涉及"n"个人

来源：stackoverflow 2024-03-10 19:27:27 0浏览收藏

各位小伙伴们，大家好呀！看看今天我又给各位带来了什么文章？本文标题是《Go 语言的 Bridge 和 Torch 问题涉及"n"个人》，很明显是关于Golang的文章哈哈哈，其中内容主要会涉及到等等，如果能帮到你，觉得很不错的话，欢迎各位多多点评和分享！

问题内容

问题：给定一个正不同整数数组，表示“n”个人的穿越时间。这‘n’个人站在桥的一侧。桥一次最多可容纳两人。两个人过桥时，必须以较慢的人的速度行走。求所有人都能过桥的最短总时间。

我无法找到如何为“n”个人扩展此模式的模式。但不知何故，我设法找到了有 4 个人的箱子。有人可以帮我弄这个吗。我是 golang 新手，我遇到了这个问题。

package main

import (
    "fmt"
    "io/ioutil"
    "log"
    "os"
    "sort"

    "gopkg.in/yaml.v2"
)

type conf struct {
    person []map[string]float32 `yaml:"person"`
}

func (c *conf) getconf() *conf {
    filename := os.args[1]                     // taking file input
    yamlfile, err := ioutil.readfile(filename) // yaml parse
    if err != nil {
        log.printf("yamlfile.get err   #%v ", err)
    }
    err = yaml.unmarshal(yamlfile, c)
    if err != nil {
        log.fatalf("unmarshal: %v", err)
    }
    return c
}

func main() {
    var c conf  // object of struct conf
    c.getconf() // calling getconf function
    // sorting the current conf map
    n := map[float32][]string{} // map to store current conf map
    var a []float32             // store values from conf map
    for k, v := range c.person {
        v := float32(v)
        fmt.println(k, v)
        n[v] = append(n[v], k)
    }
    for k := range n {
        a = append(a, k)
    }
    // converting float32 as float64 in order to sort the values in conf map
    float32asfloat64values := make([]float64, len(a))
    for i, val := range a {
        float32asfloat64values[i] = float64(val)
    }
    sort.float64s(float32asfloat64values)
    for i, val := range float32asfloat64values {
        a[i] = float32(val)
    }
    var time float32
    fmt.printf("\n%v\n", a)
    for _, k := range a {
        min1 := a[0]
        min2 := a[1]
        min3 := a[2]
        for _, s := range n[k] {
            //debug:
            fmt.printf("%s, %g\n", s, k)
            if len(a) > 3 {
                time = (3 * min2) + min1 + a[3] //formula for minimum time in case of 4 people
            } else if len(a) == 3 {
                time = min1 + min2 + min3
            } else {
                fmt.println("enter valid arguments in config.yaml")
            }
        }
    }
    fmt.printf("minimum time taken to cross the bridge is:\t%g\n", time)
}

演示：https://play.golang.org/p/obtva8gk0mg

config.yaml 是：

person:
  person_1: 2
  person_2: 1
  person_3: 5
  person_4: 8
  person_5: 9

可以将其运行为：“go run main.go config.yaml”。我的情况是，此 yaml 中可能有 4,5 或“n”个人。那么在给定的限制条件下，他们过桥的最短时间是多少。

解决方案

我认为最初的问题比所述问题更有趣（是的，“桥和火炬”问题中必须有一个火炬！）。

例如，根据维基百科的描述，

夜里，四人来到一条河边。有一座狭窄的桥，但一次只能容纳两个人。他们有一支火把，因为是晚上，过桥时必须使用火把。 a人1分钟过桥，b人2分钟过桥，c人5分钟过桥，d人8分钟过桥。两个人一起过桥时，必须以较慢的人的速度行走。问题是，如果火炬只持续15分钟，他们能全部过桥吗？

当然，在我们的例子中，有 n 个人而不是只有四个人，他们过桥所需的时间各不相同，但故事的其余部分是相同的。

这里是实现：

import (
    "fmt"
    "sort"
)

func mincrossingtime(x []int) int {
    if len(x) == 1 {
        return x[0]
    }

    sort.ints(x)

    t := 0
    a, b := x[0], x[1]
    x = x[2:]

    for len(x) >= 2 {
        n := len(x)
        c, d := x[n-2], x[n-1]
        x = x[:n-2]

        t1 := 2*b + a + d
        t2 := d + c + 2*a
        if t1 < t2 {
            t += t1
        } else {
            t += t2
        }
    }

    if len(x) == 1 {
        c := x[0]
        t += a + b + c
    } else {
        t += b
    }
    return t
}

func main() {
    x1 := []int{1, 2, 5, 8}
    fmt.printf("x = %x, time = %d\n", x1, mincrossingtime(x1))
    x2 := []int{3, 8, 1, 6, 2, 9}
    fmt.printf("x = %x, time = %d\n", x2, mincrossingtime(x2))
}

输出：

x = [1 2 5 8], time = 15
x = [1 2 3 6 8 9], time = 27

注意：第一个示例 [1 2 5 8] 直接来自维基百科，所以答案是肯定的，他们可以在 15 分钟内穿过

关键思想：

定义：

设 x = [x1,x2,...,xn] 为交叉时间的排序数组，其中 x1 最快，xn 最慢
我们将 xi 和 xj 两人过马路表示为 {xi,xj}，将 xk 一个人过马路表示为 {xk}，其中 +{...} 表示沿所需方向的过马路，-{.. .}相反的方向

逻辑：

如果 n < 4 问题就很简单：
- n = 1 => t = x1 (+{x1})
- n = 2 => t = x2 (+{x1,x2})
- n = 3 => t = x1 + x2 + x3 (+{x1,x2} -{x1} + {x1,x3})
如果 n >= 4，请考虑以下问题：如何让两个最慢的人（并且只有他们）过桥并在最短的时间内将火炬带回来。有两种“好”的方法可以做到这一点，随着时间的推移 t1 = x1 + 2*x2 + xn (+{x1,x2} -{x1} +{x[n-1],xn} -{x2}) 和 t2 = 2*x1 + x[n-1] + xn (+{x1,x[n-1]} -{x1} +{x1,xn} -{x1})，所以我们选择最好的（最小值）在这两个中
现在最慢的两个人已经过了桥，火炬在它开始的同一侧，所以我们剩下 x' = [x1, x2, ..., x[n-2 ]]，可以通过应用相同的逻辑并对交叉时间求和来迭代求解

额外：

有关数学证明和更多上下文，请参阅例如https://page.mi.fu-berlin.de/rote/Papers/pdf/Crossing+the+bridge+at+night.pdf
用不同编程语言编写高尔夫解决方案：https://codegolf.stackexchange.com/questions/75615/the-bridge-and-torch-problem

你的算法看起来很复杂。

例如，

package main

import (
    "fmt"
    "sort"
)

func mincrossingtime(people []int) int {
    sort.slice(people, func(i, j int) bool {
        return people[i] > people[j]
    })
    min := 0
    for i := 0; i < len(people); i += 2 {
        min += people[i]
    }
    return min
}

func main() {
    people := []int{2, 1, 5, 8, 9}
    fmt.println(len(people), people)
    crossingtime := mincrossingtime(people)
    fmt.println(len(people), people)
    fmt.println(crossingtime)
}

演示：https://play.golang.org/p/pXdGcinwxr-

输出：