4

最近在一个编程课上，我们被分配用任何语言编写一个程序，给定n ，它将为大小为n的数组p产生所有可能的混乱，使得p [i] != i for all i: 0 <= 我 < n。我们不得不使用迭代器，例如.yield

示例：n=3, [0, 1, 2] 不是紊乱，但 [2, 0, 1] 和 [1, 2, 0] 一样。

我想出了一个可行的伪代码解决方案，但问题是它需要电源循环（即n嵌套循环，其中n仅在运行时已知）。为此，我在一个字符串中的 Ruby 代码中生成了n 个嵌套循环，然后eval-ed 字符串。我的解决方案有效，但是我的教授认为使用几个gotos 会比动态代码生成更好的解决方案（至少更易于阅读）。

我的印象是这goto总是一个糟糕的选择。为什么动态生成代码的运行时评估可能是比 更糟糕的选择goto？生成的代码简洁明了，对于给定的问题似乎相当有效。代码生成所依赖的唯一用户输入是n，预先对其进行检查以确保它是一个整数值。这yield只是独特的精神错乱，应该如此。

我不是在为我的编程任务寻求解决方案，我只是想知道使用goto过度动态代码评估背后的原因，反之亦然。

编辑： 澄清一下，任务包括使用迭代器编写程序和使用递归编写另一个程序，因此迭代版本不一定是高效的。

4

11 回答 11

6

GOTO 和代码生成都是 IMO 问题的不优雅解决方案。这里有一个递归算法可能是正确的答案。

于 2009-09-11T18:42:55.750 回答
2

在没有看到您的代码的情况下，我倾向于站在教授一边。如果要在 GoTo 和动态代码之间进行选择，我会倾向于前者。GoTo 并不总是一个糟糕的选择。

于 2009-09-11T18:46:11.983 回答
2

您可以在不使用 GoTos 的情况下解决几乎所有问题。特别是对于循环，您可以使用 break 和 continue 语句来隐式使用 goto，同时仍保持代码标准。

n嵌套循环听起来像是一个糟糕的计划，我建议您改用递归函数。每次您需要执行 n 循环时，您都应该始终考虑递归。

于 2009-09-11T18:46:25.630 回答
2

动态代码在编译时不可检查，这意味着任何错误在运行时都不会被发现。可能使他们更难找到。对于 ruby​​，这意味着 IDE 或编辑器不会发现语法错误，无论您碰巧使用的是哪个。这是选择 goto 的一个优点。

我想在这种情况下我必须看到两者才能做出决定。我还没有看到代码，但我敢打赌有一个不使用动态代码或 goto 的好解决方案。goto 并不总是很糟糕，但如果您正在考虑使用它，您可能还没有做出最好的设计决策，并且可能想要重新审视您的解决方案。

于 2009-09-11T18:49:08.183 回答
2

这是一个非常有趣的问题——我不确定是否有明确的答案。

goto 的问题在于它以非结构化方式使用 - goto 是“大规模随机跳跃”，所以在一般情况下，跳跃之后，你不知道你从哪里来，这会导致各种问题调试和可维护性以及 - 在更正式的意义上证明代码的“正确性”。当然，有些语言（我已经有一段时间了）你没有选择在什么时候对代码强加结构。最重要的是，并不是 GOTO 不好，而是 goto 的使用（和滥用）方式不好，这使得它成为一个危险的构造。

使用代码生成然后评估结果很聪明 :) 但是“聪明”并不总是一件好事，我怀疑使用它作为解决方案的部分问题在于它实际上并没有按预期解决问题。从某种意义上说，这可能是“作弊”——至少就你的教授而言——不会使你的解决方案无效，但可能会使它“不雅”。调试和维护问题也出现在代码方面。

一个递归解决方案——尤其是当我模糊记得（大约 25 年前）被教导通常可以将递归展开为循环时——可能是最优雅的。

绝对是一个有趣的问题！

于 2009-09-11T19:10:01.860 回答
1

在我大学的一项作业中，我曾经不得不做一些相对相似的事情。我的解决方案是使用递归函数，将数组、数组的大小和嵌套级别作为参数传递。然后该函数以嵌套级别 +1 调用自身，直到嵌套级别等于数组的大小。没有 Goto，没有代码评估，只有干净的代码！

例子

function computeDerangement(yourArray, loopLevel, arraySize)
{
    //We check to see if the loop level is the same as the array size
    //if true, then we have executed exactly n loop
    if (loopLevel == arraySize) {
         display(yourArray); //Display being some kind of function that show the array,
                             //you get the idea
    } else {
        while(something) {
            //Here you put the logic that you execute at one level of the loop

            //Then you call yourself with one more level of nesting
            computeDerangement(yourArray, loopLevel + 1, arraySize);
        }
    }
}

希望有帮助！

我一生中从未使用过 goto，所以我很确定总有办法避免它们

于 2009-09-11T19:01:23.990 回答
1

人们避免使用 goto 语句的主要原因是它们会使您的程序更难理解。

如果没有看过你的代码，我猜它比使用 goto 的等效程序更难理解......

于 2009-09-11T19:38:15.473 回答
1

GOTO 解决方案——在模拟函数调用时，goto 很方便。这是一个非递归解决方案，它使用堆栈和 goto 标签简单地模拟递归解决方案，以返回到发生函数调用的点。

请参阅递归过程（我已将其作为单独的答案发布）进行比较。

Option Strict On 选项显式打开

模块 Module1 Dim x As Stack

Private Sub printGeneratedList(ByVal generatedList As List(Of Integer))
    For Each el In generatedList
        Console.Write(el & " ")
    Next
    Console.WriteLine()
End Sub
Private Sub generateAux(ByVal i As Integer, ByVal n As Integer, _
                        ByVal generatedList As List(Of Integer))
    Dim stackI As Stack(Of Integer) = New Stack(Of Integer)
    Dim stackJ As Stack(Of Integer) = New Stack(Of Integer)


    Dim j As Integer

开始标签：

    j = 0

    If i >= n Then
        printGeneratedList(generatedList)
        If stackI.Count = 0 Then
            Return
        Else
            GoTo ReturnLabel
        End If
    End If

     While j < n
        If Not j = i Then
            If Not generatedList.Contains(j) Then
                generatedList.Add(j)
                stackI.Push(i)
                stackJ.Push(j)
                i = i + 1
                GoTo StartLabel

退货标签：

                i = stackI.Pop()
                j = stackJ.Pop()
                generatedList.Remove(j)
            End If
        End If
        j = j + 1
    End While
    If stackI.Count = 0 Then
        Return
    Else
        GoTo ReturnLabel
    End If
End Sub

Private Sub generate(ByVal n As Integer)
    Console.WriteLine("Generating for n = " & n.ToString())
    Dim l As List(Of Integer) = New List(Of Integer)
    If n < 0 Then
        Throw New Exception("n must be >= 0")
    End If
    generateAux(0, n, l)
End Sub

Sub Main()
    generate(0)
    Console.ReadLine()
    generate(1)
    Console.ReadLine()
    generate(2)
    Console.ReadLine()
    generate(3)
    Console.ReadLine()
    generate(4)
    Console.ReadLine()
End Sub

端模块

于 2009-09-11T23:17:06.683 回答
0

goto的不干净。但是如果需要高性能，有时你需要打破一些编码规则......

如果速度真的很重要，例如，如果你想编写一个库或你有很大需求的代码，你可以考虑使用 goto。当然，您必须注意一切顺利。

评论：最后，执行中的 CPU 只做简单的跳转。只是编程语言/编译器创建它们。谨慎使用，不要乱用。

于 2009-09-11T18:45:06.930 回答
0

goto 解决方案和动态代码生成的想法都很糟糕。这很容易通过其他人提到的递归解决方案来解决。您只需递归地生成所有排列（标准递归解决方案），当生成完成时（即在递归的叶子处），只需跳过返回的不是混乱的排列。

于 2009-09-11T19:18:39.233 回答
0

递归解决方案——这是一个早期修剪的解决方案。我唯一的问题是关于枚举：他是否希望您创建一个枚举器，在每次成功调用时都会生成列表中的下一个项目？这可能是通过创建该程序的 lambda 版本最容易实现的——我曾经在编写查询生成器时一直在 lisp 中执行此操作，该生成器会在执行 prolog-interpreter 样式查询时生成问题的下一个答案。

Option Strict On 选项显式打开

模块模块1

Private Sub printGeneratedList(ByVal generatedList As List(Of Integer))
    For Each el In generatedList
        Console.Write(el & " ")
    Next
    Console.WriteLine()
End Sub

Private Sub generateAux(ByVal i As Integer, ByVal n As Integer, _
                    ByVal generatedList As List(Of Integer))
    If i >= n Then
        printGeneratedList(generatedList)
        Return
    End If
    For j As Integer = 0 To n - 1
        If Not j = i Then
            If Not generatedList.Contains(j) Then
                generatedList.Add(j)
                generateAux(i + 1, n, generatedList)
                generatedList.Remove(j)
            End If
        End If
    Next
End Sub

Private Sub generate(ByVal n As Integer)
    Console.WriteLine("Generating for n = " & n.ToString())
    Dim l As List(Of Integer) = New List(Of Integer)
    If n < 0 Then
        Throw New Exception("n must be >= 0")
    End If
    generateAux(0, n, l)
End Sub

Sub Main()
     generate(0)

    Console.ReadLine()
    generate(1)

    Console.ReadLine()
    generate(2)

    Console.ReadLine()
    generate(3)

    Console.ReadLine()
    generate(4)

    Console.ReadLine()

End Sub

端模块

于 2009-09-11T21:33:31.000 回答