在說起全排列前，先說一下昨天碰到的一個題目（答案不是我做出來的，但是我感覺有好多個亮點，貼出來方便日后的學習）：

?

素數環

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

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

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

輸入

有多組測試數據，每組輸入一個n(0<n<20)，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








這個題的解法我考慮了很久，怎么說呢，感覺上并不是一道難度很大的題，實際操作起來卻又無從下手。我說一下我的思考過程
首先，這牽扯到尋找素數，但是呢，不是簡單的找素數，而是兩個數的和，在[1,n]之間的兩個數m，n的和

　　　　　　　　有多組測試數據，每組輸入一個n(0<n<20)，n=0表示輸入結束。

這句話可以看出輸入的n，最大，也就20.那么，即使在跑程序的時候，當真輸入為20，最大的的一個和值也就是20+20=40,那么，我完全可以把[1,40]間的素數全部找出來并建立一個數
組s[40]，然后在[1,n]間查看，看哪兩個數的和是素數，通過在數組s[40]里查找是否符合，若符合，將符合的值存放在一個數組里，而后輸出。 #include <stdio.h> #include<string.h> int count,sa[40]; // coount 用于控制輸出流 sa[]是一個用來顯示區間[2,42]內每個數是否為素數的數組，若為素數，其對應的sa[j]=1/*** found 函數的定義，據作者說是由全排列改編過來的 ***/ void found(int n,int cur,int a[],int flag[]){ // 傳入的 n 為 in[]數組中的元素，即輸入值； cur 初始值為1 是用于控制a[]的下標 ； a[]是一個a[0]=1的用于存放可滿足數的數組； // flag[]是一個初始值全部置0的數組 ， 用于儲存在判定檢查過程中的數是否為要用的值后的布爾值if(cur==n&&sa[a[0]+a[cur-1]]) // 這里用cur 與 輸入值 n 進行比較判斷 也就是說 a數組里存放的個數最多 n個，最多把[1,n]之間的值全部放進去,或者說數組a里的最大值肯定不能大于n { { for(int i=0;i<n;i++) printf("%d ",a[i]); // 那么，當a數組檢查n是否可以存放時，這次遍歷也就到此結束了，也就是該輸出數組a了putchar('\n'); count=0; } } /***** 在cur!=n時，需要進一步的檢查時，利用遞歸，在區間[2,n]，以此將滿足的數存放在a[]中 *****/else // for(int i=2;i<=n;i++) // if(!flag[i]&&sa[i+a[cur-1]]) // { // a[cur]=i; // flag[i]=1; // found(n,cur+1,a,flag); // flag[i]=0; // } // } // /*********************************************************************************/ int main(void) {int i=0,a[20],in[100],flag[20]; // in[20] 用于存放輸入 memset(sa,0,sizeof(sa)); memset(flag,0,sizeof(flag)); /***********************************************************/ for(int ok=1,k=2,j=2;j<40;j++,ok=1) // { // for(int i=2;i<=j/2;i++) // 在區間[2,40]里進行是否為素數的判定 用j控制數組sa的下標，同時，j還是一個數列【2，,40】 { // if(j%i==0) ok=0; // 若為素數，sa[j]=1,否則不對sa[j]處理，即為0 } // if(ok) sa[j]=1; // } // /**************************************************/ /**************************************/do // 我很喜歡這段控制輸入的代碼{ // scanf("%d",&in[i++]); // 很簡單 但是很巧妙 }while(in[i-1]); // /********************************/// 大方 優雅 a[0]=1; for(int j=1;j<i;j++) {count=1; printf("Case %d:\n",j); // j 顯示輸入的數據的個數 if(!(in[j-1]%2)||in[j-1]==1) found(in[j-1],1,a,flag); // if里判定 in[]數組里的元素是否為奇數 或者是為1 兩種情況均調用函數 if(count) printf("No Answer\n"); } return 0; }

?

?

?先簡單簡單注釋一下，可能在匆忙之中有一些錯誤，哪位有發現，多謝指出

?

轉載于:https://www.cnblogs.com/zhangzimu/p/6187187.html

總結

以上是生活随笔為你收集整理的素数环 与 算法 全排列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。