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

字符全排列(2)

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

【题目描述】

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


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

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

分享给朋友：
返回列表

上一篇：字符全排列

下一篇：质数环

相关文章

【题解】背包问题2

【题目描述】设有 n 中物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为 m ，今从 n 种物品中选取若干件（同一物品可以多次选取），使其重量的和小于等于 m...

糖果传递

题目描述有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。输入格式第一行一个正整数n≤1000000，表示小朋友的个数．接下来n行，每行一个整数ai，表...

【题解】夹角

【题目描述】这次童鞋们面临的问题是这样的：在一个平面内有两个点，求两个点分别和原点的连线的夹角的大小。注：夹角的范围[0，180]，两个点不会在圆心出现。【输入描述】输入数据的第一行是一个数据T，表示...

【题解】老王赛马

【题目描述】赛马是一古老的游戏，早在公元前四世纪的中国，处在诸侯割据的状态，历史上称为“战国时期”。在魏国作官的孙膑，因为受到同僚庞涓的迫害，被齐国使臣救出后，到达齐国国都。 赛马是当时最受...

【题解】Power Strings

【题目描述】给定若干个长度 ≤106 的字符串，询问每个字符串最多是由多少个相同的子字符串重复连接而成的。如：ababab 则最多有 3 个 ab 连接而成。【输入描述】输入若干行，每行有一...

【题解】连通块

【题目描述】一个n × m的方格图，一些格子被涂成了黑色，在方格图中被标为1，白色格子标为0。问有多少个四连通的黑色格子连通块。四连通的黑色格子连通块指的是一片由黑色格子组成的区域，其中的每个黑色格子...

鲁ICP备20008475号

Powered By Z-BlogPHP. Theme by TOYEAN.