misschuer

常用链接

统计

积分与排名

百事通

最新评论

Prime Ring Problem

#include< iostream >
using namespace std;

int n , a[ 23 ] , visited[ 23 ] , prime[ 23 ];

void dfs(int k)
{
    
    if(k == n)
        if(prime[ a[ 0 ] + a[ n - 1 ] ])
        {
            printf("%d" , a[ 0 ]);
            
            for(int i = 1 ; i < n ; ++ i)
                
                printf(" %d" , a[ i ]);
            
            printf("\n");
            
            return ;
        }
        
        for(int j = 2 ; j <= n ; ++j)
            
            if(visited[ j ])
            {
                if( prime[ a[k - 1] + j ])
                {
                    a[ k ] = j;
                    
                    visited[ j ] = 0;
                    
                    dfs(k + 1);
                    
                    visited[ j ] = 1;
                }
            }
}



int main()
{
    int k = 0 , i , j;
    
    for(i = 2 ; i < 23 ; ++ i)
        
        prime[ i ] = 1;
    
    for(i = 2 ; i < 23 ; ++ i)
        
        if(prime[ i ])
            
            for(j = i + i ; j < 23 ; j += i)
                
                prime[ j ] = 0;
            
            
            
            while(scanf("%d" , &n) != EOF)
            {
                printf("Case %d:\n" , ++ k);
                
                memset(visited , 1 , sizeof(visited));
                
                a[ 0 ] = 1;
                
                dfs(1);

                printf("\n");
            }
            
            return 23;
}

posted on 2009-04-18 10:50 此最相思 阅读(97) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理