C中的递归问题

Question

我已经尝试解决这个问题几天了，但似乎我还没有掌握递归的概念。

我必须用 C 语言构建一个程序（这里必须递归，但也允许循环），它执行以下操作： 用户输入2个不同的字符串。例如： 字符串 1 - ABC 字符串 2 - DE

该程序应该打印由用户输入的字符串组合而成的字符串。 规则是每个字符串中字母的内部顺序 (1&2) 必须保持不变。 这是 string1=ABC & 的输出string2=DE ":

abcde abdce abdec 阿德布塞 阿德贝克 阿德贝克 达布采 达贝克 达埃布克 deabc

如果有人能帮我一把，那就太好了。 谢谢你们。

Answer 1

这是 Java 中的部分解决方案：它应该具有启发性：

public class Join {                                       // prints:
   static void join(String s, String s1, String s2) {     // ABCde
      if (s1.isEmpty() || s2.isEmpty()) {                 // ABdCe
         System.out.println(s + s1 + s2);                 // ABdeC
      } else {                                            // AdBCe
         join(s + s1.charAt(0), s1.substring(1), s2);     // AdBeC
         join(s + s2.charAt(0), s1, s2.substring(1));     // AdeBC
      }                                                   // dABCe
   }                                                      // dABeC
   public static void main(String[] args) {               // dAeBC
      join("", "ABC", "de");                              // deABC
   }
}

它是如何工作的

基本上你有 String s，“输出流”，和 String s1, s2，“输入流”。只要有机会，您首先从 s1 获取，然后再次尝试从 s2 获取，递归地探索这两个选项。

如果任何时候任一“输入流”为空，那么您别无选择，只能采用剩下的内容（如果有）。

Answer 2

这里是用 C 语言编写的，基于 @polygenelubricants 使用的相同想法。并不是我偷了他的想法，而是这是一个经典问题，这是最简单的方法:)。

#include <stdio.h>
#include <string.h>

void solve(const char *str1, const char *str2,
           const int length1, const int length2,
           char *output, int pozOut, int pozIn1, int pozIn2)
{
    if (pozIn1 == length1 && pozIn2 == length2)
    {
        printf("%s\n", output);
        return;
    }

    if (pozIn1 < length1)
    {
        output[pozOut] = str1[pozIn1];
        solve(str1, str2, length1, length2, output, pozOut + 1, pozIn1 + 1, pozIn2);
    }

    if (pozIn2 < length2)
    {
        output[pozOut] = str2[pozIn2];
        solve(str1, str2, length1, length2, output, pozOut + 1, pozIn1, pozIn2 + 1);
    }
}

int main()
{
    char temp[100]; // big enough to hold a solution.
    solve("ABC", "12", strlen("ABC"), strlen("12"), temp, 0, 0, 0);

    return 0;
}

这一点可以改进。例如，如何去掉一些参数？
另外，这还有一个错误：在打印之前，您应该确保 output 在末尾包含 '\0'，否则您可能会得到意外的结果。我会把这个问题留给你来解决。

Answer 3

我不想写下整个算法。不过，这里有一些可能对您有帮助的线索。

基本上，您必须合并两个字符串，保持字符顺序。这就像你有两堆可能大小不同的东西。

在您的示例中：

stack #1: A B C
stack #2: D E

您还知道生成的字符串的长度为两个输入字符串的长度之和。 （所以你已经知道要分配多少长度）

如果你逐个字符地进行：每一回合你都可以选择是从堆栈 #1 还是堆栈 #2 中弹出一个字符，然后继续。 （这里可能是递归）。如果您汇总所有可能的调用，您将获得所有结果字符串。

我在大学时曾经喜欢这样的问题：有时看起来很困难，但是当你自己解决它时如此值得！

如果您需要更多线索，请随时发表评论。

Answer 4

与 IVlad 相同的算法，但动态分配结果数组，并使用指针而不是索引，我认为这使它更清晰一些。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void solve(const char* result, const char* x0, const char* x1, char* p) {
    if (!*x0 && !*x1) printf("%s\n", result);
    if (*x0) {
        *p = *x0;
        solve(result, x0 + 1, x1, p + 1);
    } 
    if (*x1) {
        *p = *x1;
        solve(result, x0, x1 + 1, p + 1);
    }
}

int main(int argc, char* argv[]) {
    if (argc >= 3) {
        size_t total_length = strlen(argv[1]) + strlen(argv[2]) + 1;
        char *result = malloc(total_length);
        if (result) {
            result[total_length - 1] = '\0';
            solve(result, argv[1], argv[2], result);
            free(result);
        }
    }
    return 0;
}