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

字符全排列(2)

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

【题目描述】

从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;
}


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

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

分享给朋友：
返回列表

上一篇：字符全排列

下一篇：质数环

相关文章

【题解】密码截获

【题目描述】Catcher是MCA国的情报员，他工作时发现敌国会用一些对称的密码 进行通信，比如像这些ABBA，ABA，A，123321，但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。...

【题解】高精度除法

【题目描述】高精除以高精，求它们的商和余数。【输入描述】输入两个低于300位的正整数。【输出描述】输出商和余数。【样例输入】12313123184575776878979876423245678643...

【题解—动态规划】背包问题1

【题目描述】一个旅行者有一个最多能装 m 公斤物品的背包，现在有 n 件物品，它们的重量分别是 w1,w2,…,wn, 它们的价值分别为 c1,c2,…cn 。若每种物品只有一件，求旅行者能获得的最大...

【题解】公式成绩

【题目描述】学校的期中考试到了。 gp 老师一共收集到 n 个学生的成绩，每个学生有 5 科成绩，分别是语文、数学、英语、政治、历史。（ai,bi,ci,di,ei） gp 老师突发奇想，他用 m...

【题解】登山

【题解】登山

【题目描述】五一到了，ACM队组织大家去登山观光，队员们发现山上一共有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。同时队员们还有另一个登山习惯，就是不...

文具订购（NOI online入门组）

【题目描述】小明的班上共有n元班费，同学们准备使用班费集体购买3种物品。圆规，每个7元。笔，每支4元。笔记本，每本3元。小明负责订购文具，设圆规、笔、笔记本的订购数量为a,b,c,他订购的原则依次如下...

鲁ICP备20008475号

Powered By Z-BlogPHP. Theme by TOYEAN.