首页 > 电脑常识 > 电脑常识

DFS1205素数环(STL队列,栈,DFS,递归)算法

admin 电脑常识 2021-04-26 15:55:23 队列   算法   数据结构  
后台-系统设置-扩展变量-手机广告位-内容正文底部

素数环:

只能被1和自己整除的数,1不是素数,2是最小的素数
素数环是指将从1到n这n个整数围成一个圆环,若其中任意2个相邻的数字相加,结果均为素数,那么这个环就成为素数环(比如1 2 3 4,1 6 5 2 3 4)
要求:输出所有素数环
提示:用到表和队列,如果n为奇数,不构成素数环

样列

Input
6
Output
1 4 3 2 5 6
4 3 2 5 6 1
3 2 5 6 1 4
2 5 6 1 4 3
5 6 1 4 3 2
6 1 4 3 2 5
1 6 5 2 3 4
6 5 2 3 4 1
5 2 3 4 1 6
2 3 4 1 6 5
3 4 1 6 5 2
4 1 6 5 2 3
Sample Input
4
Sample Output
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
1 4 3 2
4 3 2 1
3 2 1 4
2 1 4 3

详情看代码注释

#include<bits/stdc++.h>
using namespace std;
int DE[100];//储存数据
int SUM[100];//记录是否访问过

int n =1;
int Prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
queue<int> Q;
bool prime(int s)
{
    int i;
for( i=0;i<25;i++)
    if(Prime[i]==s)
        return 1;
        if(i==25)
            return 0;

}
void clear()
{
    while(!Q.empty())Q.pop();  //清空Q

    Q.push(1);
}
void Display()
{
    int temp=Q.back();

    for(int j=0;j<n;j++)  //循环遍历,打印队列
    {

         for(int i=0;i<n;i++)
          {    int TE=Q.front();
              cout<<Q.front()<<" ";
              Q.pop();
              Q.push(TE);
          }
          cout<<endl;
        int g=Q.front();
        Q.pop();
        Q.push(g);
        //cout<<g<<endl;

    }
        clear();//将队列清空,也可选择存入栈

}
void DFS(int num)
{
    for(int i=2;i<=n;i++)
    if(num==n&&prime(DE[0]+DE[num-1]))//如果满且队列头与队列位之和为素数
    {

        for(int i=1;i<num;i++)  //把数组的值入栈
          Q.push(DE[i]);


        Display();
        return;
    }
    else
    {

        if(prime(DE[num-1]+i)&&SUM[i]!=1) //当层未使用过且相邻两者相加为素数
        {   //cout<<i<<" ";
            SUM[i]=1;
            DE[num++]=i;
            DFS(num);
            SUM[i]=0;//遍历回来的时候将一切恢复至当层原样
            DE[num--]=0;

        }

    }
}
int main()
{
    cin>>n;
    SUM[1]=1;
    Q.push(1);
    DE[0]=1;
    DFS(1);

}

有事请@王也枉不了

文章来源:https://blog.csdn.net/wxk0123456789/article/details/116113895

后台-系统设置-扩展变量-手机广告位-内容正文底部
版权声明

本文仅代表作者观点,不代表本站立场。
本文系作者授权发表,未经许可,不得转载。
本文地址:https://jcdi.cn/diannaochangshi/diannaochangshi/627.html

留言与评论(共有 0 条评论)
   
验证码:
后台-系统设置-扩展变量-手机广告位-评论底部广告位

教程弟

https://www.jcdi.cn/

统计代码 | 京ICP1234567-2号

Powered By 教程弟 教程弟

使用手机软件扫描微信二维码