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

字符全排列(2)

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

【题目描述】

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


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

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

分享给朋友：
返回列表

上一篇：字符全排列

下一篇：质数环

相关文章

【题解】种花问题

【题目描述】假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。给你一个整数数组 flowerbed 表示花坛，...

【题解】真分数（2019青岛市程序设计竞赛）

【描述】真分数，指的是分子比分母小的分数，真分数的分数值小于1。给出n个正整数，任取两个数分别作为分子和分母组成真分数。求能组成多少不同值的真分数。【输入】第一行是一个正整数n。第二行是n个不同的正整...

【题解】求最长不下降序列

【题目描述】设有由n(1≤n≤200)个不相同的整数组成的数列，记为:b(1)、b(2)、……、b(n)且b(i)≠b(j)(i≠j)，若存在i1<i2<i3<…<ie 且有b...

【题解】电缆线（2019青岛市程序设计竞赛）

【问题描述】在郊区有N座通信基站，P条双向电缆，第 i 条电缆连接基站 A_i 和 B_i。特别地，1号基站是通信公司的总站，N号基站位于一座农场中。现在，农场主希望对通信线路进行升级，其中升级第 i...

【题解】合根植物

【题解】合根植物

【题目描述】w星球的一个种植园，被分成 m * n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成...

【题解】木材加工

【题目描述】 木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头（木头有可能有剩余），需要得到的小段的数目是事先给定的，切割时希望得到的小段越长越好。   ...

鲁ICP备20008475号

Powered By Z-BlogPHP. Theme by TOYEAN.