首页 > 代码库 > UVA110- Meta-Loopless Sorts(模拟全排列)
UVA110- Meta-Loopless Sorts(模拟全排列)
题目链接
题意:给你n个数,要求按照题目所给的规则大小排序,输出所有可能的结果。
思路:其实求出来的所有序列是n个数的全排列,那么难点在于怎么按照题目所给的格式输出。我们可以看出其实是在已知的序列上插空,所以就可以使用回溯来插入元素,这里可以使用vector,方便元素的插入。
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int MAXN = 10; char str[MAXN]; int n; void space(int cnt) { for(int i = 0; i < cnt; i++) printf(" "); } void deal(int cur, vector<char> &s) { if (cur == n) { space(n); printf("writeln("); printf("%c", s[0]); for (int i = 1; i < n; i++) printf(",%c", s[i]); printf(")\n"); return; } else { for (int i = cur; i >= 0; i--) { space(cur); if (i < cur) printf("else "); if (i) printf("if %c < %c then", s[i - 1], cur + 'a'); printf("\n"); vector<char> ss(s); ss.insert(ss.begin() + i, 'a' + cur); deal(cur + 1, ss); } } } int main() { int cas; scanf("%d", &cas); while (cas--) { scanf("%d", &n); for (int i = 0; i < n; i++) str[i] = 'a' + i; printf("program sort(input,output);\nvar\n"); printf("%c", str[0]); for (int i = 1; i < n; i++) printf(",%c", str[i]); printf(" : integer;\nbegin\n"); printf(" readln(%c", str[0]); for (int i = 1; i < n; i++) printf(",%c", str[i]); printf(");\n"); vector<char> s; s.push_back('a'); deal(1, s); printf("end.\n"); if (cas) printf("\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。