询问:经典的中学算法竞赛试题

息阳

    有三个没有刻度的桶，容量分别为3升、5升、8升。现在8升的桶是满的，你可以将水在桶中倒来倒去。例如，首先8->3，那么8升桶内将会有5升水，3升桶会被装满；然后3->5，那么3升桶将被倒空，5升桶内将有3升水。你的目标是平分这8升水，即使5升桶和8升桶内均有4升水。
    本人使用遍历树,但是速度不是最好.
    高手给出代码(直接贴关键代码即可,不需要示例),速度越快越好.貌似使用深度优先搜索可以搞定.

执着小子

这种东西真接算还行，编程就不会了

Canbitwell

我写了个BFS，主要是怕无限搜索下去……
这个结果包含最少步数，
如果数据就是这三个桶的话还很好，多了的话队列就满了……所以lz看看能不能剪枝，加上个（已经有了一个就是目标桶不满）
    Dim av As Integer() = New Integer() {8, 5, 3}

    Structure state
        Public v As Integer()

        Public depth As Integer

        Public Sub New(ByRef s As state)
            v = New Integer(2) {}
            v(0) = s.v(0)
            v(1) = s.v(1)
            v(2) = s.v(2)
            depth = s.depth + 1
        End Sub

        ''' <summary>
        ''' a向b中倒
        ''' </summary>
        Public Function p(ByVal a As Integer, ByVal b As Integer) As Boolean
            Dim m As Integer = av(b) - v(b)

            If m > v(a) Then
                m = v(a)
            End If

            v(a) -= m
            v(b) += m

            Return m > 0
        End Function
    End Structure

    Function check(ByRef s As state) As Boolean
        Return (s.v(0) = 4 And s.v(1) = 4) Or (s.v(0) = 3 And s.v(1) = 3 And s.v(2) = 3)
    End Function

    Sub Main()
        Dim q As New Queue(Of state)(100000)

        Dim s1 As state
        s1.v = New Integer(2) {}
        s1.v(0) = 8
        s1.v(1) = 0
        s1.v(2) = 0

        q.Enqueue(s1)

        Dim found As Boolean
        While (q.Count > 0 And Not found)
            Dim cs As state = q.Dequeue

            If check(cs) Then
                Console.WriteLine(cs.v(0))
                Console.WriteLine(cs.v(1))
                Console.WriteLine(cs.v(2))
                Console.WriteLine(cs.depth.ToString + "步")
                found = True
            Else
                For i As Integer = 0 To 2
                    For j As Integer = 0 To 2
                        Dim ns As New state(cs)

                        If ns.p(i, j) Then

                            q.Enqueue(ns)
                        End If
                    Next
                Next
            End If
        End While
        Console.ReadKey()
    End Sub

Miu.C

雷顿教授与XXXXX里经常见到。

ddar

代码懒得写了.在纸上画了几次...就说说思想算了.
先写几个倒水过程(X倒Y,Z;Y倒X,Z)
再写个检测过程
到水前,倒水源为空;倒水后,检测是否与之前作过的步骤重复;倒的目标为满,的步骤都不列入成功步骤.不继续往下分步.

弄2个数组.
基本过程的结果:

瓶(100)    步骤(100)
008         A
305         AA
053         AB
350         AAA
035         AAB
323         ABA
332         AABA
026         ABAA
152         AABAA
206         ABAAA
107         AABAAA
251         ABAAAA
017         AABAAAA
341         ABAAAAA
314         AABAAAAA
044         ABAAAAAA
044         AABAAAAAA


再写个过程.取得

最块为7步
008     A
053     AB
323     ABA
026     ABAA
206     ABAAA
251     ABAAAA
341     ABAAAAA
044     ABAAAAAA

sandy_zc_1

这题目要求没给完吧，一般都会有加“最少次数”或者“所有遍历”之类的限制吧，不然不好judge啊。

这种题一般都是搜索吧，产生式系统，初始和目标状态都很确定。
是我一般就上BFS了，只要数据规模不是很大时空复杂度完全可以接受。

Canbitwell

en，一样，是7步。
不过5楼一提醒后，我才发现竟然忘建个表判重了……否则，这点数据队列最多时能有20000多个元素。。。

游戏之家站长

Miu.C: Re:询问:经典的中学算法竞赛试题

雷顿教授与XXXXX里经常见到。

雷顿教授是什么东西

Miu.C

游戏之家站长: Re: Re:询问:经典的中学算法竞赛试题



雷顿教授是什么东西

Google & Baidu

jnmao

Miu.C: Re: Re: Re:询问:经典的中学算法竞赛试题


Google & Baidu

又来，你以为它是无敌的啊