理解回溯思想,不懂得怎么运用,还是看着别人模板写的。
代码练得少,继续写。
这个留着思路,思想, 备用。
时间很慢,640ms。以后还要优化。
别人有用DFS做的, 以后还要用DFS AC次
#include <stdio.h> #include <math.h> int ans[21]; int n; //判断素数 int isPrime(int x) { int i, k = ceil(sqrt(x)); for (i = 2; i <= k; i++) if (x % i == 0) return 0; return 1; } int check(int m) { int i; for (i = 1; i < m; i++) if (ans[i] == ans[m]) return 0; return 1; } //一个一个的选。 void PrimeRingPro(int t) { int i; if (t > n) { if (isPrime(ans[1] + ans[n]) && check(n)) for (i = 1; i <= n; i++) printf("%d%c", ans[i], i == n ? '\n' : ' '); } else { for (i = 2; i <= n; i++) { ans[t] = i; if (isPrime(ans[t-1] + ans[t]) && check(t)) PrimeRingPro(t+1); } } } int main() { int i = 1; while (scanf("%d", &n) != EOF) { printf("Case %d:\n", i++); memset(ans, 0, sizeof(ans)); ans[1] = 1; PrimeRingPro(2); printf("\n"); } return 0; }