蓝桥杯算法提高VIP-特殊的质数肋骨-题解（C++代码）

解题思路:
用了递归和深度优先

深度优先看的《啊哈！算法》非常容易就能掌握
注意事项:
1.注意时间会超限，所以在set函数里的for循环没有用i从0到9，而是先建立两个全局数组，用全局数组来设置

（经观察可以得到最高位的数只能是2，3，5，7；其余位数只能是1，3，7，9）

2.在判断是否是质数的judge函数里也可以优化一下
参考代码:

#include<iostream>
using namespace  std;
int F[] ={2,3,5,7};
int L[]={1,3,7,9};

int judge(int x)  //判断是否是质数 
{
	int i;
	for(i=2;i*i<=x;i++)  //判断质数用小于等于，以免4被误认为是质数 ,用i*i<=x代替i<=x/2缩短时间 
	{
		if(x%i==0)
			return 1; //不是质数返回1 
	}
	return 0;//是质数返回 0 
}

int JUDGE(int m,int sign)//sign初始值为0，表示默认是质数 
{
	if(m==0)
	{
		return sign;
	 } 
	 if(sign==0) 
		sign=judge(m);  //上一步是质数才判断，上一步不是质数不需要再去判断是不是， 
	JUDGE(m/10,sign);
}

int show(int a[],int n)
{
	int i;
	for(i=0;i<n;i++)
	{
		cout<<a[i];
	}
	cout<<endl;
}



int tran(int a[],int x,int m) //返回数组的值 
{
	if(x==0)
	{
		m=a[x];	
		return m;	
	}
	m=tran(a,x-1,0)*10+a[x];

} 

void set(int x,int n,int a[])//x是当前的数字位置 
{
	int i;  //i是要放入的数字 	
	
	if(x==n)
	{
		if(JUDGE(tran(a,n-1,0),0)==0)
			show(a,n);
		return;		
	}
		
	if(x==0)
	{
		for(i=0;i<4;i++)
		{
			a[x]=F[i];
			set(x+1,n,a);		
		}
	} 
	else {
		for(i=0;i<4;i++)
		{
			a[x]=L[i];
			set(x+1,n,a);		
		}
	}
	return;

}

int main()
{
	int n;
	cin>>n; //N是长度
	int a[n];
 	set(0,n,a);
	return 0;
}