基本介紹
- 中文名：素數環
- 問題描述：將從1到n這n個整數圍成
- C頭檔案：#include <stdio.h>
- C++頭檔案：#include<iostream>
定義,
定義
n=20時，下面的序列就是一個素數環：
1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 20 11 12 19 18
英文名：Prime Ring Problem
//遞歸實現（C語言)#include <stdio.h>#include <math.h>#define LEN 20int primeRing(int ring[], int b[], int n);int isPrime(int n);int main(void){ int i, ring[LEN]= {0}, b[LEN]= {0}; ring[0] = 1; b[0] = 1; if( primeRing(ring, b, 1) ) { printf("\n\nThe prime ring is : "); for(i=0; i<LEN; i++) printf("%d ", ring[i]); printf("\n"); } else printf("\n\nNot found!\n"); return 0;}int primeRing(int ring[], int b[], int n){ int i; if( n==LEN ) return isPrime(ring[n-1]+ring[0]); printf("\nCalculating ring[%d] = ", n); for(i=1; i<LEN; i++) if( b[i]==0 && isPrime((i+1)+ring[n-1]) ) { b[i] = 1; ring[n] = i+1; printf("%d ", ring[n]); if( primeRing(ring, b, n+1) ) return 1; else b[i] = 0; } return 0;}int isPrime(int n){ int i, t, f=1; t = sqrt(n); for(i=2; i<=t; i++) if( n%i==0 ) { f = 0; break; } return f;}//遞歸實現（c++）#include<iostream>#include<cstring>using namespace std;int step[21];int flag[21];int a[42];int n;bool check(int x,int y){ if(a[x+y]&&!flag[y]) return true; else return false;}void dfs(int dp){ int i; if(dp==n) { if(a[1+step[n-1]]) { printf("1"); for(i=1; i<n; i++) printf(" %d",step[i]); printf("\n"); } return; } for(i=2; i<=n; i++) { if(check(step[dp-1],i)) { step[dp]=i; flag[i]=1; dfs(dp+1); flag[i]=0; } }}int main(){ int count=1; memset(a,0,sizeof(a)); a[2]=a[3]=a[5]=a[7]=a[11]=a[13]=a[17]=1; a[19]=a[23]=a[29]=a[31]=a[37]=a[41]=1; while(~scanf("%d",&n)) { printf("Case %d:\n",count++); memset(flag,0,sizeof(flag)); step[0]=1; flag[1]=1; dfs(1); printf("\n"); } return 0;}//遞歸實現（Pascal）const max=20;type sz=array[1..max] of integer;var z:integer;a:sz;res:text;Procedure print;var i:integer;BEGINfor i: =1 to max do write(a[i]:5);writeln;END;function su(x:integer):boolean;var t:integer;beginsu: =true;for t: =2 to trunc(sqrt(x)) do if x mod t=0 then su: =false;end;function buchongfu(n,x:integer):boolean;var t:integer;beginbuchongfu: =true;for t: =1 to n do if a[t]=x then begin buchongfu: =false;break;end;end;procedure find(z:longint);var t:integer;beginif z<=max-1 thenbeginfor t: =1 to max do if su(t+a[z]) thenbeginif buchongfu(z,t) then begin a[z+1]: =t;find(z+1);end;end;endelse if su(a[max]+1) then print;end;beginassign(res,'result.txt');rewrite(res);a[1]: =1;find(1);close(res);writeln('Check result.txt');end.//非遞歸實現（Java）public class Main{ public static void main(String[] args) { primering(20); } public static void primering(int n) { if(n % 2 != 0) { System.out.println("若要實現素數環，元素的個數必須為偶數，您的輸入不符合要求！"); return; } int[] a = new int[n]; a[0] = 1; int i = 1; boolean flag = true; // true表示正常向下一級移動，false表示回溯到上一級 int first; while (i < n) {//選擇一個元素//如果是正常向下一級移動，該元素應該是當前未使用的最小的數//若是從下一層回溯上來的，則該元素為“比當前值大的，並且未被使用的，最小的一個數”for1: for (a[i] = flag ? 2 : a[i] + 1; a[i] <= n; a[i]++) {for (int j = 0; j < i; j++) //檢驗選擇的元素是否曾經用過{ if (a[i] == a[j]) continue for1;}break; }//若選擇的元素超過了最大值，則應該回溯 if (a[i] > n) {i--;flag = false;continue; }// 如果當前找到的元素與前一個元素的和是素數 if (isPrime(a[i] + a[i - 1])) {if (i < n - 1) // 如果不是最後一個元素，則向下一級尋找{ i++; flag = true;}else if (isPrime(a[i] + a[0])) // 如果是最後一個元素並且於環的第一個元素的和仍然是素數{ break; //則素數環已經找到，退出循環}else //若是最後一個元素，並且不滿足素數環{ i--; //則向上一級回溯 flag = false;} } else //若當前元素不滿足素數環，則繼續尋找 {flag = false; } }//列印素數環 for(int x:a) { System.out.print(x+" "); } } public static boolean isPrime(int n) { int i; for (i = 2; i < n; i++) if (n % i == 0)break; return i==n; }}運行結果：
C:\test>java Main
1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 20 11 12 19 18
回溯實現（C++）
#include<iostream>#include<algorithm>#include<string.h>using namespace std;int a[45]={0},b[21]={0},v[21]={0},n;void init()//篩選出素數 { int i,j; for(i=2; i<45; i++) a[i] = i; for (i=2; i*i<45; i++) { if (a[i] != 0) for (j=i*2; j<45; j+=i) { a[j] = 0; } }}void dfs(int x){ int i,j; if (x > 0 && b[0]!=1) //必須1開頭 { return ; } for (j=2; j<=x; j++) { if (!a[b[j-2]+b[j-1]]) //兩素數之和不是素數之間返回 { return ; } } if (x == n)//剛好n個數 ,是一種解 { if (a[b[0] + b[x-1]]) //頭和尾也必須是素數 { for (j=0; j<n; j++) { cout<<b[j]<<" "; } cout<<endl; return ; } } for (i=1; i<=n; i++) { if (!v[i]) { b[x] = i; v[i] = 1; dfs(x+1); //列舉第二個數 v[i] = 0; } }} int main(){ init(); int i,j,ca=1,T=0; while (cin>>n) { if (n==0) break; T++; cout<<"Case "<<T<<":"<<endl; memset(v,0,sizeof(v)); if (n==1) { cout<<1<<endl; } else if (n%2==0) { dfs(0); } else { cout<<"No Answer"<<endl; } } return 0; } 回溯實現（php）
/** * 定義素數環的長度 */define("LEN", 100);class PrimesRing { /** * $ring_data array 素數環的結果 * $initial_data array 排序的原始數據 1~n */ public $ring_data; public $initial_data; public $error_msg; public function __construct() { $this->ring_data = array_fill(0, LEN, 0); /** * 設定素數環的第一位，默認為1； */ $this->ring_data[0] = 1; $this->initial_data = range(1, LEN); $this->index(); } public function index() { if(!$this->primeRing($this->initial_data, 1) ) { $this->error_msg = "1 ~ " . LEN . " 不存在素數環！"; } } /** * 執行核心代碼， 計算得出素數環的順序 * $initial_data array 排序的原始數據 * $number int 計算到第幾位素數 */ public function primeRing($initial_data, $number = 1) { if(!is_numeric($number) || $number < 1) return false; if($number == LEN) return $this->isPrimes($this->ring_data[($number - 1)], $this->ring_data[0]); for($i = 1; $i < LEN; $i++) { if(isset($initial_data[$i]) && $this->isPrimes( $initial_data[$i], $this->ring_data[($number - 1)]) ) { $this->ring_data[$number] = $initial_data[$i]; unset($initial_data[$i]); if($this->primeRing($initial_data, ($number + 1))) { return true; } else { //如果下一個不行， 就回溯到本次 $initial_data[$i] = $this->ring_data[$number]; } } } return false; } /** * 判斷兩數之和是否為素數 * $num1 int * $num2 int */ public function isPrimes($num1, $num2) { if($num1 <= 0 || $num2 <= 0) return false; if(!is_int($num1) || !is_int($num2)) return false; $sum_num = $num1 + $num2; $sqrt_num = sqrt($sum_num); $flag_status = true; for($i = 2; $i <= $sqrt_num; $i++) { $flag_status = ($sum_num % $i == 0) ? false : true; if(!$flag_status) break; } return $flag_status; }}