C趣味編程百例(10)

2019-11-17 05:40:33

字體：大中小

來源：轉載

供稿：網友

35.素數幻方
    求四階的素數幻方。即在一個4X4 的矩陣中，每一個格填入一個數字，使每一行、每一列和兩條對角線上的4 個數字所組成的四位數，均為可逆素數。
*問題分析與算法設計
    有了前面的基礎，本題應當說是不困難的。
    最簡單的算法是：采用窮舉法，設定4X4矩陣中每一個元素的值后，判定每一行、每一列和兩條對角線上的4個數字組成的四位數是否都是可逆素數，若是則求出了滿足題意的一個解。
    這種算法在原理是對的，也一定可以求出滿足題意的全部解。但是，按照這一思路編出的程序效率很低，在微機上幾個小時也不會運行結束。這一算法致命的缺陷是：要窮舉和判定的情況過多。
    充分利用題目中的“每一個四位數都是可逆素數”這一條件，可以放棄對矩陣中每個元素進行的窮舉的算法，先求出全部的四位可逆素數(204個)，以矩陣的行為單位，在四位可逆素數的范圍內進行窮舉，然后將窮舉的四位整數分解為數字后，再進行列和對角線方向的條件判定，改進的算法與最初的算法相比，大大地減少了窮舉的次數。
    考慮矩陣的第一行和最后一行數字，它們分別是列方向四位數的第一個數字和最后一個數字，由于這些四位數也必須是可逆素數，所以矩陣的每一行和最后一行中的各個數字都不能為偶數或5。這樣窮舉矩陣的第一行和最后一行時，它們的取值范圍是：所有位的數字均不是偶數或5的四位可逆數。由于符合這一條件的四位可逆素數很少，所以這一范圍限制又一次減少了窮舉的次數。
    對算法的進一步研究會發現：當設定了第一和第二行的值后，就已經可以判定出當前的這種組合是否一定是錯誤的(尚不能肯定該組合一定是正確的)。若按列方向上的四個兩位數與四位可逆數的前兩位矛盾(不是其中的一種組合)，則第一、二行的取值一定是錯誤的。同理在設定了前三行數據后，可以馬上判定出當前的這種組合是否一定是錯誤的，若判定出矛盾情況，則可以馬上設置新的一組數據。這樣就可以避免將四個數據全部設定好以后再進行判定所造成的低效。
    根據以上分析，可以用偽語言描述以上改進的算法：
        開始
            找出全部四位的可逆素數；
            確定全部出現在第一和最后一行的四位可逆素數；
            在指定范圍內窮舉第一行
                在指定范圍內窮舉第二行
                    若第一、第二、三行已出現矛盾，則繼續窮舉下一個數；
                    在指定范圍內窮舉第四行
                        判定列和對角方向是否符合題意
                            若符合題意，則輸出矩陣；
                        否則繼續窮舉下一個數；
        結束
    在實際編程中，采用了很多程序設計技巧，假如設置若干輔助數組，其目的就是要最大限度的提高程序的執行效率，縮短運行時間。下面的程序運行效率是比較高的。
*程序與程序注釋
#include<stdio.h>
#include<math.h>
int number[210][5];     /*存放可逆素數及素數分解后的各位數字*/
int select[110];        /*可以放在矩陣第一行和最后一行的素數的下標*/
int array[4][5];        /*4X4的矩陣，每行0號元素存可逆素數對應的數組下標*/
int count;              /*可逆素數的數目*/
int selecount;          /*可以放在矩陣第一行和最后一行的可逆素數的數目*/
int larray[2][200];     /*存放素數前二、三位數的臨時數組所對應的數量計數器*/
int lcount[2];
int num(int number);
int ok(int number);
void PRocess(int i);
void copy_num(int i);
int comp_num(int n);
int find1(int i);
int find2(void);
int find0(int num);
void p_array(void);

void main()
{
    int i,k,flag,cc=0,i1,i4;
    printf("there are magic squares with invertable primes as follw:/n");
    for(i=1001;i<9999;i+=2)                 /*求滿足條件的可逆素數*/
    {
        k=i/1000;
        if(k%2!=0&&k!=5&&num(i))     /*若可逆素數的第一位不是偶數或5*/
        {
            number[count][0]=i;      /*存入數組*/
            process(count++);        /*分解素數的各位數字*/
            if(number[count-1][2]%2!=0&&   /*若可逆素數滿足放在矩陣第一行*/
               number[count-1][3]%2!=0&&   /*和最后一行的條件，記錄可逆素數的*/
               number[count-1][2]!=5&&     /*下標，計數器加1*/
               number[count-1][3]!=5)
                select[selecount++]=count-1;
        }
    }
    larray[0][lcount[0]++]=number[0][0]/100;     /*臨時數組的第一行存前二位*/
    larray[1][lcount[1]++]=number[0][0]/10;      /*臨時數組的第二行存前三位*/
    for(i=1;i<count;i++)                /*將素數不重復的前二、三位存入臨時數組中*/
    {
        if(larray[0][lcount[0]-1]!=number[i][0]/100)
            larray[0][lcount[0]++]=number[i][0]/100;
        if(larray[1][lcount[1]-1]!=number[i][0]/10)
            larray[1][lcount[1]++]=number[i][0]/10;
    }
    for(i1=0;i1<selecount;i1++)                    /*在第一行答應的匯聚圍內窮舉*/
    {
        array[0][0]=select[i1];                    /*取對應的素數下標*/
        copy_num(0);                               /*復制分解的素數*/
        for(array[1][0]=0;array[1][0]<count;array[1][0]++)    /*窮舉第二行*/
        {
            copy_num(1);                /*復制分

上一篇：C趣味編程百例(06)

下一篇：C趣味編程百例(32)