UVA 524 素数环Prime Ring Problem (回溯法)

太过爱你忘了你带给我的痛 2024-02-17 19:03 130阅读 0赞

啃爹的输出格式！PE了好几次！

#include<cstdio>
    #include<cstring>
    #include<cmath>
    using namespace std;
    const int maxn=16;
    int vis[maxn],A[maxn]; 
    int n;
    bool isp(int temp){                //判断是否为素数，是则返回true; 
    	int flag=1;
    	for(int i=2;i<=sqrt(temp);i++){
    		if(temp%i==0){
    			flag=0;break;
    		}
    	}
    	if(flag)return true;
    	else return false;
    }
    
    void dfs(int cur){
    	if(cur==n && isp(A[0]+A[n-1])){    
    		printf("%d",A[0]);
    		for(int i=1;i<n;i++)printf(" %d",A[i]);
    		printf("\n");
    	}
    	else for(int i=2;i<=n;i++){   //尝试放置每个数i; 
    		if(!vis[i] && isp(A[cur-1]+i)){ //如果i没有被使用过，并且与前一个数之和为素数 
    			A[cur]=i;
    			vis[i]=1;             //使用标志 
    			dfs(cur+1);
    			vis[i]=0;           //一定要改回 
    		}
    	}
    }
    int main(){
    	int count=0;
    	while(scanf("%d",&n)==1){
    		memset(vis,0,sizeof(vis));
    		A[0]=1;
    		if(count++)printf("\n");
    		printf("Case %d:\n",count);
    		dfs(1);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，130人围观）

还没有评论，来说两句吧...

相关阅读

相关 UVA 524 素数环Prime Ring Problem (回溯法)

啃爹的输出格式！PE了好几次！ include<cstdio> include<cstring> include<cmath> using n

太过爱你忘了你带给我的痛/ 2024年02月17日 19:03/ 0 赞/ 131 阅读

相关 hdoj 1016 Prime Ring Problem【素数环】

Prime Ring Problem Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/3276

痛定思痛。/ 2022年08月08日 15:58/ 0 赞/ 259 阅读

相关 UVA - 524 Prime Ring Problem

Description A ring is composed of n (even number) circles as shown in diagram. Put natu

朱雀/ 2022年07月10日 11:28/ 0 赞/ 234 阅读

相关 ACM dfs回溯法 Prime Ring Problem

滴，集训第二天打卡。今天是紫书第七章训练+约瑟夫问题。约瑟夫问题就是一个公式可以解决的事情~~ 基本套路就是： include <stdio.h>

不念不忘少年蓝@/ 2022年06月12日 07:07/ 0 赞/ 264 阅读

相关 Prime Ring Problem

A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into

女爷i/ 2022年06月12日 02:27/ 0 赞/ 321 阅读

相关 hdu 1016 Prime Ring Problem

Prime Ring Problem Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K

本是古典何须时尚/ 2022年06月12日 02:08/ 0 赞/ 270 阅读

相关 Prime Ring Problem （素数环）深度优先搜索

题目链接：https://vjudge.net/contest/176287\problem/G 代码： ![Center][] ![Center 1][]

墨蓝/ 2022年06月10日 04:44/ 0 赞/ 303 阅读

相关 HDU 1016 Prime Ring Problem

Problem Description A ring is compose of n circles as shown in diagram. Put natural num

港控/mmm°/ 2022年05月29日 13:54/ 0 赞/ 269 阅读

相关 Prime Ring Problem

Prime Ring Problem A ring is compose of n circles as shown in diagram. Put natural nu

小灰灰/ 2022年05月16日 09:06/ 0 赞/ 276 阅读

相关洛谷题解UVA524 素数环

一、题目 [https://www.luogu.org/problemnew/show/UVA524][https_www.luogu.org_problemnew_sh

淡淡的烟草味﹌/ 2022年02月27日 13:26/ 0 赞/ 367 阅读