2

全面披露：这是一个硬件问题，我希望您提供最少的代码来解释该问题，我很感激我得到的任何帮助。

基本上我必须编写一个函数，以以下方式递归地打印出 2^n-1 个项目：

The output if n=1 is: 1
The output if n=2 is: 1 2 1
The output if n=3 is: 1 2 1 3 1 2 1
The output if n=4 is: 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

我不知道我该怎么做。我在玩斐波那契数列，但这似乎是一个死胡同。谢谢！

4

4 回答 4

4

第一步：
首先分析问题。你发现它需要递归。

第 2 步：
找出递归方案并建立一个假设：
因为n==2你的答案是1 2 1，因为n==3ans 是1 2 1 3 1 2 1然后你突然注意到n==3你正在写第一个答案n==2，然后3又一次回答n==2 所以现在你的假设将是 n- 的答案1 然后 n 再回答 n-1

第三步：
验证假设：
现在你应该验证你是否正确。你检查了 n=2 和 n=4，哇！你会找到预期的答案。现在你有了一个经过验证的递归假设。继续写代码。

第4步：
写下代码：
首先找出基本情况：这里是n = 1，因为你不能更深入。所以我们的函数开始像：

void foo(int n){
    if(n==1){
        cout<<1;
        return ;
    }
}

现在使用我们的假设，写下剩余的代码。

void foo(int n){
    if(n==1){
        cout<<1;
        return ;
    }
    foo(n-1);        //our hypothesis say first we need to write the answer for n-1
    cout<<" "<<n<<" ";  //then writing n itself
    foo(n-1);    //again writing answer for n-1
}
于 2013-10-06T01:03:03.000 回答
1

这个函数应该作为一个完整的二叉树上的就地遍历工作。就像你有以下树：

        3
    2       2
  1   1   1   1

树反映在每个级别中具有相同的值。所以你的功能应该是这样的：

void func(int n) {
  if (n == 1) {
    cout << "1 ";
    return;
  }

  func(n - 1);
  cout << n << ' ';
  func(n - 1);
}
于 2013-10-06T00:45:48.357 回答
1

鉴于无论如何已经给出了答案，这里有一个简短的版本：

bool f(int i)
{
    return i && (f(i-1), std::cout << i << ' ', f(i-1));
}
于 2013-10-06T01:01:03.720 回答
1

很简单，您试图用较小的数字覆盖每个数字（并且该数字将通过自身的递归重复相同的过程），直到参数 (n) 达到 0。在这种情况下，它只会返回而不做任何事情。

代码将如下所示：

void sequence(int n) {
    if (n == 0)
        return;

    sequence(n-1);
    cout << n << ' ';
    sequence(n-1);
}
于 2013-10-06T01:07:56.400 回答