首页 > 代码库 > 楼梯问题：输出所有可能的走法
楼梯问题：输出所有可能的走法
楼梯有n阶台阶，上楼可以一步上1阶，也可以一步上2阶，编一程序列出每一种走法。
例：3阶台阶的走法是
{
{ 1, 1, 1, },
{ 1, 2, },
{ 2, 1, },
}
因为每一步只有两个选择1/2阶，那么根据题意可建立一棵二叉树，比如当n=3时：
0 / 1 2 / \ / 1 2 1 / 1
这样（深搜+回溯）一棵树的所有到达叶子节点的路径就是上楼梯的所有方法了
（递归法）C++代码如下：
#include <iostream>
#include <list>
struct Node{ int value = http://www.mamicode.com/0; Node *left = nullptr; Node *right = nullptr;};//@param n 总楼梯数//@param value 步长(1 || 2)//@param cur 当前已走过的总楼梯数void BuildTree(Node *root, int n, int value, int cur = 0){ root->value =http://www.mamicode.com/ value; cur += value; if (cur == n) return; if (cur + 1 <= n) { root->left = new Node; BuildTree(root->left, n, 1, cur); } if (cur + 2 <= n) { root->right = new Node; BuildTree(root->right, n, 2, cur); }}void PrintAll(Node *root, std::list<int> &vec, int cur = 0){ if (root == nullptr) return; cur += root->value; vec.push_back(root->value); if (root->left == nullptr && root->right == nullptr) { for (int i : vec) { if(i != 0) printf("%d ", i); } printf("\n"); } PrintAll(root->left, vec, cur); PrintAll(root->right, vec, cur); vec.pop_back();}void DeleteAll(Node *root){ if (root == nullptr) return; DeleteAll(root->left); DeleteAll(root->right); delete root;}void Compute(int n){ Node *root = new Node; std::list<int> st; BuildTree(root, n, 0); PrintAll(root, st); DeleteAll(root);}int main(){ std::cout << "n = 3 :" << std::endl; Compute(3); std::cout << std::endl; std::cout << "n = 4:" << std::endl; Compute(4);}
（递归法）lua 代码：
--@param n 总楼梯数--@param value 步长(1 || 2)--@param cur 当前已走过的总楼梯数function BuildTree(root, n, value, cur) root.value = value cur = cur + value if cur == n then return end if cur + 1 <= n then root.left = { value = http://www.mamicode.com/0, left = nil, right = nil} BuildTree(root.left, n, 1, cur) end if cur + 2 <= n then root.right = { value = http://www.mamicode.com/0, left = nil, right = nil} BuildTree(root.right, n, 2, cur) endend
function PrintAllPath(root, stack, cur) if root == nil then return end cur = cur + root.value table.insert(stack, root.value) if root.left == nil and root.right == nil then for key, value in pairs(stack) do if value ~= 0 then io.write(value,‘ ‘) end end io.write(‘\n‘) end PrintAllPath(root.left, stack, cur) PrintAllPath(root.right, stack, cur) table.remove(stack)endfunction Compute(n) stack = {} root = { value = http://www.mamicode.com/0, left = nil, right = nil} BuildTree(root, n, 0, 0) --BuildTree(root, n) PrintAllPath(root, stack, 0)endprint("n=3:")Compute(3)io.write(‘\n‘)print("n=4:")Compute(4)io.write(‘\n‘)print("n=5:")Compute(5) 
迭代法(C++):
void BuildTree(Node *root, int n){ if (root == nullptr) return; int cur(0); std::stack<Node*> st; std::map<Node*, int> stepMap;//记录当前已走过的楼梯数 Node *p = root; st.push(p); stepMap[p] = 0; while (!st.empty()) { p = st.top(); st.pop(); cur = stepMap[p]; if (cur + 2 <= n) { p->right = new Node; p->right->value = http://www.mamicode.com/2; if (cur + 2 < n) { st.push(p->right); stepMap[p->right] = cur + 2; } } if (cur + 1 <= n) { p->left = new Node; p->left->value = http://www.mamicode.com/1; if (cur + 1 < n) { st.push(p->left); stepMap[p->left] = cur + 1; } } }}
迭代法（Lua）：
function BuildTree(root, n) if root == nil then return end cur = 0 stack = {} stepMap = {} p = root table.insert(stack, p) stepMap[p] = 0 while(#stack ~= 0) do p = stack[1] table.remove(stack, 1) cur = stepMap[p] if cur + 2 <= n then p.right = {value = http://www.mamicode.com/2, left = nil, right = nil} if cur + 2 < n then table.insert(stack, p.right) stepMap[p.right] = cur + 2 end end if cur + 1 <= n then p.left = {value = http://www.mamicode.com/1, left = nil, right = nil} if cur + 1 < n then table.insert(stack, p.left) stepMap[p.left] = cur + 1 end end endend
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。