论坛 › 【编程】编程圣殿 › [搜索题]zju_1457

sheep426 发表于 2005-7-21 19:13

[搜索题]zju_1457

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.
http://acm.zju.edu.cn/showimg.php?pid=1457&file=1457.gif
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 发表于 2005-7-21 19:16

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 发表于 2005-7-21 19:17

#include <iostream>
#include <cmath>

using namespace std;

int ring;
int prime;
bool used;


void make_prime()
{
        int i,j;
        bool ok = true;
        for(i = 0;i < 100;i++)
        {
                prime = false;
        }
        prime = 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 + i)&& isprime( ring + i) )
                        {
                                used = true;
                                ring = i;
                                int k;
                                for(k = 1;k<=n;k++)
                                {
                                        if(k == n)
                                        {
                                                cout << ring<<endl;
                                        }
                                        else
                                        {
                                                cout << ring<<\" \";
                                        }
                                }
                               
                                used = false;
                        }
                        else
                        {
                                if(isprime( ring + i))
                                {
                                        used = true;
                                        ring = 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;
                        used=true;
                       
                        search(2,n);
                }
                cout << endl;
        }
}

小康 发表于 2005-7-21 19:21

#include<stdio.h>
int dep,n;
int can={0};
int an;
int use;
int yes;
find()
{
int i,j,k;
k=an;
dep++;
for (i=1;i<can+1;i++) if (use]==1)
   {
      use]=0;
      an=can;
         if (dep==n)
         {
          if (yes+an]==1)
          {
          for (j=1;j<n;j++)
         printf(\"%d \",an);
          printf(\"%d\\n\",an);
         }
         } else
         find();
      use]=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=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==1) {
   can++;
   can]=j;
   can++;
   can]=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=0;
dep=1;
if (n==1) {
   printf(\"\\n\");
} else
find();
printf(\"\\n\");
}
      return 0;
}

查看完整版本: [搜索题]zju_1457