题目类型:搜索题

题目链接:http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=2319

题目分析:此题数据范围比较的大 ,直接暴力穷举的话肯定会超时,因为这样的数毕竟只占了少数,可以用搜索做,既不会超时,也不会超内存。假如给定的是四位数,先搜一位数的,是素数的继续往后面搜索,不是素数的就不用往下了,在第一位是素数的基础上再搜索第二位,依次往下,直到第四位,然后结束。

代码如下:

//BFS广度优先搜索
#include<iostream>
#include<queue>
#include<cmath>
using namespace std;

queue<int> Q;
int n;

int isprime(int n){  //判断一个数是否是素数
 int i,k=sqrt(n*1.0);
 if(n==1) return 0;
 for(i=2;i<=k;i++)
  if(n%i==0)
   return 0;
 return 1;
}

void BFS(){
 int t=0,len,m,i,j;
 for(i=2;i<10;i++){ //先把一位数的素数进队列
  if(isprime(i))
   Q.push(i); 
 }
 while(!Q.empty()){  //队列为空则表示结束了
  t++;
  len=Q.size();   //记录每一层的个数
  for(i=1;i<=len;i++){  //分别出队列,向高位扩展
   m=Q.front();
   Q.pop();    //删除队头元素
   if(t==n){   //如果找到n位数的整数,则表示队列中全部是n位
               //数的整数,不要再进队列,直接输出队列中的元素即可。
    cout<<m<<endl;
    continue;
   }
   else for(j=1;j<10;j++) //增加一位数,如果是素数,则进队列
    if(isprime(m*10+j))
     Q.push(m*10+j);
  }
 }
}

int main(){
 cin>>n;
 BFS();
 return 0;
}

//广度优先搜索
#include<iostream>
#include<cmath>
using namespace std;

int n;

int isprime(int n){  //判断一个数是否是素数
 int i,k=sqrt(n*1.0);
 if(n==1) return 0;
 for(i=2;i<=k;i++)
  if(n%i==0)
   return 0;
 return 1;
}

void DFS(int m,int t){
 //t定义成局部变量,便于回溯时t的值自动减小
 int i;
 if(t>n) return ;  //如果现在的这个数m的位数大于n位,则返回
 if(t==n)          //如果现在的这个数m的位数等于n位,则输出
  cout<<m<<endl;
 for(i=1;i<10;i++)   //增加一个位数,先判断是否是素数,是素数继续往下搜索
  if(isprime(m*10+i))
   DFS(m*10+i,t+1);
}

int main(){
 cin>>n;
 DFS(0,0);
 return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation