HDU 1016 Prime Ring Problem （深搜）

本文主要是介绍HDU 1016 Prime Ring Problem （深搜），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

OJ题目 ： click here ~~

大概题意：n个数，形成一个环，使得相邻两个数的和为素数。以1开始，按字典序输出序列。

很简单的深搜。

AC_CODE

int n;
int visit[22];
int num[22];
int len;
bool Is_prime(int x)
{for(int i = 2;i*i <= x;i++)if(x%i == 0) return false;return true;
}void print()
{int i;for(i = 0;i < n - 1;i++)printf("%d ",num[i]);printf("%d\n",num[i]);
}void dfs()
{if(len == n && Is_prime(num[0] + num[n - 1])) {print();return;}for(int i = 2;i <= n;i++){if(visit[i] == 0 && Is_prime(num[len - 1] + i)){visit[i] = 1;num[len] = i;len++;dfs();visit[i] = 0;len--;}}return ;
}int main()
{int t = 0;while(scanf("%d",&n) != EOF){t++;memset(visit , 0 , sizeof(visit));printf("Case %d:\n",t);num[0] = 1;len  = 1;dfs();cout << endl;}return 0;
}

这篇关于HDU 1016 Prime Ring Problem （深搜）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---