蓝桥练习场上不断碰到类似的题，都是一个递归搜索的套路。
算法提高 排列数
时间限制：1.0s 内存限制：256.0MB
问题描述
0、1、2三个数字的全排列有六种，按照字母序排列如下：
012、021、102、120、201、210
输入一个数n
求0~9十个数的全排列中的第n个（第1个为0123456789）。
012、021、102、120、201、210
输入一个数n
求0~9十个数的全排列中的第n个（第1个为0123456789）。
输入格式
一行，包含一个整数n
输出格式
一行，包含一组10个数字的全排列
样例输入
1
样例输出
0123456789
数据规模和约定
0 < n <= 10!
作者注释：标准的递归搜索题，如今这是个套路。
#include<stdio.h>
#include<string.h>
int n,sum=;
bool use[];//用来标记数字i是否被用了，即是否已被放在了排列中
int a[];
void dfs(int begin){
if(begin==){ //表示当前数组a中已有10个数字
sum++;
if(sum==n){
for(int i=; i<; i++)
printf("%d",a[i]);
}
}
for(int i=; i<=; i++){//枚举数字0到数字9
if(!use[i]){
use[i]=true;
a[begin]=i;//数组第一个元素为0
dfs(begin+);
use[i]=false;
}
}
}
int main(){
memset(use,false,sizeof(use));
scanf("%d",&n);
if(n==){
return ;
}
dfs();
return ;
}
算法提高 排列式
时间限制：1.0s 内存限制：256.0MB
问题描述
7254是一个不寻常的数，因为它可以表示为7254 = 39 x 186，这个式子中1~9每个数字正好出现一次
输出所有这样的不同的式子（乘数交换被认为是相同的式子）
结果小的先输出；结果相同的，较小的乘数较小的先输出。
输出所有这样的不同的式子（乘数交换被认为是相同的式子）
结果小的先输出；结果相同的，较小的乘数较小的先输出。
输出格式
每一行输出一个式子，式子中的等号前后空格、乘号（用字母x代表）前后空格
较小的乘数写在前面
较小的乘数写在前面
样例输出
问题中的式子在结果中会出现一行如下：
7254 = 39 x 186
7254 = 39 x 186
方法一：暴力枚举呗，注意判断条件。（运行超时）
#include<stdio.h>
void meiju(){//解题函数
int count=,m,n,x;
int p,q;
for(int a=; a<; a++)
for(int b=; b<; b++)
for(int c=; c<; c++)
for(int d=; d<; d++)
for(int e=; e<; e++)
for(int f=; f<; f++)
for(int g=; g<; g++)
for(int i=; i<; i++)
for(int j=; j<; j++){
//保证1-9只出现一次
if(a!=b&&a!=c&&a!=d&&a!=e&&a!=f&&a!=g&&a!=i&&a!=j&&b!=c&&b!=d&&b!=e&&b!=f&&b!=g&&b!=i&&b!=j&&c!=d&&c!=e&&c!=f&&c!=g&&c!=i&&c!=j&&d!=e&&d!=f&&d!=g&&d!=i&&d!=j&&e!=f&&e!=g&&e!=i&&e!=j&&f!=g&&f!=i&&f!=j&&g!=i&&g!=j&&i!=j){
m=a*+b*+c*+d;
n=e*+f;
x=g*+i*+j;
p=e;
q=f*+g*+i*+j;
if (m==n*x){
count++;
printf("%d=%dx%d\n",m,n,x);
}
if(m==p*q){
count++;
printf("%d=%dx%d\n",m,p,q);
}
}
}
printf("共有%d种。",count);
}
int main(){
meiju();
return ;
}
方法二：递归搜索
#include<stdio.h>
#include<string.h>
int sum=;
bool use[];
int a[];
void dfs(int begin){
if(begin==){ //表示当前数组a中已有9个数字
int num1=a[]*+a[]*+a[]*+a[];
int num2=a[]*+a[];
int num3=a[]*+a[]*+a[];
int num4=a[];
int num5=a[]*+a[]*+a[]*+a[];
if(num1==num2*num3){
printf("%d = %d x %d\n",num1,num2,num3);
}
if(num1==num4*num5){
printf("%d = %d x %d\n",num1,num4,num5);
}
return;
}
for(int i=; i<=; i++){//枚举数字1到数字9
if(!use[i]){
use[i]=true;
a[begin]=i;//数组第一个元素为0
dfs(begin+);
use[i]=false;
}
}
}
int main(){
memset(use,false,sizeof(use));
dfs();//对数组a来讲,表示从第 1个位置开始搜索
return ;
}