首页 > 代码库 > Uva 552 Prime Ring Problem
Uva 552 Prime Ring Problem
题目链接：Uva 552
思路：
时间限制为3s，数据较小，使用深度搜索查找所有的解。
代码：
#include <iostream>#include <string.h>using namespace std;const int MAX_N = 20;int n;int A[MAX_N], vis[MAX_N];int is_prime( int n ){ if ( n == 2 ) return true; for ( int i = 2; i * i <= n; ++i ) if ( n % i == 0 ) return false; return true;}void dfs( int cur ){ if ( cur == n && is_prime( A[0] + A[n - 1] ) ) { int i = 0; for ( i = 0; i < n - 1; ++i ) printf( "%d ", A[i] ); printf( "%d", A[i] ); printf( "\n" ); } else { for ( int i = 2; i <= n; ++i ) { if ( !vis[i] && is_prime( i + A[cur - 1] ) ) { A[cur] = i; vis[i] = 1; dfs( cur + 1 ); vis[i] = 0; } } }}int main( ){ int count = 1; while ( scanf( "%d", &n ) != EOF ) { if ( count != 1 ) printf( "\n" ); A[0] = 1; memset( vis, 0, sizeof( vis ) ); printf( "Case %d:\n", count++ ); dfs( 1 ); } return 0;}
Uva 552 Prime Ring Problem
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。