首页 > 代码库 > C语言 · 排列数 · 排列式

C语言 · 排列数 · 排列式

2024-09-12 09:54:46   220人阅读

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

　　方法二：递归搜索

　

 1 #include<stdio.h>  
 2 #include<string.h> 
 3 int sum=0;  
 4 bool use[10];
 5 int a[10];
 6 void dfs(int begin){  
 7     if(begin==9){  //表示当前数组a中已有9个数字  
 8         int num1=a[0]*1000+a[1]*100+a[2]*10+a[3];
 9         int num2=a[4]*10+a[5];
10         int num3=a[6]*100+a[7]*10+a[8];
11         int num4=a[4];
12         int num5=a[5]*1000+a[6]*100+a[7]*10+a[8];
13         if(num1==num2*num3){
14             printf("%d = %d x %d\n",num1,num2,num3);
15         }
16         if(num1==num4*num5){  
17             printf("%d = %d x %d\n",num1,num4,num5); 
18         }
19         return;
20     }
21     for(int i=1; i<=9; i++){//枚举数字1到数字9
22         if(!use[i]){
23             use[i]=true;
24             a[begin]=i;//数组第一个元素为0 
25             dfs(begin+1);
26             use[i]=false; 
27         }
28     }  
29 }  
30 int main(){
31     memset(use,false,sizeof(use));
32     dfs(0);//对数组a来讲,表示从第 1个位置开始搜索 
33     return 0;
34 }

 

C语言 · 排列数 · 排列式


联系
我们