4

我已经开始练习一些 C 语言，发现这个很好的练习，我必须通过输入打印一个三角形。对于输入 6 它将打印

*
**
***
****
*****
******
*****
****
***
**
*

现在，看着它，我想，嗯，这不是一项艰巨的任务。所以我决定尝试使用递归编写它，没有循环，只有 2 个变量。该函数应如下所示：

void PrintTriangle(int iMainNumber, int iCurrNumber)
{
   //Logic goes here
}

几个小时后，我意识到这比我想象的要困难得多，因为我需要为函数传递足够的信息才能“记住”它应该打印多少三角形。

所以现在我决定问你这是否可能。

（记住，没有循环，没有其他功能，只有递归）。

编辑： 这不是家庭作业，这纯粹是出于好奇。但是我可能无法为您验证。我已经成功完成了一半

void PrintTriangle(int iMainNumber, int iCurrNumber)
{
    if (iMainNumber == 0)
    {
        printf("\r\n");
    }
    else if (iMainNumber == iCurrNumber)
    {
        printf("\r\n");
        PrintTriangle(iMainNumber - 1, 0);
    }
    else
    {
        printf("%s", MYCHAR);
        PrintTriangle(iMainNumber, iCurrNumber + 1);
    }
}

我在尝试创建相反的函数时遇到了困难，我相信如果我能做到，我将能够利用 iMainNumber 和 iCurrNumber 是正数或负数的事实来浏览函数流。

换句话说，当参数为负时，我会在输入减一的长度上打印一个降星，当参数为正时，我会在输入的长度上打印升星。

我考虑过使用标志，但不是用 2 个整数。

也许如果我添加另一个标志并有 2 个整数和一个标志，那么我可以解决它，但正如我所说，我试图将自己限制为 2 个整数。

我开始想到的是，如果不使用超过 2 个整数和递归，就无法通过这种方法传递打印升星所需的信息。

但我仍然不太确定，因此提出了这个问题。

4

5 回答 5

3

我想出了：

void PrintTriangle(int size, int indent)
{
    switch(size) {
    case 0:
        if (indent > 1) PrintTriangle(size, indent-1);
        putchar('*');
        break;
    case 1:
        PrintTriangle(size-1, indent+1);
        putchar('\n');
        break;
    default:
        PrintTriangle(1, indent);
        PrintTriangle(size-1, indent+1);
        PrintTriangle(1, indent);
        break; }
}

int main()
{
    PrintTriangle(6, 0);
    return 0;
}

作为快速的第一次尝试。似乎完成了这项工作。

size是要打印的三角形的大小，并且indent是要在三角形的每一行之前打印的额外星数。 size==0表示只打印indent星号，没有换行符（用于打印三角形前的缩进）

如果您想要更紧凑的东西，可以将其重写为：

void PrintTriangle(int size, int indent)
{
    if (size <= 0) {
        if (indent > 1) PrintTriangle(size, indent-1);
        putchar('*');
    } else {
        if (size > 1) PrintTriangle(1, indent);
        PrintTriangle(size-1, indent+1);
        if (size > 1) PrintTriangle(1, indent);
        else putchar('\n'); }
}
于 2013-10-14T22:26:00.003 回答
3

使用循环完成的任何事情都可以通过具有相同数量变量的递归来完成。您只需要梳理出状态是什么，然后在递归调用中传递更新的状态，而不是循环。

因此，让我们首先迭代地进行。输入是size，三角形的大小。让我们有两个状态变量，lineNumber从 1 到size*2-1和columnNumber从 1 到size。注意：

columnsForLine = lineNumber <= size ? lineNumber : size*2 - lineNumber

迭代版本将是这样的：

int lineNumber = 1;
int columnNumber = 1;
int size = 6;
while (lineNumber <= size*2-1) {        
    printf("*");
    int columnsForLine = lineNumber <= size ? lineNumber : size*2 - lineNumber;
    if (columnNumber == columnsForLine) {
        printf("\n");
        columnNumber = 1;
        lineNumber += 1; 
    }
    else {
        columnNumber += 1;
    }
}

这确实有效。现在如何递归地做到这一点？只需梳理出状态正在更新的位置，并将其作为递归调用：

void recstars(int size, int lineNumber, int columnNumber) {
    if (!(lineNumber <= size*2 - 1)) {
        return;
    }
    printf("*");
    int columnsForLine = lineNumber <= size ? lineNumber : size*2 - lineNumber;
    if (columnNumber == columnsForLine) {
        printf("\n");
        recstars(size, lineNumber + 1, 1);
    }
    else {
        recstars(size, lineNumber, columnNumber + 1);
    }
}
recstars(6, 1, 1);

瞧。_ 适用于任何尺寸，例如13。

请注意，代码基本相同，只是控制流程不同。另请注意，这是尾递归的，这意味着智能编译器将能够执行递归调用，而无需为每个调用增加堆栈。

嗯，如果你只想使用 2 个变量，包括输入，会有点棘手......你总是可以作弊并将所有 3 个整数填充到一个整数中，然后每次解压并重新打包。例如

void recstars(int state) {
    int size = state / 10000;
    int lineNumber = (state - size*10000) / 100;
    int columnNumber = state - size*10000 - lineNumber*100;
    if (!(lineNumber <= size*2 - 1)) {
        return;
    }
    printf("*");
    int columnsForLine = lineNumber <= size ? lineNumber : size*2 - lineNumber;
    if (columnNumber == columnsForLine) {
        printf("\n");
        recstars(size*10000 + (lineNumber+1)*100 + 1);
    }
    else {
        recstars(size*10000 + lineNumber*100 + (columnNumber+1));
    }
}
recstars(6*10000 + 1*100 + 1);

似乎工作。你觉得这合法吗？

否则，棘手的部分不是递归，它只是用 2 个 int 来完成工作。你可以只用 2 个整数迭代吗？

于 2013-10-14T21:32:31.297 回答
1

按照 OP 的建议使用 2 个参数

void PrintTriangle(int iMainNumber, int iCurrNumber) {
  if (iMainNumber < 0) { // Row (use negative iMainNumber)
    printf("%c", '*');
    PrintTriangle(iMainNumber + 1, 0);
    if (iMainNumber == -1)
      printf("\n");
  } else if (iMainNumber > 0) { 
    if (iCurrNumber < iMainNumber) { // Preceding short lines
      if (iCurrNumber > 1)
        PrintTriangle(iMainNumber, iCurrNumber - 1);
      PrintTriangle(-iCurrNumber, 0);
    } else if (iCurrNumber == iMainNumber) { 
      PrintTriangle(iMainNumber, iCurrNumber - 1);  // left
      PrintTriangle(iMainNumber, iCurrNumber + 1);  // Right
    } else {                         // Subsequent short lines
      if ((iCurrNumber - iMainNumber) < iMainNumber)
        PrintTriangle(iMainNumber, iCurrNumber + 1);
      PrintTriangle(-(iCurrNumber - iMainNumber), 0);
    }
  }
}

int main() {
  PrintTriangle(3,3);
  PrintTriangle(6,6);
  return 0;
  }
于 2013-10-14T22:03:07.790 回答
0

根据我的阅读，大多数建议已经指出可以在您需要的任何状态下通过。

但是，您真的不需要那么多分支语句。大多数你需要的东西，你可以算术推导出来。您可以计算递归总数并从当前递归计数中得出星数。此外，通过将初始调用的部分与递归分开，您可以使使用更加简单。

刚刚看到你不想要两个以上的整数。考虑以下内容，看看您是否真的想保持这种偏好。如果是这样，您可以将总数的计算放在递归部分中。我认为它的可读性会降低。

void _print_stars(int height, int total, int current)
{
    int stars = current <= height ? current : 2 * height - current;

    for (int i = 0; i < stars; i++) { printf("*"); }
    printf("\n");

    if (current != total)
    {
        _print_stars(height, total, current + 1);
    }
}

void print_stars(int height)
{
    int total_recursions = 2 * height - 1;
    _print_stars(height, total_recursions, 1);
}
于 2013-10-14T23:28:20.680 回答
0

纯递归，无循环，调用程序'main()'只传递一个参数：

void PrintTheClms(int width, int stars) {
    printf("*");
    if stars < width then {
      PrintTheClms(width, stars+1);
    }
}

void PrintStars(int  width) {
    PrintTheClms(width, 1);
    printf("\n");
}

void PrintTheRows(int size, int indent) {
    PrintStars(indent);
    if indent < size then {
      PrintTheRows(size, indent+1);
      PrintStars(indent);
    }
}

void PrintTriangle(int size) {
    if size > 0 then {
      PrintTheRows(size, 1);
    }
}

int main() {
    PrintTriangle(6);
    PrintTriangle(11);
    // etc.
    return 0;
}

非常简单——没有 else 子句，没有 case 结构，没有方向标志。不过，有很多 procs 和很多调用。

于 2013-10-15T01:06:32.450 回答