程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> nyoj 488 素數環(深搜)

nyoj 488 素數環(深搜)

編輯:C++入門知識

nyoj 488 素數環(深搜)


素數環

時間限制:1000 ms | 內存限制:65535 KB 難度:2
描述

有一個整數n,把從1到n的數字無重復的排列成環,且使每相鄰兩個數(包括首尾)的和都為素數,稱為素數環。

為了簡便起見,我們規定每個素數環都從1開始。例如,下圖就是6的一個素數環。

\

輸入
有多組測試數據,每組輸入一個n(0 輸出
每組第一行輸出對應的Case序號,從1開始。
如果存在滿足題意敘述的素數環,從小到大輸出。
否則輸出No Answer。
樣例輸入
6
8
3
0
樣例輸出
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
Case 3:
No Answer
來源
hdu改編
上傳者

ACM_丁國強

考察的是深搜;

深搜模板:

//深搜模板:(自己總結的,有不對的地方,還請各位路過的大牛,不吝指教!) 
int n;//首先申請一個全局變量 
int visit[10010];//標記 元素 
int a[10010];//存放元素 
void dfs(int cur)
{
	//此處是遞歸跳出條件 
	if(cur==n)//此處的判斷條件看數組下標是否 是從1 開始的
	{
		if(   )//題目中限定的一定條件。
		{
			printf("  ");//輸出相應的要求解的值 
		}
	}
	for(i=2;i<=n;++i)
	{
		if(  )//又是與題中的限定條件有關,到那時多了一個判斷是否已經標記過
		{
			visit[i]=1;
			a[k]=i;//將此時境況下滿足條件的數據存入數組 
			dfs(k+1); //對後面的元素進行遞歸 
			visit[i]=0;//這兩步與輸出多組數據有關,遞歸跳出的時候,在多組跳出的時候
			           //為了後續滿足題意的數據的輸出,需要返回出師狀態 
		} 
	} 
} 

代碼如下:

#include
#include
int n;
int visit[110];
int ring[110]={1};
int prime(int x)//判斷是否是素數 
{
	for(int i=2;i*i<=x;++i)
	{
		if(x%i==0)
		return 0;
	}
	return 1;
}
void dfs(int k)//深搜 
{
	int i;
	if(k==n-1)//循環跳出的條件 
	{
		if(prime(1+ring[k]))//滿足和為素數 
		{
			printf("1");
			for(i=1;i


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved