鱼C论坛

 找回密码
 立即注册
查看: 676|回复: 5

[已解决]合法出栈序列问题

[复制链接]
发表于 2023-4-1 13:54:07 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
假设栈的输入序列为1、2、3、...、n,设计算法求出所有可能的出栈序列。比如输入1、2、3、4、5,可能出栈的序列为12345、13452等42个。
这种题该怎么做,想了很久还是做不来。求大神的解答!
最佳答案
2023-4-1 14:45:49
白痴爱面包 发表于 2023-4-1 14:32
因为是初学者的原因对一些库函数并不了解,我主要想看一下栈的递归过程这是困扰我的最大难处,这段代码封 ...

这是C语言的版本:

  1. #include <stdio.h>

  2. int counter = 0;

  3. void stack_permutation(int input[], int n, int in_idx, int out_idx, int stack[], int stack_top) {
  4.     if (out_idx == n) {
  5.         counter++;
  6.         for (int i = 0; i < n; i++) {
  7.             printf("%d", stack[n + i]);
  8.         }
  9.         printf("\n");
  10.         return;
  11.     }

  12.     if (stack_top > 0) {
  13.         int pop_val = stack[stack_top - 1];
  14.         stack_top--;
  15.         stack[n + out_idx] = pop_val;
  16.         stack_permutation(input, n, in_idx, out_idx + 1, stack, stack_top);
  17.         stack_top++;
  18.         stack[stack_top - 1] = pop_val;
  19.     }

  20.     if (in_idx < n) {
  21.         stack[stack_top] = input[in_idx];
  22.         stack_top++;
  23.         stack_permutation(input, n, in_idx + 1, out_idx, stack, stack_top);
  24.     }
  25. }

  26. int main() {
  27.     int n;
  28.     printf("请输入序列长度:");
  29.     scanf("%d", &n);

  30.     int input[n];
  31.     printf("请输入入栈序列(以空格分隔):");
  32.     for (int i = 0; i < n; i++) {
  33.         scanf("%d", &input[i]);
  34.     }

  35.     int stack[2 * n];
  36.     stack_permutation(input, n, 0, 0, stack, 0);

  37.     printf("所有可能的出栈序列的个数:%d\n", counter);

  38.     return 0;
  39. }
复制代码


代码说明:


  • 首先,定义一个全局变量counter,用于计算所有可能的出栈序列的个数。
  • 然后,定义一个名为stack_permutation的递归函数,它的参数包括:

    • input[]:用户输入的入栈序列
    • n:序列长度
    • in_idx:当前正在处理的输入序列的索引
    • out_idx:当前正在处理的输出序列的索引
    • stack[]:用于模拟栈的数组,前一半用于模拟栈,后一半用于存储输出序列
    • stack_top:栈顶指针,指向栈中下一个空位置

  • stack_permutation函数的逻辑如下:

    • 如果out_idx等于n,则表示所有元素已经出栈。此时,我们将计数器加1,并输出当前的输出序列。
    • 如果stack_top大于0,表示栈非空,我们可以进行出栈操作。首先将栈顶元素出栈并保存到输出序列中,然后递归调用stack_permutation。递归调用返回后,需要将刚刚出栈的元素重新入栈,以便尝试其他可能的操作。
    • 如果in_idx小于n,表示还有元素可以入栈。将当前输入序列中的元素入栈,然后递归调用stack_permutation。

  • 在main函数中:

    • 获取用户输入的序列长度n。
    • 创建一个大小为n的input数组,用于存储用户输入的入栈序列。
    • 使用一个循环从用户处读取入栈序列。
    • 创建一个大小为2 * n的stack数组。前一半用于模拟栈,后一半用于存储输出序列。
    • 调用stack_permutation函数,传入input数组、序列长度、初始索引和栈顶指针。
    • 最后,输出计数器的值作为所有可能的出栈序列的个数。




这个代码允许用户输入自定义的入栈序列,并输出所有可能的出栈序列及其个数。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-4-1 14:02:11 | 显示全部楼层
这是一个经典的栈问题。在这里,我们需要设计一个算法来生成所有可能的出栈序列。

可以使用递归的方法来解决这个问题。

首先,我们需要定义一个辅助函数,用于生成所有可能的出栈序列。

在这个辅助函数中,我们需要跟踪以下几个参数:

  • 当前的入栈序列
  • 当前的出栈序列
  • 当前栈的状态


算法的基本思路是:

  • 如果栈为空且没有剩余的入栈元素,则将当前的出栈序列添加到结果列表中。
  • 如果还有剩余的入栈元素,我们可以将其入栈,然后递归地继续生成序列。
  • 如果栈不为空,我们可以将栈顶元素出栈,并将其添加到当前的出栈序列中,然后递归地继续生成序列。


这是一个使用Python实现的示例:

  1. def generate_sequences(stack, in_seq, out_seq, result):
  2.     if not stack and not in_seq:
  3.         result.append(out_seq)
  4.         return

  5.     # 入栈操作
  6.     if in_seq:
  7.         stack.append(in_seq.pop(0))
  8.         generate_sequences(stack, in_seq, out_seq, result)
  9.         in_seq.insert(0, stack.pop())

  10.     # 出栈操作
  11.     if stack:
  12.         out_seq.append(stack.pop())
  13.         generate_sequences(stack, in_seq, out_seq, result)
  14.         stack.append(out_seq.pop())

  15. def all_pop_sequences(n):
  16.     in_seq = list(range(1, n+1))
  17.     stack, out_seq, result = [], [], []
  18.     generate_sequences(stack, in_seq, out_seq, result)
  19.     return result

  20. if __name__ == "__main__":
  21.     n = 5
  22.     sequences = all_pop_sequences(n)
  23.     print("共有 {} 个出栈序列。".format(len(sequences)))
  24.     for seq in sequences:
  25.         print(seq)
复制代码


输入:n = 5
输出:共有 42 个出栈序列。

这个算法生成了所有可能的出栈序列,并将它们添加到结果列表中。你可以根据需要调整输入参数n来改变入栈序列的长度。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-4-1 14:16:32 | 显示全部楼层
isdkz 发表于 2023-4-1 14:02
这是一个经典的栈问题。在这里,我们需要设计一个算法来生成所有可能的出栈序列。

可以使用递归的方法来 ...

请问能列出一个c或c++的例子吗,python的看不懂
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-4-1 14:19:27 | 显示全部楼层
白痴爱面包 发表于 2023-4-1 14:16
请问能列出一个c或c++的例子吗,python的看不懂

这是C++的例子:

  1. #include <iostream>
  2. #include <vector>

  3. void generate_sequences(std::vector<int>& stack, std::vector<int>& in_seq, std::vector<int>& out_seq, std::vector<std::vector<int>>& result) {
  4.     if (stack.empty() && in_seq.empty()) {
  5.         result.push_back(out_seq);
  6.         return;
  7.     }

  8.     // 入栈操作
  9.     if (!in_seq.empty()) {
  10.         stack.push_back(in_seq.front());
  11.         in_seq.erase(in_seq.begin());
  12.         generate_sequences(stack, in_seq, out_seq, result);
  13.         in_seq.insert(in_seq.begin(), stack.back());
  14.         stack.pop_back();
  15.     }

  16.     // 出栈操作
  17.     if (!stack.empty()) {
  18.         out_seq.push_back(stack.back());
  19.         stack.pop_back();
  20.         generate_sequences(stack, in_seq, out_seq, result);
  21.         stack.push_back(out_seq.back());
  22.         out_seq.pop_back();
  23.     }
  24. }

  25. std::vector<std::vector<int>> all_pop_sequences(int n) {
  26.     std::vector<int> in_seq(n);
  27.     for (int i = 0; i < n; ++i) {
  28.         in_seq[i] = i + 1;
  29.     }

  30.     std::vector<int> stack, out_seq;
  31.     std::vector<std::vector<int>> result;
  32.     generate_sequences(stack, in_seq, out_seq, result);
  33.     return result;
  34. }

  35. int main() {
  36.     int n = 5;
  37.     auto sequences = all_pop_sequences(n);
  38.     std::cout << "共有 " << sequences.size() << " 个出栈序列。" << std::endl;
  39.     for (const auto& seq : sequences) {
  40.         for (int num : seq) {
  41.             std::cout << num;
  42.         }
  43.         std::cout << std::endl;
  44.     }
  45.     return 0;
  46. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-4-1 14:32:41 | 显示全部楼层
isdkz 发表于 2023-4-1 14:19
这是C++的例子:

因为是初学者的原因对一些库函数并不了解,我主要想看一下栈的递归过程这是困扰我的最大难处,这段代码封装了太多东西因此并不能看懂
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-4-1 14:45:49 | 显示全部楼层    本楼为最佳答案   
白痴爱面包 发表于 2023-4-1 14:32
因为是初学者的原因对一些库函数并不了解,我主要想看一下栈的递归过程这是困扰我的最大难处,这段代码封 ...

这是C语言的版本:

  1. #include <stdio.h>

  2. int counter = 0;

  3. void stack_permutation(int input[], int n, int in_idx, int out_idx, int stack[], int stack_top) {
  4.     if (out_idx == n) {
  5.         counter++;
  6.         for (int i = 0; i < n; i++) {
  7.             printf("%d", stack[n + i]);
  8.         }
  9.         printf("\n");
  10.         return;
  11.     }

  12.     if (stack_top > 0) {
  13.         int pop_val = stack[stack_top - 1];
  14.         stack_top--;
  15.         stack[n + out_idx] = pop_val;
  16.         stack_permutation(input, n, in_idx, out_idx + 1, stack, stack_top);
  17.         stack_top++;
  18.         stack[stack_top - 1] = pop_val;
  19.     }

  20.     if (in_idx < n) {
  21.         stack[stack_top] = input[in_idx];
  22.         stack_top++;
  23.         stack_permutation(input, n, in_idx + 1, out_idx, stack, stack_top);
  24.     }
  25. }

  26. int main() {
  27.     int n;
  28.     printf("请输入序列长度:");
  29.     scanf("%d", &n);

  30.     int input[n];
  31.     printf("请输入入栈序列(以空格分隔):");
  32.     for (int i = 0; i < n; i++) {
  33.         scanf("%d", &input[i]);
  34.     }

  35.     int stack[2 * n];
  36.     stack_permutation(input, n, 0, 0, stack, 0);

  37.     printf("所有可能的出栈序列的个数:%d\n", counter);

  38.     return 0;
  39. }
复制代码


代码说明:


  • 首先,定义一个全局变量counter,用于计算所有可能的出栈序列的个数。
  • 然后,定义一个名为stack_permutation的递归函数,它的参数包括:

    • input[]:用户输入的入栈序列
    • n:序列长度
    • in_idx:当前正在处理的输入序列的索引
    • out_idx:当前正在处理的输出序列的索引
    • stack[]:用于模拟栈的数组,前一半用于模拟栈,后一半用于存储输出序列
    • stack_top:栈顶指针,指向栈中下一个空位置

  • stack_permutation函数的逻辑如下:

    • 如果out_idx等于n,则表示所有元素已经出栈。此时,我们将计数器加1,并输出当前的输出序列。
    • 如果stack_top大于0,表示栈非空,我们可以进行出栈操作。首先将栈顶元素出栈并保存到输出序列中,然后递归调用stack_permutation。递归调用返回后,需要将刚刚出栈的元素重新入栈,以便尝试其他可能的操作。
    • 如果in_idx小于n,表示还有元素可以入栈。将当前输入序列中的元素入栈,然后递归调用stack_permutation。

  • 在main函数中:

    • 获取用户输入的序列长度n。
    • 创建一个大小为n的input数组,用于存储用户输入的入栈序列。
    • 使用一个循环从用户处读取入栈序列。
    • 创建一个大小为2 * n的stack数组。前一半用于模拟栈,后一半用于存储输出序列。
    • 调用stack_permutation函数,传入input数组、序列长度、初始索引和栈顶指针。
    • 最后,输出计数器的值作为所有可能的出栈序列的个数。




这个代码允许用户输入自定义的入栈序列,并输出所有可能的出栈序列及其个数。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 02:24

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表