[搜索题]zju_1457

sheep426

http://acm.zju.edu.cn/show_problem.php?pid=1457
Prime Ring Problem
Time limit: 10 Seconds   Memory limit: 32768K   
Total Submit: 3909   Accepted Submit: 1277   
A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.
Note: the number of first circle should always be 1.

Input
n (0
Output
The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.
You are to write a program that completes above process.
Print a blank line after each case.
Sample Input
6
8
Sample Output
Case 1:
1 4 3 2 5 6
1 6 5 2 3 4
Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2

sheep426

1325067 2005-07-21 18:50:39 Accepted 1457 C++ 00:01.09 932K sheep
虽然过了，可是效率和人家相差太远了
1 2003-05-05 20:38:39 00:00.32 440K C++ mathli

ps
http://acm.stu.edu.cn/cgi-bin/problem?id=3059
和这题很像，不过bt很多

[ Last edited by sheep426 on 2005-7-21 at 19:20 ]

sheep426

#include <iostream>
#include <cmath>

using namespace std;

int ring[22];
int prime[105];
bool used[22];


void make_prime()
{
        int i,j;
        bool ok = true;
        for(i = 0;i < 100;i++)
        {
                prime = false;
        }
        prime[2] = true;
        for(i = 2; i < 100;i++)
        {
                ok = true;
                for(j = 2;j<=sqrt( static_cast<float>(i) );j++)
                {
                        if( i % j == 0)
                        {
                                ok = false;
                                break;
                        }
                }
                if( ok)
                {
                        prime = true;
                }
        }
       
}

bool isprime(int i)
{
        return prime;
}
void search(int pos,int n)
{
        int i;
        for(i = 1; i<=n;i++)
        {
                if(!used)
                {
                        if(pos == n && isprime( ring[1] + i)  && isprime( ring[n-1] + i) )
                        {
                                used = true;
                                ring[pos] = i;
                                int k;
                                for(k = 1;k<=n;k++)
                                {
                                        if(k == n)
                                        {
                                                cout << ring[k]<<endl;
                                        }
                                        else
                                        {
                                                cout << ring[k]<<" ";
                                        }
                                }
                               
                                used = false;
                        }
                        else
                        {
                                if(isprime( ring[pos-1] + i))
                                {
                                        used = true;
                                        ring[pos] = i;
                                        search(pos+1,n);
                                }
                                used = false;
                               
                        }
       
                }
        }
       
}

int main()
{
        int n,i,times=0;
        make_prime();
        while(cin >> n)
        {
                times++;
                cout <<"Case "<<times<<":"<<endl;
                if(n % 2 == 0)
                {
                        for(i = 0;i <22;i++)
                        {
                                used=false;
                        }
                        ring[1] = 1;
                        used[1]=true;
                       
                        search(2,n);
                }
                cout << endl;
        }
}

小康

#include<stdio.h>
int dep,n;
int can[41][41]={0};
int an[81];
int use[81];
int yes[80];
find()
{
int i,j,k;
k=an[dep];
dep++;
  for (i=1;i<can[k][0]+1;i++) if (use[can[k]]==1)
   {
        use[can[k]]=0;
        an[dep]=can[k];
         if (dep==n)
         {
          if (yes[an[dep]+an[1]]==1)
          {
          for (j=1;j<n;j++)
           printf("%d ",an[j]);
          printf("%d\n",an[n]);
           }
         } else
         find();
        use[can[k]]=1;
   }
dep--;
}
int main(int argc, char* argv[])
{
int shu[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67};
int ncase=0,i,j,u,k;
for (i=1;i<20;i++) for (j=0;j<20;j++)     can[j]=0;
for (i=1;i<40;i++)
  {
   yes=1;
   for (j=2;j<=i /2 ;j++) if (i%j==0) {yes=0;break;};

  }

for (i=1;i<20;i++)
  for (j=i+1;j<20;j++)
  {
    k=i+j;
    if (yes[k]==1) {
     can[0]++;
     can[can[0]]=j;
     can[j][0]++;
     can[j][can[j][0]]=i;
    };
  }
  while ( scanf("%d",&n)!=EOF)
  {
  ncase++;
  printf("Case %d:\n",ncase);
  for (i=0;i<=n;i++) use=1;
  i=1;an=1;use[1]=0;
  dep=1;
  if (n==1) {
   printf("\n");
  } else
  find();
  printf("\n");
  }
        return 0;
}