当前位置：首页 > 题解目录 > 正文内容

字符全排列(2)

亿万年的星光5年前 (2021-01-28)题解目录2169

【题目描述】

从n个字符(n从a开始，依次递增)中选取r个字符，对r个字符进行不重复排列。字典序小的在前面。

【输入描述】

一行，n和r

【输出描述】

r个字符的所有组合，每种组合占一行，字符和字符之间用空格隔开。

【样例输入】

3 2

【样例输出】

a b
a c
b c

【样例说明】

数字3代表c，就是从a,b,c三个中任选两个进行不重复组合。

【题目分析】

(1)一道搜索与回溯的题目,不同的是要输出不重复的组合
(2)可以直接对字符进行操作
(3)因为题目比较特殊，可以直接对数字排序， 然后由数字转换成字符

【参考代码1】

#include<bits/stdc++.h>
using namespace std;
int n,r; //定义一共几个数，需要选几个数
int pd[100],ans[100];//pd数组是判断是否用过这个数，ans是结果数组
void print() { //输出函数
   int i;
   for(i=1; i<=r; i++) //根据规模范围输出
       printf("%c ",ans[i]+'a'-1);//由原来的数字改成字符
   cout<<endl;
}
void dfs(int k) { //深搜函数，当前是第k格
   int i;
   if(k==r){ //填满了的时候
       print();//输出当前解
       return;
   }
   for(i=ans[k]; i<=n; i++) { //1-n循环填数,先从上一步的数据开始，
       if(pd[i]==0) { //如果当前数没有用过
           pd[i]=1;//标记一下,1表示当前这个数字使用过
           ans[k+1]=i;//把这个数填入结果数组
           
           dfs(k+1);//填下一个
           pd[i]=0;//回溯
       }
   }
}
int main() {
   cin>>n>>r;//读入规模和要选几个数
   ans[0]=1;// 因为要用到上一步的值，所以开始的时候要给初值，不然就会取到0
   dfs(0);//注意，这里是从第0格开始的！
   return 0;
}


扫描二维码推送至手机访问。

版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。

分享给朋友：
返回列表

上一篇：字符全排列

下一篇：质数环

相关文章

【题解】自动晾衣机

【题目描述】有一个环形可以晾衣服的衣架，有若干个夹子组成，它可以晾不同长度的衣服（占用多个夹子），并且每两件衣服中间要有一个空夹子作为空位，下面需要依次晾干几件长度不一的衣服，请你给出某个夹子的使用情...

线段

题目描述在一个数轴上有n条线段，现选取其中k条线段使得这k条线段两两没有重合部分，问最大的k为多少?输入格式第一行为一个正整数n，下面n行每行2个数字ai，bi，描述每条线段。输出格式输出文件仅包括1...

【题解】舞蹈机器人

题目描述在一个拥有无限大小的二维平面的原点处，有一个舞蹈机器人，这个机器人将在这个平面上跳舞。这个机器人每次可以向自己的前方移动一个单位的长度，由于它需要在移动的过程中跳舞，因此，舞蹈机器人每移动一次...

【题解】校运会

【题解】校运会

【题目描述】校运会上，一共有N个参赛选手，已知N个选手的名字。然后老师告诉你M句话，话的内容是学生A与学生B在同一组里。如果学生A与学生B在同一组里，学生B与学生C也在同一组里，就说明学生A与学生C在...

【题解】结构体与闰年

【题目描述】定义一个结构体变量（包括年、月、日）。计算该日在本年中是第几天，注意闰年问题。【输入描述】年月日【输出描述】当年第几天【样例输入】2000 12 31【样例输出】366...

【题解】循环比赛日程表

【题解】循环比赛日程表

【题目描述】设有N个选手进行循环比赛，其中N=2M，要求每名选手要与其他N-1名选手都赛一次，每名选手每天比赛一次，循环赛共进行N-1天，要求每天没有选手轮空。【输入描述】输入：M。【输出描述】输出：...

鲁ICP备20008475号

Powered By Z-BlogPHP. Theme by TOYEAN.