1

所以我已经编写了一个函数来使用几个 for 循环来编写一个可变高度的数字金字塔，它工作得很好。

这是我正在谈论的金字塔类型的示例：

用户输入 4

      1 

    1 2 1

  1 2 3 2 1 

1 2 3 4 3 2 1

所以我确实需要用空格填充左侧。

我的问题是我不能让它只使用递归，没有循环。我什至想不出从递归的角度开始的地方，真的。我知道我需要一个基本案例，以及处理该基本案例的方法。

我应该编写多个递归函数，还是有办法只用一个？（除了主要的，我的意思是。）

这是我到目前为止所拥有的（一点也不多）：

void givepyramid(int lines);  //lines = Number of lines in pyramid (4 in example above)
{
     if lines == 1;
        cout << (//all the spaces needed)<<1;
     else
         cout << (I'm not too sure on how to go about this here.)
}

任何建议将不胜感激！谢谢。

4

7 回答 7

2

这是一个简单的解决方案，它可以在不使用循环的情况下绘制漂亮的三角形：

#include <iostream>

void printRowNumbers( unsigned int n, unsigned int max )
{
    if ( n < max ) {
        std::cout << n << ' ';
        printRowNumbers( n + 1, max );
    }
    std::cout << n << ' ';
}

void drawTriangle( unsigned int n, unsigned int indent = 0 )
{
    if ( n > 1 ) {
        drawTriangle( n - 1, indent + 2 );
    }
    std::cout << std::string( indent, ' ' );
    printRowNumbers( 1, n );
    std::cout << "\n";
}

主要思想是，您通常会使用循环来解决两个问题：

  1. 打印一行数字（没有任何特定的缩进），例如1 2 3 2 1或1 2 3 4 5 4 3 2 1。关键的想法是，您不仅将数字打印到最大值并返回，实际上您正在将数字从某个起始值（似乎总是1在这里）打印到最大值，然后返回开始价值。

    洞察力是，从 1 到 5 再打印这样的“数字镜子”与打印 1 相同，然后从 2 到 5 打印镜子，然后再次打印 1。从 2 到 5 打印一个镜像与打印 2 相同，然后从 3 到 5 做一个镜像，然后再次打印 2。依此类推，直到最小值与最大值相同，在这种情况下，您只需打印该数字（这是您的基本情况）。

  2. 多次打印一些东西，每次都在一个新的行上，缩进不断减少。我们需要一个可以多次打印某些东西（比如一个字母）的函数——每次都在自己的行上并且缩进不断减少。最后一行根本没有缩进。简单的情况是只打印一行 - 在这种情况下，您根本没有任何缩进。打印两行与先打印一行，缩进为 2 - 然后再次打印该行是一样的。打印三行意味着首先打印两行，缩进为 2（这反过来意味着打印一行，缩进为四！），然后是第三行没有缩进。

    我们的代码只是碰巧没有打印一些随机字母，而是该drawTriangle函数负责正确缩进（并打印换行符），但让我们printRowNumbers打印实际数字。

如您所见，我没有使用非常严格的分析方法（可以将任何循环重写为递归，因此您可以编写一个循环，然后通过遵循一些规则将其机械地转换为递归）。相反，我只是手工做了一些实验，比如“做这两次与只做一次有何不同，做三次与做两次有何不同”，然后发现了一个模式。

于 2013-10-10T20:31:51.097 回答
0

你可以更换

for (int i = 0; i != N; ++i) {
    body(i, localVars);
}

经过

void body_rec(int N, int i, LocalVars& localVars)
{
    if (i == N) return;
    body(i, localvars);
    body_rec(N, i + 1, localVars)
}
于 2013-10-10T19:43:37.730 回答
0

适用于大于 10 的数字，并且完全没有循环。

PS：C++11

#include <iostream>
#include <vector>
#include <string>


void gen_numbers(int len, int number, std::string &ans) {

    if (len > 1) {
        ans.append(std::to_string(number));
        ans.push_back(' ');
        gen_numbers(len - 1, number + 1, ans);
        ans.push_back(' ');
        ans.append(std::to_string(number));
    }
    if (len == 1)
        ans.append(std::to_string(number));

}

void print_spaces(int number) {
    std::cout << " ";
    if (number)
        print_spaces(number - 1);
}

void draw (int line, int depth) {
    if (line > 1) {
        draw(line - 1, depth);
    }

    print_spaces(2 * (depth - line));
    std::string ans;
    gen_numbers(line, 1, ans);
    std::cout << ans;
    print_spaces(depth - line);
    std::cout << std::endl;
}



int main() {
    draw(12, 12);
    return 0;
}
于 2013-10-10T19:14:04.317 回答
0

我创建了以下解决方案。它适用于超过 10 行的行数。

#include <iostream>
#include <vector> 
using namespace std;

void buildLine(int countline, int iteration)
{
 cout << string((countline-iteration),'\t');


 for(int i = 0; i < iteration; ++i)
 {
  cout << i+1 << "\t";
 }

 for(int i = iteration-1; i > 0; --i)
 {
   cout << i << "\t";
 }

 cout << string(countline-iteration,'\t') << endl;

 buildLine(countline,++iteration);

}

void buildPyramid(int lines)
{
 buildLine(lines, 1);
}


int main() {

   buildPyramid(11); 
}

在此处输入图像描述

于 2013-10-10T19:15:07.377 回答
0

您可以使用两个不同的递归函数，它们可能会或可能不会简化为单个递归函数。下面的示例可以编辑为相对简单地填充左侧，并作为练习留下。本质上，您想分别在左侧和右侧构建字符串的行，然后将它们连接到中心数字周围。

std::string buildString(int i, bool side)
{
    if(i < 1)
    {
        return "";
    }
    if(i == 1)
    {
        return "1";
    }
    if(i > 1)
    {
        std::ostringstream s;
        s << i;
        if(side == false) // left build
        {
             return buildString(i - 1, false) + " " + s.str();
        }
        if(side == true) // right build
        {
             return s.str() + " " + BuildString(i - 1, true);
        }
     }
 }

 //pass is function the expected length as well in order to enable padding
 void buildPyramid(int i /*, int max */)
 {
     if(i < 1)
     {
          return;
     }
     if(i > 1)
     {
          //by calling build pyramid recursively and falling through to the print statement after, you can cause the top of the pyramid to print first without looping
          buildPyramid(i - 1);
     }
     //the center number of each row is added here since it's the only number that isn't duplicated. By storing the resultant string in an ostringstream you can check the length and add padding.
     std::cout << buildString(i - 1, false) << " " << i << " " << buildString(i - 1, true);
 }
于 2013-10-10T19:15:13.810 回答
0

一个没有循环的简单递归函数：

void printTree(int maxLevel, int currLevel = 0, int currPos = 1)
{
    if(currLevel>maxLevel)
        return;
    if(currPos<(maxLevel-currLevel))
    {
        cout<<'\t';
        printTree(maxLevel, currLevel, ++currPos);
    }
    else if(currPos<(maxLevel-currLevel + currLevel*2)-1)
    {
        cout<<((maxLevel - currPos)<=0?(currPos - maxLevel)+2:(maxLevel - currPos))<<'\t';
        printTree(maxLevel, currLevel, ++currPos);
    }
    else
    {
        cout<<endl;
        printTree(maxLevel, ++currLevel, 0);
    }
}

对于您的示例，将该函数称为printTree(4)

于 2013-10-10T19:36:47.863 回答
0

我没有测试过这段代码，但你可以做这样的事情。它不使用任何循环。这将打印出一个倒金字塔，所以我将把不倒置的部分留给读者作为练习。

void givepyramid(int lines)
{
    giveIndentedPyramid(lines, 0);
}

void giveIndentedPyramid(int line, int indentation)
{
    printIndentationRecursive(indentation);

    if(line > 0)
    {
        printLineRecursiveUp(1, line);
        printLineRecursiveDown(line);

        cout << endl;
        giveIndentedPyramid(line-1, indentation+2);
    }
}

void printIndentationRecursive(int indentation)
{
    /*
    for(int i = 0; i < indentation; i++)
    {
        cout << " ";
    }
    */
    if(indentation > 0)
    {
        cout << " ";
        printIndentationRecursive(indentation-1);
    }
}

void printLineRecursiveUp(int current, int line)
{
    /*
    for(int i = 1; i < line; i++)
    {
        cout << i << " ";
    }
    */
    if(current < line)
    {
        cout << current << " ";
        printLineRecursiveUp(current + 1, line);
    }
}

void printLineRecursiveDown(int line)
{
    if(line > 0)
    {
        cout << line << " ";
        printLineRecursiveDown(current - 1, line);
    }
}

请记住，这是未经测试的代码，因此请将其视为伪代码，您可以将其用作学习如何使用递归的指南。

于 2013-10-10T18:46:36.703 回答