ACM dfs回溯法 Prime Ring Problem

不念不忘少年蓝@ 2022-06-12 07:07 181阅读 0赞

滴，集训第二天打卡。

今天是紫书第七章训练+约瑟夫问题。

约瑟夫问题就是一个公式可以解决的事情~~

基本套路就是：

#include <stdio.h>
    int main()
    {
    	int n,m,i,s=0;
    	scanf("%d%d",&n,&m);
    	for(i=2;i<=n;i++)
    	s=(s+m)%i;
    	printf("%d\n",s+1);
    }

然后今天主要是暴利枚举..其实枚举也是有很多学问的~~~

要尽量让枚举的数少一点...

然后下面贴一道 dfs回溯法的题目

**UVA 524 Prime Ring Problem**

![20170718163038781][]

题目大意:给一个n,让1-n围成圈，满足相邻两个的合是一个素数，满足条件的输出逆时针序列。

我的思路：因为n很小，最大就16，所以可以枚举2\*16以下的素数，然后用isp判断是否为素数。

#include<iostream>
    #include<cstring>
    #include<cmath>
    using namespace std;
    int n;
    int a[20],vis[20];
    int num[12]={2,3,5,7,11,13,17,19,23,29,31,37};
    int isp(int a) //判断是否为素数
    {
        for(int i=0;i<12;i++)
        	if(a==num[i])
    			return 1;
        return 0;
    }
    void dfs(int s)
    {
        if(s==n&&isp(a[1]+a[n])) //递归边界
        {
            for(int i=1;i<n;i++)
            cout<<a[i]<<" ";
            cout<<a[n]<<endl;
        }
        else
        {
            for(int i=2;i<=n;i++)
            {
                if(!vis[i]&&isp(i+a[s]))  //如果i没有用过，并且与前一个数之和为素数
                {
                    a[s+1]=i;
                    vis[i]=1;       //标记  
                    dfs(s+1);
                    vis[i]=0;       //清除标记
                }
            }
        }
    }
    int main()
    {
        int t=0;
        while(cin>>n)
        {
            memset(vis,0,sizeof(vis));
            a[1]=1;
            if(t!=0) 
    		cout<<endl;            
            t++;
            cout<<"Case "<<t<<":"<<endl;
            dfs(1);
        }
        return 0;
    }

[20170718163038781]: /images/20220612/4c191565166f45be9558e57c81e70318.png