考查递归 回溯
测试输入:
4
aacc
预期输出:
aacc
acac
acca
caac
caca
ccaa
6
思路:
全排列表示把集合中元素的所有按照一定的顺序排列起来,使用P(n, n) = n!表示n个元素全排列的个数。P(n, n)中的第一个n表示元素的个数,第二个n表示取多少个元素进行排列。
给定一个n个元素数组,其全排列的过程可以描述如下:
(1)任意取一个元素放在第一个位置,则有n种选择;
(2)再剩下的n-1个元素中再取一个元素放在第二个位置则有n-1种选择,此时可以看做对n-1个元素进行全排列;
(3)重复第二步,直到对最后一个元素进行全排列,即最后一个元素放在最后一个位置,全排列结束。
以数组{1,2,3}为例,其全排列的过程如下:
(1)1后面跟(2,3)的全排列;
(2)2后面跟(1,3)的全排列;
(3)3后面跟(1,2)的全排列。
去重的时候 是从前往后去重的
不然就不是样例的样子了 其实怎么去重都能得到个数
bool findsame(int idx,int m){
for(int i = idx; i < m;i++)
if(ch[m]==ch[i]) return 1;
return 0;
}
过题代码:
#include<stdio.h>
#include<iostream>
using namespace std;
int n,cnt = 0;
char ch[550];
int a[550];
void sswap(int a,int b){
char tmp = ch[a];
ch[a] = ch[b]; ch[b] = tmp;
}
bool findsame(int idx,int m){
for(int i = idx; i < m;i++)
if(ch[m]==ch[i]) return 1;
return 0;
}
//通过交换和挪动位置来实现排列
void p(int len,int idx){
if(idx==len-1){
for(int i = 0; i < n;i++)
printf("%c",ch[i]);
printf("\n"); cnt ++;
}else{
for(int i = idx;i<len;i++){
// cout<<idx<<" "<<i<<" "<<ch[i]<<" "<<findsame(idx,i)<<endl;
if(findsame(idx,i)) continue;
sswap(idx,i);
p(len,idx+1);
sswap(idx,i);
}
// cout<<"idx: "<<idx<<" "<<ch<<endl;
}
return;
}
int main(){
scanf("%d\n",&n) ;
for(int i = 0; i < n;i++)
scanf("%c",&ch[i]);
p(n,0);
printf("%d",cnt);
return 0;
}
今天的文章递归排序算法原理_递归优化手段分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/83471.html