注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Minary_Acdream

http://f10.moe/

 
 
 

日志

 
 

[hdu]1016 Prime Ring Problem  

2012-08-13 12:50:13|  分类: HDU |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

DFS水过。题目要求是相邻的数之和为质数,由于这里仅仅只有20组数据,所以素数存储我们可以用数组 prime[38] = {0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1}; 

Prime Ring Problem

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 13974    Accepted Submission(s): 6346


Problem Description
A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

Note: the number of first circle should always be 1.

[hdu]1016 Prime Ring Problem - Minary - Minary_Acdream
 

Input
n (0 < n < 20).
 

Output
The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.

You are to write a program that completes above process.

Print a blank line after each case.
 

Sample Input
8
 

Sample Output
Case 1: 
1 4 3 2 5 6 
1 6 5 2 3 4  

Case 2: 
1 2 3 8 5 6 7 4 
1 2 5 8 3 4 7 6 
1 4 7 6 5 8 3 2 
1 6 7 4 3 8 5 2
 

Source
 

Recommend
JGShining
 

代码如下:


#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<cmath>
using namespace std;
int prime[38] = {0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1};
int n,b[25],prii[60]; //数组prii用来存储数字。
void dfs(int a)
{
if(a == n && prime[1 + prii[n]]) //判断最后一个与第一个之和是不是为素数
{
printf("%d",prii[1]);
for(int i = 2;i <= n;i ++) printf(" %d",prii[i]);
printf("\n");
}
for(int i = 2;i <= n;i ++)
{
if(b[i] != 0 && prime[prii[a] + i])
{
prii[a + 1] = i;
b[i] = 0;
dfs(a + 1);
b[i] = i;
}
}
}

int main()
{
int t = 0;
for(int i = 0;i < 25;i ++) b[i] = i;
prii[1] = 1;
while(cin>>n)
{
t ++;
printf("Case %d:\n",t);
dfs(1);
printf("\n");
}
return 0;
}

/*
Sample Input
6
8


Sample Output
Case 1:
1 4 3 2 5 6
1 6 5 2 3 4

Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2*/



  评论这张
 
阅读(188)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018