[已解决]C++

黎子卿

描述
错排问题：编号是1、2、…、n的n封信，装入编号为1、2、…、n的n个信封，要求每封信和信封的编号不同，问有多少种装法。

走楼梯时，每次能跨一级、二级、……、n级，但I级能且仅能跨一次，且要求第i次跨步的大小不能是i级楼梯。n*（n+1）/2级楼梯有几种走法，输出所有的走法

输入
一个正整数n（n<10）
输出
多行，每行表示一种走楼梯的方法
样例输入
3
样例输出
231
312

最佳答案

月排行榜 / 总排行榜

isdkz

2023-11-22 08:09:18

这是一个经典的错排问题和楼梯走法问题。下面是C++的解决方案：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 错排问题
int derangement(int n) {
    if (n == 1) return 0;
    if (n == 2) return 1;
    return (n - 1) * (derangement(n - 1) + derangement(n - 2));
}

// 楼梯走法问题
void dfs(vector<int>& path, vector<vector<int>>& result, int n) {
    if (path.size() == n) {
        result.push_back(path);
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (find(path.begin(), path.end(), i) == path.end()) {
            if (path.empty() || abs(i - path.back()) != path.size() + 1) {
                path.push_back(i);
                dfs(path, result, n);
                path.pop_back();
            }
        }
    }
}

int main() {
    int n;
    cin >> n;

    // 错排问题
    cout << derangement(n) << endl;

    // 楼梯走法问题
    vector<vector<int>> result;
    vector<int> path;
    dfs(path, result, n);
    for (const auto& r : result) {
        for (int i : r) {
            cout << i;
        }
        cout << endl;
    }
    return 0;
}

这段代码首先计算了错排问题的解，然后使用深度优先搜索（DFS）计算了楼梯走法问题的解。

跳转到最佳答案楼层

isdkz

这是一个经典的错排问题和楼梯走法问题。下面是C++的解决方案：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 错排问题
int derangement(int n) {
    if (n == 1) return 0;
    if (n == 2) return 1;
    return (n - 1) * (derangement(n - 1) + derangement(n - 2));
}

// 楼梯走法问题
void dfs(vector<int>& path, vector<vector<int>>& result, int n) {
    if (path.size() == n) {
        result.push_back(path);
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (find(path.begin(), path.end(), i) == path.end()) {
            if (path.empty() || abs(i - path.back()) != path.size() + 1) {
                path.push_back(i);
                dfs(path, result, n);
                path.pop_back();
            }
        }
    }
}

int main() {
    int n;
    cin >> n;

    // 错排问题
    cout << derangement(n) << endl;

    // 楼梯走法问题
    vector<vector<int>> result;
    vector<int> path;
    dfs(path, result, n);
    for (const auto& r : result) {
        for (int i : r) {
            cout << i;
        }
        cout << endl;
    }
    return 0;
}

这段代码首先计算了错排问题的解，然后使用深度优先搜索（DFS）计算了楼梯走法问题的解。