重庆分公司,新征程启航
为企业提供网站建设、域名注册、服务器等服务
整体思路就是利用回溯的思想,也可认为是深度优先搜索
网页设计是网站建设的前奏,好的网页设计更深度的剖析产品和设计风格定位,结合最新的网页设计流行趋势,与WVI应用标准,设计出具企业表现力,大器而深稳的网站界面设。创新互联公司成立于2013年,是成都网站建设公司:提供企业网站设计,品牌网站设计,营销型企业网站建设方案,响应式网站开发,小程序开发,专业建站公司做网站。
从字符串第一位idx=0开始,每次递归都从s[idx]之后选择一个字符与s[idx]交换
因为可能有重复字符,可使用哈希数组标记当前循环每个字符是否被选择
因为字符范围不超过ASCII码,所以使用128空间的数组足够用来标记了
选择好当前字符s[i]并与s[idx]交换之后,递归调用继续排列下一位s[idx+1]
注意这里要进行回溯,即不选s[i]而选择之后的某个字符交换到s[idx]
所以要将之前的s[i]与s[idx]交换过来,恢复原状,才能循环判断下一个选择
具体代码截图如下:
运行结果如下:
结果正确,望采纳~
附源码:
#include stdio.h
#include stdlib.h
#include string.h
#define MAXN 1000000 // 排列总数可能很多
int num = 0; // 记录排列总数
char *res[MAXN] = {NULL}; // 指针数组保存排列结果
void swap(char *x, char *y) { // 交换两个字符变量的内容
char ch = *x;
*x = *y;
*y = ch;
}
void perm(char *s, int n, int idx) { // 回溯产生字符串全排列
if (idx == n) { // 已排列到字符串结尾
res[num] = (char *)malloc(sizeof(char) * (n + 1));
//printf("%s\n", s); // 输出当前排列
strcpy(res[num], s); // 保存当前排列
num++; // 排列总数加1
return;
}
int i, hash[128] = {0}; // 哈希数组,标记每个字符是否被选择
for (i = idx; i n; i++) {
if (hash[s[i]] == 1)
continue; // 跳过已被标记过的重复字符
hash[s[i]] = 1; // 选过的话在数组中标记为1
swap(s[idx], s[i]); // 选择s[i]交换到s[idx]
perm(s, n, idx + 1); // 递归,继续s[idx+1]的选择
swap(s[idx], s[i]); // 回溯,当前不选择s[i],而选择其他字符
}
}
int main() {
int n, i;
scanf("%d", n);
char *s = (char *)malloc(sizeof(char) * (n + 1));
scanf("%s", s);
perm(s, n, 0);
printf("一共有%d种排列:\n", num); // 输出排列总数
for (i = 0; i num; i++) { // 输出所有排列
printf("%s\n", res[i]);
free(res[i]); // 释放内存空间
}
free(s);
return 0;
}
#include iostream
#include stdio.h
#include algorithm
using namespace std;
int main()
{
int num[4]={1,2,3,4};
do
{
printf("%c,%c,%c,%c\n",num[0]+'A'-1,num[1]+'A'-1,num[2]+'A'-1,num[3]+'A'-1);
}while(next_permutation(num,num+4));
return 0;
}
可以借助于stl模板中的next_permutation函数,这个函数是按照字典序不停的取该序列的下一个序列,直到结束。然后输出的时候讲数字转化为你要的字母即可。
例如 第一个序列是1,2,3,4,--》A,B,C,D
我给你举两个简单的列子:题目:输入三个整数x,y,z,请把这三个数由小到大输出。 1.程序分析:我们想办法把最小的数放到x上,先将x与y进行比较,如果xy则将x与y的值进行交换,然后再用x与z进行比较,如果xz则将x与z的值进行交换,这样能使x最小。 2.程序源代码: main() { int x,y,z,t; scanf("%d%d%d",x,y,z); if (xy) {t=x;x=y;y=t;} /*交换x,y的值*/ if(xz) {t=z;z=x;x=t;}/*交换x,z的值*/ if(yz) {t=y;y=z;z=t;}/*交换z,y的值*/ printf("small to big: %d %d %d\n",x,y,z); } 题目:有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位数?都是多少? 1.程序分析:可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去掉不满足条件的排列。 2.程序源代码: main() { int i,j,k; printf("\n"); for(i=1;i5;i++)/*以下为三重循环*/ for(j=1;j5;j++) for (k=1;k5;k++) { if (i!=ki!=jj!=k) /*确保i、j、k三位互不相同*/ printf("%d,%d,%d\n",i,j,k); } } 你的问题很笼统,根本就是让人无从答起,我只是举了其中几个列子而已,如果你还是要执着的话,那我的答案就是你所学的教材,你若能把你的书看懂了,你就不会在问这种问题了,
C语言版:
#includestdio.h
#includestdlib.h
#includestring.h
int a[10], book[10], n, k[10], l;
void dfs(int step)
{
int i = 0;
if(step == l + 1)
{
if(a[1] != 0)
{
for(i = 1; i = l; i++)
{
printf("%d", a[i]);
}
printf("\n");
}
return ;
}
for(i = 0; i l; i++)
{
if(book[k[i]] == 0)
{
a[step] = k[i];
book[k[i]] = 1;
dfs(step + 1);
book[k[i]] = 0;
}
}
}
int main(void)
{
memset(k, 0, sizeof(k));
memset(book, 0, sizeof(book));
int n;
scanf("%d", n);
char buf[15] = "";
sprintf(buf, "%d", n);
l = strlen(buf);
int i = 0;
for(i = 0; i l; i++)
k[i] = buf[i] - '0';
dfs(1);
system("pause");//如果通不过编译就试着删除这句话
return 0;
}
C++版:
#includecstdio
#includecstdlib
#includecstring
int a[10], book[10], n, k[10], l;
void dfs(int step)
{
if(step == l + 1)
{
if(a[1] != 0)
{
for(int i = 1; i = l; i++)
{
printf("%d", a[i]);
}
printf("\n");
}
return ;
}
for(int i = 0; i l; i++)
{
if(book[k[i]] == 0)
{
a[step] = k[i];
book[k[i]] = 1;
dfs(step + 1);
book[k[i]] = 0;
}
}
}
int main(void)
{
memset(k, 0, sizeof(k));
memset(book, 0, sizeof(book));
int n;
scanf("%d", n);
char buf[15] = "";
sprintf(buf, "%d", n);
l = strlen(buf);
for(int i = 0; buf[i] != '\0'; i++)
k[i] = buf[i] - '0';
dfs(1);
return 0;
}