0

现在，我有以下伪代码

Printstations(fastest, path, lastpath, n)
 print "fastest solution requires" + fastest + "time units"
 print "line' + lastpath +"station" + n
 for j = n downto 2
      print "line" + path[lastpath, j] + "station" + j-1
      lastpath = path[lastpath, j]

示例输出为：最快的解决方案需要 14 个时间单位：1 号线、4 号站、2 号线、3 号站、2 号线、2 号站、1 号线、1 号站

我需要使用递归来反转打印输出的顺序。基本上，我需要它来阅读：最快的解决方案需要 14 个时间单位：1 号线、1 号站、2 号线、2 号站、2 号线、3 号站、1 号线、4 号站

谢谢。

所以本质上，站顺序需要从读取 4 到 1 变为从站 1 到 4，由于示例，行顺序似乎没有改变，而是因为本质上这里的行号创建了一个回文. 我还没有真正能够得到任何连贯的东西。我对递归如何改变顺序感到困惑。

我想出了这个：

PrintStations(fastest, path, lastpath, n)
 if n = 0
      print "fastest solution requires" + fastest + "time units"
 else
      PrintStations(fastest, path, path[lastpath, n], n-1)
      print "line" + lastpath + "station" + n

我认为这可能有效，但不完全确定。

4

1 回答 1

0

你在正确的轨道上。您当前的输出如下所示：

fastest solution requires 14 time units: 
    line 1, station 4 
    line 2, station 3 
    line 2, station 2 
    line 1, station 1

你想有这样的输出： 

fastest solution requires 14 time units: 
    line 1, station 1 
    line 2, station 2 
    line 2, station 3 
    line 1, station 4

为了使用递归来实现这一点，您需要更改当前的解决方案：

PrintStations(fastest, path, lastpath, n)
    if n = 0
        COMMENT: incorrect, because this will be the last printed text,
        COMMENT: this line should be called once at the begining
        COMMENT: or even better before the recursive call is executed
        print "fastest solution requires" + fastest + "time units"
    else
        COMMENT: better change the order of the resursive call and the print
        PrintStations(fastest, path, path[lastpath, n], n-1)
        print "line" + lastpath + "station" + n

这将在执行结束时而不是在开始时打印 line faster solution requires ...。我假设您从 n 而不是 0 开始，因为如果您从 0 开始，则永远不会到达递归调用。

使用递归的一般方法是提取调用自身的函数并从另一个函数开始执行它，因为您需要一个起点。您可以创建一个名为PrintSolution的函数，该函数采用与PrintStations函数相同的参数，并从内部调用PrintStations一次。这也是打印最快解决方案的正确位置...文本：

COMMENT: this is now your starting point
PrintSolution(fastest, path, lastpath, n)
    print "fastest solution requires" + fastest + "time units"
    PrintStations(fastest, path lastpath, n)

您的PrintStation也将变得更小，更易于书写/阅读：

PrintStations(fastest, path, lastpath, n)
    COMMENT: execution break condition is n == 0
    if n > 0
        COMMENT: print current path and station
        print "line" + lastpath + "station" + n
        COMMENT: call print station with next/previous path to print
        PrintStations(fastest, path, path[lastpath, n], n-1)

当然还有其他可能性来创建递归函数。不需要第二个功能的解决方案可能如下所示：

variable m = n
PrintStations(fastest, path, lastpath, n)
    COMMENT: execution break condition is n == 0
    if (n = m)
        COMMENT: first call
        print "fastest solution requires" + fastest + "time units"          
    if n > 0
        COMMENT: print current path and station
        print "line" + lastpath + "station" + n
        COMMENT: call print station with next/previous path to print
        PrintStations(fastest, path, path[lastpath, n], n-1)

在这种情况下，您需要 n 变量的初始值才能仅打印第一行一次。

递归调用等效于迭代，因为它也在给定的数据结构上按顺序操作：

print(3);

COMMENT: equivalent to for (i = 3; i <= 1; i--) => 3 -> 2 -> 1
for i = 3 downto 1
    out i

COMMENT: 3 -> 2 -> 1
print(n)
    if (n > 0)
        print(n-1);
        out n

COMMENT: reverse the print - 1 -> 2 -> 3
variable m = n
print(n)
    if (n <= m)
        print(n+1);
        out n

另一种可能性是将中断条件常量作为参数：

print(n, m)
    if (n <= m)
        print(n+1, m);
        out n
COMMENT: initial call: print(1, 3)

如果没有关于路径数组的精确描述和更多信息（或至少是数据），很难编写一个可行的解决方案，但伪代码朝着正确的方向发展。

于 2013-10-18T07:36:30.303 回答