1

我是大学第一年的初学者程序员。我的导师要求我们对递归算法进行一些研究，并使其不递归。不管我尝试了多少，这似乎是不可能的。问题是

A 是一个字符串（例如 A = "hello"），作为抽象的交换，将第 k 个字符与 A 的第 i 个字符交换，例如 CALL 交换（"hello", 2, 3) 将更改为 "你好”到“hlelo”）。

这个想法是打印出所有可能的排列 C++ 中的版本读取

void perm(char*a, const int k, const int n)
{
  if(k==n)
  {
    cout << a;
  }
  else
  {
    for (i=k;i<=n;i++)
    {
      interchange(a, k, i);
      perm(a, k+1, n)
    }
  }
 }

我的导师更喜欢使用一种叫做 ADL 的语言，这种语言似乎只出现在 Horowitz 的《算法和数据结构》一书中。他在 ADL 中提出了这个问题，所以我也会添加该代码，它很容易理解。

proc perm(IN a, IN k, IN n)
  if k=n then
    print(a)
  else
    {
     for i <- k to n do
       call interchange(a,k,i)
       call perm( a, k+1, n)
     end
    }
end

感谢任何可以提供帮助的人。马丁

4

2 回答 2

3

递归算法只是一种使用堆栈的算法。

递归允许您将调用堆栈用作数据堆栈。

任何采用这种形式的递归函数：

void perm(char*a, const int k, const int n)
{
   // check if your code should return

   // make a recursive call with new data
}

可以改成这样：

void perm(char*a, const int k, const int n)
{
   // Create a stack, push (a,k,n)

   while ( /* stack isn't empty */ )
   {
       // check if stack should be *popped* (instead of returning)

       // Put new data on the stack (instead of recursing)
   }
}
于 2013-04-02T19:53:02.567 回答
2

这是一个提示，无需为您做功课。当你沿着字符串走，查看第 i 个字符时，你处于三种可能的状态之一：

  • 我 == k
  • 我 == n
  • 别的

在这三种情况下，您分别打印什么？

于 2013-04-02T19:52:06.310 回答