输入任意正整数n(n>=3),要求输出由1,1,2,2,3,3,......,n,n等2n个数组成的数列,使得: 两个“1”之间有1个数 两个“2”之间有2个数 两个“3”之间有3个数 ...... 两个“n”之间有n个数 如输入3,则输出231213或312132 ...... 具体要求如下: (1)符合要求的排列可能有多个,也可能没有。要求输出全部满足条件的排列,或者打印没有相关排列的信息;(5分) (2)问题的规模n是变化的,因此要求用malloc/new申请空间,用free/delete释放空间;(5分) (3)要求数据存在数组中,用非递归(即迭代)的方式实现算法,不允许用递归来实现;(30分) (4)代码拥有尽可能低的时间复杂度和空间复杂度;(5分)
时间: 2024-02-11 09:04:44 浏览: 31
好的,以下是C++的代码实现,使用了动态内存分配和迭代的方式实现算法,时间复杂度为O(n!),空间复杂度为O(n):
```c++
#include <iostream>
#include <stack>
#include <cstring>
using namespace std;
void print_arr(int *arr, int n) {
for (int i = 0; i < n; i++) {
cout << arr[i];
}
cout << endl;
}
void swap(int *arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
bool is_valid(int *arr, int n) {
int counts[n + 1];
memset(counts, 0, sizeof(counts));
for (int i = 0; i < 2 * n; i++) {
counts[arr[i]]++;
if (counts[arr[i]] > i / 2 + 1) {
return false;
}
}
return true;
}
void find_permutation(int n) {
int *arr = new int[2 * n];
for (int i = 0; i < n; i++) {
arr[i * 2] = arr[i * 2 + 1] = i + 1;
}
stack<int> s;
int i = 0;
bool found = false;
while (i < 2 * n) {
if (s.empty() || s.top() <= arr[i]) {
s.push(i);
i++;
if (i == 2 * n) {
if (is_valid(arr, n)) {
print_arr(arr, 2 * n);
found = true;
}
}
} else {
int j = s.top();
s.pop();
for (int k = i; k < 2 * n; k++) {
if (s.empty() || s.top() <= arr[k]) {
swap(arr, j, k);
s.push(j);
i = j + 1;
break;
}
}
}
}
if (!found) {
cout << "No valid permutations." << endl;
}
delete[] arr;
}
int main() {
int n;
cout << "Enter n: ";
cin >> n;
find_permutation(n);
return 0;
}
```
在这里,我们首先使用动态内存分配来创建一个大小为2n的整型数组arr来存储数列。在is_valid函数中,我们使用一个counts数组来记录每个数出现的次数,如果发现某个数出现的次数超过了限制,就返回false。在find_permutation函数中,我们使用一个栈来记录回溯过程中需要回溯的位置。如果栈为空,或者栈顶元素小于等于当前元素,就将当前元素加入栈中,并继续向后遍历。否则,就从栈中取出最后一个需要回溯的位置j,然后从当前位置i开始向后遍历,找到第一个大于等于栈顶元素的位置k,并将位置j和k上的元素交换。然后将位置j重新加入栈中,并将i更新为j+1。如果遍历完所有元素后发现存在合法的排列,就将其输出。如果没有找到合法的排列,就输出提示信息。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.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)