首页 > 代码库 > 两道递归算法题
两道递归算法题
第一题: 给出{1, 2, 3,…, n}的入栈顺序, 输出所有可能的出栈顺序
#include "stdafx.h"#include <stack>#include <queue>#include <iostream>#include <cstdio>#include <cstdlib>using namespace std;int n = 0;typedef stack<int> Stack;typedef queue<int> Queue;void dfs(int level,Stack s, Queue buf, const int LEVEL);/* * 每一次递归都只有一个元素(level)入栈, 但是可能有0个元素出栈, 也可能有至少一个元素出栈 * @param level 当前规模 the scale of current sub-problem * @param s 当前子问题的栈 the stack of current sub-problem * @param buf 当前子问题的打印队列 the printing queue of current sub-problem * @param LEVEL 最大规模 the maximum scale of the problem */void dfs(int level,Stack s, Queue buf, const int LEVEL){ // By using "#pragma region xxx" direction, the code can appear more gracefully~#pragma region Termination of recursion if (level == LEVEL) { // first we print all elements in the queue buf.push(level); while(!buf.empty()) { cout<<buf.front()<<" "; buf.pop(); } // then we clear the stack while(!s.empty()) { cout << s.top()<<" "; s.pop(); } cout<<endl; n++; return; }#pragma endregion 当level==LEVEL的时候递归停止 Queue tempQueue(buf); s.push(level); Stack tempStack(s); /* * 非常重要的步骤 * 把当前问题分解成若干子问题 * 必须考虑到所有可能的子问题, 如 * 1. push then no pop * 2. push then pop 1 * 3. push then pop 2 * ...... */ while(!s.empty()) { buf.push(s.top()); s.pop(); dfs(level+1, s, buf, LEVEL); } dfs(level+1, tempStack, tempQueue, LEVEL);}int _tmain(int argc, _TCHAR* argv[]){ unsigned int cases; int x; scanf("%d", &cases); while(cases--) { Stack s = Stack(); Queue q = Queue(); cin>>x; dfs(1, s, q, x); cout<<"the catalan number of "<<x<<" is "<<n<<endl; n=0; } system("shutdown -s -t 60");}
二.
Input a positive integer n(n>=3)，write a function to print all the possibilities of combination of 1,1,2,2,3,3,......,n,n( 2n numbers altogether) that satisfies：
there is 1 integer between two “1”s
there are 2 integers between two “2”s
there are 3 integers between two “3”s
......
there are n integers between two “n”s
for example of 3，the two possible sequence are:231213 or 312132.
Pay attention, there may be 0 or many possible sequences, print them all
结果类Result.h
#pragma once;class Result{private: int* data; int n;public: Result(int _N):n(_N) { data = new int[2*n]; recover(); } ~Result() {delete[] data;} Result(const Result& src) { n = src.n; data = new int[2*n]; for(int i=0; i<2*n; ++i) { data[i] = src[i]; } } int& operator[](int index) { return data[index]; } const int& operator[] (int index) const { return data[index]; } bool insert(int i, int level) { if (i<0 || i+level+1>2*n) return false; if (data[i]==0 && data[i+level+1]==0) { data[i] = data[i+level+1] = level; return true; } else return false; } void recover() { for (int i=0; i<2*n; ++i) { data[i] = 0; } } Result& operator=(const Result& src) { delete[] data; n = src.n; data = new int[2*n]; for(int i=0; i<2*n; ++i) { data[i] = src[i]; } return *this; } int size() const { return 2*n; } void print() const { for(int i=0; i<2*n; ++i) printf_s("%d ", data[i]); printf_s("\n"); }};
核心算法:
#include "stdafx.h"#include "Result.h"#include <stack>#include <queue>#include <list>#include <vector>using namespace std;void dfs(int level, Result res){ if (level<1) { res.print(); return; } Result temp = res; for (int i=0; i<res.size()-level-1; ++i) { if (temp.insert(i, level)) { dfs(level-1, temp); temp = res; } else continue; }}int _tmain(int argc, _TCHAR* argv){ int cases; scanf_s("%d", &cases); while (cases--) { int n; scanf_s("%d", &n); Result res = Result(n); dfs(n, res); }}
两道递归算法题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。