本文主要是介绍Prime Ring Problem(UVA 524),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
网址如下:
Prime Ring Problem - UVA 524 - Virtual Judge (vjudge.net)
(第三方网站)
没想到之前一直刷的这种题会出现在算法书上
我是先找出可能得到的素数然后进行枚举的
代码如下:
#include<cstdio>
#include<cstring>
#include<algorithm>
const int prime[11] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
const int maxn = 17;
bool vis[maxn];
int ans[maxn];void print_ans(int n, int cur){if(cur == n){int tmp = ans[n] + ans[n - 1];for(int i = 0; i < 11; i++)if(prime[i] == tmp){for(int i = 0; i < n; i++){if(i) putchar(' ');printf("%d", ans[i]);}putchar('\n');break;}}else{for(int i = 0; i < 11; i++){if(prime[i] - ans[cur - 1] > n) break;if(prime[i] > ans[cur - 1] && !vis[prime[i] - ans[cur - 1]]){int idx = prime[i] - ans[cur - 1];vis[idx] = true;ans[cur] = idx;print_ans(n, cur + 1);vis[idx] = false;}}}
}int main(void)
{int n, kase = 0;while(scanf("%d", &n) == 1){memset(vis, 0, sizeof(vis)); vis[1] = true;ans[0] = ans[n] = 1;if(kase) putchar('\n');printf("Case %d:\n", ++kase);print_ans(n, 1);}return 0;
}
这篇关于Prime Ring Problem(UVA 524)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!