hdu 2016 소수 링

5799 단어 HDU
소수 고리, 고전적인 검색 문제.
선단수를 배운 후에 귀착에 대해 약간의 체득을 얻었기 때문에 이 문제를 쓰는 것은 그래도 괜찮다.
ans는 다음 수를 찾아서
 
 ,

 。

 , , 。

ans , 、

#include<stdio.h>

int ss[41],visit[21],b[21];

void getss()

{

    int i,j;

    for(i=1;i<=40;i++)

        ss[i]=1;

    ss[1]=0;

    for(i=2;i<=7;i++)

        for(j=i*i;j<=40;j=j+i)

            ss[j]=0;

}

void bfs(int ans,int n)

{

    int i;

    if(ans==n+1&&ss[b[ans-1]+1]==1)

    {

        for(i=1;i<=n;i++)

        {

            if(i==1)printf("%d",b[i]);

            else printf(" %d",b[i]);

        }

        printf("
"); return ; } for(i=2;i<=n;i++) { if(visit[i]==0) if(ss[i+b[ans-1]]==1) { visit[i]=1; b[ans]=i; bfs(ans+1,n); visit[i]=0; } } } int main() { int i,t=0,n; getss(); while(scanf("%d",&n)>0) { for(i=1;i<=n;i++) visit[i]=0; visit[1]=1; b[1]=1; printf("Case %d:
",++t); if(n%2==1) {printf("
");continue;} // , 。 bfs(2,n); printf("
"); } return 0; }

 

좋은 웹페이지 즐겨찾기