用c++非递归写排列组合算法

可以使用以下代码实现非递归的排列组合算法：

#include <stdio.h>

int factorial(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

int combination(int n, int k) {
    if (k > n) {
        return 0;
    }
    return factorial(n) / (factorial(k) * factorial(n - k));
}

int permutation(int n, int k) {
    if (k > n) {
        return 0;
    }
    return factorial(n) / factorial(n - k);
}

int main() {
    int n = 5, k = 3;
    printf("%dC%d = %d\n", n, k, combination(n, k));
    printf("%dP%d = %d\n", n, k, permutation(n, k));
    return 0;
}

该代码使用了阶乘函数来计算组合数和排列数，同时使用了条件判断来避免出现无效的计算。

相关问题

用C++编写实现拓扑排序非递归算法

在C++中，我们可以使用邻接表（Adjacency List）的数据结构来实现拓扑排序的非递归算法。拓扑排序主要用于有向无环图（DAG，Directed Acyclic Graph）中，对节点进行线性排列，使得所有的边都是从前面的节点指向后面的节点。

下面是一个简单的非递归算法步骤：

1. 使用哈希表存储每个节点的入度（in-degree），记录有多少条边进入该节点。
2. 遍历图，将所有入度为0的节点加入到结果列表中，并将其出度减1（即减少依赖项）。
3. 对于剩下的节点，如果它们的入度仍然为0，继续加入结果列表。
4. 重复第二步和第三步，直到所有节点都被处理过。

以下是伪代码和部分C++代码实现：

#include <vector>
using namespace std;

class Graph {
private:
    vector<int> indegrees; // 存储每个节点的入度
    vector<vector<int>> adjList; // 邻接表

public:
    void addEdge(int src, int dest) {
        adjList[src].push_back(dest);
        indegrees[dest]++;
    }

    vector<int> topologicalSort() {
        vector<int> result;
        queue<int> q;

        // 初始化：入度为0的节点入队
        for (int i = 0; i < indegrees.size(); ++i) {
            if (indegrees[i] == 0)
                q.push(i);
        }

        while (!q.empty()) {
            int node = q.front();
            q.pop();

            result.push_back(node); // 将节点添加到结果列表
            for (int neighbor : adjList[node]) {
                indegrees[neighbor]--;
                if (indegrees[neighbor] == 0)
                    q.push(neighbor);
            }
        }

        return result.size() == indegrees.size() ? result : vector<int>(); // 如果所有节点都已处理，返回结果；否则表示有循环
    }
};

// 使用示例
Graph g;
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 3);

vector<int> sortedOrder = g.topologicalSort();

用C++写出能排列出数组里每个数字组合后令组合数最大的程序

要在C++中编写一个程序，用于找出数组中所有可能数字组合的最大组合数，通常我们会考虑生成所有可能的子集，并计算它们的数量。这可以通过递归算法（如回溯法）实现。这里是一个简单的例子，假设我们有一个整数数组`arr`：

#include <iostream>
#include <vector>

// 函数用于递归生成并计数数组的所有非空子集
size_t countSubsets(std::vector<int>& arr, size_t start = 0) {
    if (start == arr.size()) { // 当前子集已全部包含，返回1
        return 1;
    }

    // 计算当前数字添加到已有子集后的组合数
    size_t withCurrent = countSubsets(arr, start + 1); // 不包含当前数字

    // 计算当前数字创建新子集的组合数
    size_t withoutCurrent = countSubsets(arr, start + 1); // 包含当前数字

    // 返回总组合数
    return withCurrent + withoutCurrent;
}

int main() {
    std::vector<int> arr = {1, 2, 3}; // 示例数组
    size_t maxCombinations = countSubsets(arr);

    std::cout << "最大组合数是: " << maxCombinations << std::endl;

    return 0;
}

这个程序会打印出给定数组`arr`中所有可能子集的最大组合数。