求四階的素數(shù)幻方

《求四階的素數(shù)幻方》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、求四階的素數(shù)幻方。即在一個4X4的矩陣中，每一個格填入一個數(shù)字，使每一行、每一列和兩條對角線上的4個數(shù)字所組成的四位數(shù)，均為可逆素數(shù)?！　?問題分析與算法設(shè)計　　有了前面的基礎(chǔ)，本題應(yīng)當(dāng)說是不困難的?！　∽詈唵蔚乃惴ㄊ牵翰捎酶F舉法，設(shè)定4X4矩陣中每一個元素的值后，判斷每一行、每一列和兩條對角線上的4個數(shù)字組成的四位數(shù)是否都是可逆素數(shù)，若是則求出了滿足題意的一個解?！　∵@種算法在原理是對的，也一定可以求出滿足題意的全部解。但是，按照這一思路編出的程序效率很低，在微機(jī)上幾個小時也不會運(yùn)行結(jié)束。這一算法致命的缺陷是：要窮舉和判斷的情況過多?！　〕浞掷妙}目中的“每一個四位數(shù)都是可逆素數(shù)”

2、這一條件，可以放棄對矩陣中每個元素進(jìn)行的窮舉的算法，先求出全部的四位可逆素數(shù)(204個)，以矩陣的行為單位，在四位可逆素數(shù)的范圍內(nèi)進(jìn)行窮舉，然后將窮舉的四位整數(shù)分解為數(shù)字后，再進(jìn)行列和對角線方向的條件判斷，改進(jìn)的算法與最初的算法相比，大大地減少了窮舉的次數(shù)?！　】紤]矩陣的第一行和最后一行數(shù)字，它們分別是列方向四位數(shù)的第一個數(shù)字和最后一個數(shù)字，由于這些四位數(shù)也必須是可逆素數(shù)，所以矩陣的每一行和最后一行中的各個數(shù)字都不能為偶數(shù)或5。這樣窮舉矩陣的第一行和最后一行時，它們的取值范圍是：所有位的數(shù)字均不是偶數(shù)或5的四位可逆數(shù)。由于符合這一條件的四位可逆素數(shù)很少，所以這一范圍限制又一次減少了窮

3、舉的次數(shù)?！　λ惴ǖ倪M(jìn)一步研究會發(fā)現(xiàn)：當(dāng)設(shè)定了第一和第二行的值后，就已經(jīng)可以判斷出當(dāng)前的這種組合是否一定是錯誤的(尚不能肯定該組合一定是正確的)。若按列方向上的四個兩位數(shù)與四位可逆數(shù)的前兩位矛盾(不是其中的一種組合)，則第一、二行的取值一定是錯誤的。同理在設(shè)定了前三行數(shù)據(jù)后，可以立刻判斷出當(dāng)前的這種組合是否一定是錯誤的，若判斷出矛盾情況，則可以立刻設(shè)置新的一組數(shù)據(jù)。這樣就可以避免將四個數(shù)據(jù)全部設(shè)定好以后再進(jìn)行判斷所造成的低效?！　「鶕?jù)以上分析，可以用偽語言描述以上改進(jìn)的算法：　　開始　　找出全部四位的可逆素數(shù);　　確定全部出現(xiàn)在第一和最后一行的四位可逆素數(shù);　　在指定范圍內(nèi)窮舉第一

4、行　　在指定范圍內(nèi)窮舉第二行　　若第一、第二、三行已出現(xiàn)矛盾，則繼續(xù)窮舉下一個數(shù);　　在指定范圍內(nèi)窮舉第四行　　判斷列和對角方向是否符合題意　　若符合題意，則輸出矩陣;　　否則繼續(xù)窮舉下一個數(shù);　　結(jié)束　　在實際編程中，采用了很多程序設(shè)計技巧，假如設(shè)置若干輔助數(shù)組，其目的就是要最大限度的提高程序的執(zhí)行效率，縮短運(yùn)行時間。下面的程序運(yùn)行效率是比較高的?！　?程序說明與注釋　#include?　　#include?　　int?number[210][5];?/*存放可逆素數(shù)及素數(shù)分解后的各位數(shù)字*/?　　int?select[110];?/*可以放在矩陣第一行和最后一行的素數(shù)的下標(biāo)*/?

5、　　int?array[4][5];?/*4X4的矩陣，每行0號元素存可逆素數(shù)對應(yīng)的數(shù)組下標(biāo)*/?　　int?count;?/*可逆素數(shù)的數(shù)目*/?　　int?selecount;?/*可以放在矩陣第一行和最后一行的可逆素數(shù)的數(shù)目*/?　　int?larray[2][200];?/*存放素數(shù)前二、三位數(shù)的臨時數(shù)組所對應(yīng)的數(shù)量計數(shù)器*/?　　int?lcount[2];?　　int?num(int?number);?　　int?ok(int?number);?　　void?process(int?i);?　　void?copy_num(int?i);?　　int?comp_num(in

6、t?n);?　　int?find1(int?i);?　　int?find2(void);?　　int?find0(int?num);?　　void?p_array(void);?　　int?main()?　　{?　　int?i,k,flag,cc=0,i1,i4;?　　printf("there?are?magic?squares?with?invertable?primes?as?follw:");?　　for(i=1001;i<9999;i+=2)?/*求滿足條件的可逆素數(shù)*/?　　{?　　k=i/1000;?　　if(k%2!=0&&k!=5&&num(i))?/*若可逆素

7、數(shù)的第一位不是偶數(shù)或5*/?　　{?　　number[count][0]=i;?/*存入數(shù)組*/?　　process(count++);?/*分解素數(shù)的各位數(shù)字*/?　　if(number[count-1][2]%2!=0&&?/*若可逆素數(shù)滿足放在矩陣第一行*/?　　number[count-1][3]%2!=0&&?/*和最后一行的條件，記錄可逆素數(shù)的*/?　　number[count-1][2]!=5&&?/*下標(biāo)，計數(shù)器加1*/?　　number[