出题人: 描述 设有n个整数的集合{1,2,…,n},从中取出任意r个数进行排列(1<=r<n<=10),试列出所有的排列。 输入描述 输入两个整数,第一个为整数的个数n,第二个为取出的数r. 输出描述 输出一个整数为所以排列的个数。 用例输入 1 4 3 用例输出 1 24c++代码用DFS不用vector
时间: 2024-04-13 22:28:21 浏览: 25
```cpp
#include <iostream>
using namespace std;
int count = 0;
void dfs(int n, int r, bool* visited, int* path, int depth) {
if (depth == r) {
count++;
return;
}
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
visited[i] = true;
path[depth] = i;
dfs(n, r, visited, path, depth + 1);
visited[i] = false;
}
}
}
int main() {
int n, r;
cin >> n >> r;
bool* visited = new bool[n + 1];
int* path = new int[r];
for (int i = 0; i <= n; i++) {
visited[i] = false;
}
dfs(n, r, visited, path, 0);
cout << count << endl;
delete[] visited;
delete[] path;
return 0;
}
```
这段代码使用了深度优先搜索(DFS)来生成所有的排列。我们定义一个布尔数组`visited`用于标记某个整数是否已被访问,一个整数数组`path`用于存储当前的排列。
在搜索过程中,我们从1到n的整数中选择一个未被访问的整数,将其标记为已访问,并将其加入到`path`中。然后,我们继续递归搜索剩余的整数。当我们选择了`r`个整数时,就得到了一个排列,我们将计数器`count`加一。最后,我们将已访问的整数标记为未访问,以便进行下一轮搜索。
这样,我们就可以生成所有的排列,并输出它们的个数。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)