【C/C++】全排列及素数环问题

全排列

问题描述：将n个互不相同的数全排列，即1，2，······n
方法：dfs

算法思路：

dfs(从第一层开始){
    if(递归结束条件){
        遍历a[i]
    }
    打印换行
    for(循环n个位数) {
        if(当前数字没用过){
            第k层（第k个位置）填数字i
            标记置为1
            进入下一层
            标记重新置0
        }
    }
}

代码：

#include<stdio.h>

int n,flag[100],a[100];
void dfs(int k){
    if(k==n+1){   //递归结束条件，当到达第n+1层，代表第n层已经填完
        for(int i=1;i<=n;i++){
            printf("%d ",a[i]);
        }
        printf("\n");
    }
    for(int i=1;i<=n;i++){  //n个数字 
        if(flag[i]==0){  //当前数字没用过才可以排列
            a[k]=i;      //第k层（第k个位置）填数字i
            flag[i]=1;   //该数已经用过，置为1
            dfs(k+1);    //填下一层（下一个位置）
            flag[i]=0;   //递归回来的时候需要重新置为0 
        }
    }
}
int main()
{
	scanf("%d",&n);
	dfs(1);     //从第一层（第一个位置）开始排列 
	return 0;
}

n个数选m个数全排列

#include<stdio.h>

int n,m,flag[100],a[100];
void dfs(int k){
    if(k==m+1){   //递归结束条件，当到达第n+1层，代表第n层已经填完
        for(int i=1;i<=m;i++){
            printf("%d ",a[i]);
        }
        printf("\n");
    }
    for(int i=1;i<=n;i++){  //n个数字
        if(flag[i]==0){  //当前数字没用过才可以排列
            a[k]=i;      //第k层（第k个位置）填数字i
            flag[i]=1;   //该数已经用过，置为1
            dfs(k+1);    //填下一层（下一个位置）
            flag[i]=0;   //递归回来的时候需要重新置为0
        }
    }
}
int main()
{
	scanf("%d %d",&n,&m);
	dfs(1);     //从第一层（第一个位置）开始排列
	return 0;
}

n个不同的元素，任取m个数进行组合。（组合无序）

#include<stdio.h>

int n,m;
int a[1000];

void dfs(int k){
	if(k==m+1){  //递归结束条件，当到达第m+1层，代表第m层已经填完
		for(int i=1;i<=m;i++){
			printf("%d ",a[i]);
		}
		printf("\n");
	}
	//当前位置数值比前一个数至少大1，a[k]代表当前位置上的值，它的范围是[a[k-1]+1,n]
	for(int i=a[k-1]+1;i<=n;i++){
		a[k]=i;   //第k层（第k个位置）填数字i
		dfs(k+1);    //填下一层（下一个位置）
	}
}

int main(){
	scanf("%d %d",&n,&m);
	dfs(1);  //从第一层（第一个位置）开始排列
	return 0;
}

素数环

题目：
素数环:把从 1 到 n 这 n 个数摆成一个环，要求相邻两个数的和是一个素数，编
程求出所有解法。

#include<stdio.h>
#include<math.h>

int n=6;
int flag[100],a[100];
int exist = 0;

int prime(int n){
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0){
            return 0;
        }
    }
    return 1;
}

void dfs(int k){
    if(k==n+1 && prime(a[1]+a[k])){
        for(int j=1;j<=n;j++){
            printf("%d",a[j]);
            exist = 1;
        }
        printf("\n");
    }
    else{
        for(int i=1;i<=n;i++){
            if(flag[i]==0 && (k==1 || prime(i+a[k-1]))){
                a[k]=i;
                flag[i]=1;
                dfs(k+1);
                flag[i]=0;
            }
        }
    }
}

int main(){
	dfs(1);
	if(flag == 0)
        printf("无解");
	return 0;
}