版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)
文檔簡介
1、 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 文章編輯一、需求分析1.問題回顧題目名稱:n階魔方(3n15)題目描述:n階魔方,又叫幻方陣,在我國古代稱為“縱橫圖”,是一個比較有趣的游戲。所謂n階魔方就是一個填數(shù)游戲。要求用1到n2的數(shù)字(3n15)不重復(fù)地填入方針中,使得每一行、每一列、每條對角線上的數(shù)字累家和都相等。例如,圖1-1所示就是一個3階魔幻方陣。它是用數(shù)字1到9不重復(fù)地填入33方針中,使得方陣的每一行、每一列、每條對角線上的數(shù)字累加和都等于15。618753294 圖1-1功能要求:1)、輸入一個數(shù)字n(3n15),則輸出對應(yīng)的n階魔幻方陣,并輸出每一行、每一列、每條對角線上的數(shù)字累家和;2)、若輸出數(shù)字
2、n超出要求范圍,則提醒用戶重新輸入n;3)、但輸入數(shù)字為0時,操作結(jié)束,退出程序。使用多維數(shù)組輸出魔幻方陣,分別用4個子函數(shù)實現(xiàn)相應(yīng)的功能;輸入形式:數(shù)字n(3n15)輸出形式:(1)以矩陣的形式輸出n(3n15)階魔幻方陣; (2)輸出魔幻方陣每一行、每一列、每條對角線上數(shù)字累加和;(3)輸出程序運行時間復(fù)雜度。2.問題及算法分析:1)當(dāng)n為奇數(shù)時,n階魔幻方陣有多種實現(xiàn)方法,其中之一就是“左上斜行法”。該方法的基本思想如下。a)在1到n2的數(shù)字中,選擇1開始填充魔方,將數(shù)字1填入第1行的中間方格中,即(0,n/2)位置。b)向已填充的前一個數(shù)字位置(p,q)的左上角(p-1,q-1)填入下
3、一個數(shù)字。如果出現(xiàn)以下情況,則修改填充位置:)若填充位置超出上邊界,則修改為下邊界的相應(yīng)位置,即把p-1修改為n-1;)若填充位置超出左邊界,則修改為最右邊的相應(yīng)位置,即把q-1修改為n-1;)若該位置已有數(shù)字,則填充位置修改為下一行,同一位置。c)重復(fù)以上過程,直至將n2個數(shù)字全部填入魔方中。2)當(dāng)n為雙偶數(shù)時,魔幻方陣的實現(xiàn)方法如下。a)把1到n2依次填入nn的n階方陣中;b)方陣行數(shù)與列數(shù)之和除4取余為3或者行數(shù)除4的余數(shù)等于列數(shù)除4的余數(shù),則此位置上數(shù)不變,c)將其余數(shù)apq 與an-1-pn-1-q位置對調(diào)即可得到雙偶數(shù)n階魔幻方陣。3)當(dāng)n為單偶數(shù)時,魔幻方陣的實現(xiàn)方法如下。a)將
4、n階單偶幻方表示為4m+2階幻方。將其等分為四分,成為如下圖所示a、b、c、d四個2m+1階奇數(shù)幻方。 a c d b b)用1至(2m+1)*(2m+1)填寫成(2m+1)階幻方;b用(2m+1) *(2m+1)+1至2*(2m+1) *(2m+1)填寫成2m+1階幻方;c用2*(2m+1) *(2m+1) +1至3*(2m+1) *(2m+1)填寫成2m+1階幻方;d用3*(2m+1) *(2m+1)+1至4*(2m+1) *(2m+1)填寫成2m+1階幻方;c)在中間一行取m個小格,其中1格為該行居中1小格,另外m-1個小格任意,其他行左側(cè)邊緣取m列,將其與d相應(yīng)方格內(nèi)交換;與接近右側(cè)m
5、-1列相互交換,即的n階魔幻方陣。二、總體設(shè)計本次程序設(shè)計主要采用了c語言的結(jié)構(gòu)化程序設(shè)計思想,采用過程設(shè)計方法,以功能函數(shù)為基本結(jié)構(gòu)單位,對問題中的功能要求做出了準(zhǔn)確的實現(xiàn)。1、在數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)存儲表示方面,使用二維數(shù)組ann來靜態(tài)存儲不超過n行n列的數(shù)組方陣,其中n(3n15)為滿足條件的數(shù)。2、在功能函數(shù)實現(xiàn)方面,主要使用與實現(xiàn)了如下函數(shù):1) void main()函數(shù),主函數(shù),調(diào)用以下子函數(shù),實現(xiàn)魔幻方陣填充與輸出,實現(xiàn)問題要求功能;2) #include函數(shù),程序運行時間復(fù)雜度函數(shù);3) void jishu(int n)函數(shù),n為奇數(shù)時實現(xiàn)n階魔幻方陣,并調(diào)用函數(shù)out(n,a)
6、和check(n,a),實現(xiàn)魔幻方陣的輸出,檢驗?zāi)Щ梅疥嚨臏?zhǔn)確性;4) void shuang(int n)函數(shù),n為雙偶數(shù)時實現(xiàn)n階魔幻方陣,并調(diào)用函數(shù)out(n,a) 和check(n,a),實現(xiàn)魔幻方陣的輸出,檢驗?zāi)Щ梅疥嚨臏?zhǔn)確性;5) void dan(int n)函數(shù),n為單偶數(shù)時實現(xiàn)n階魔幻方陣,并調(diào)用函數(shù)out(n,a) 和check(n,a),實現(xiàn)魔幻方陣的輸出,檢驗?zāi)Щ梅疥嚨臏?zhǔn)確性;6) void out(int n,int a1515)函數(shù),實現(xiàn)魔幻方陣的輸出;7) void check(int n,int a1515)函數(shù),驗證魔幻方陣的準(zhǔn)確性。三、各函數(shù)邏輯關(guān)系調(diào)用圖v
7、oid main()void jishu(int n)void shuang(int n)void shuang(int n)n為奇數(shù)n為雙偶數(shù)n為單偶數(shù)out(n,a)out(n,a)check(n,a)check(n,a)out(n,a)check(n,a)四、本程序執(zhí)行流程圖開始輸入nn在允許范圍內(nèi)?n調(diào)用void jishu(int n)y 調(diào)用void shuang(int n) 調(diào)用void shuang(int n)n為奇數(shù)n為雙偶數(shù)n為單偶數(shù)調(diào)用out(n,a)調(diào)用out(n,a)調(diào)用check(n,a)調(diào)用check(n,a)調(diào)用out(n,a)調(diào)用check(n,a)輸出n
8、魔幻方陣及其每一行、每一列、每條對角線上各數(shù)字累加和結(jié)束三、詳細(xì)設(shè)計1、基本功能函數(shù)具體實現(xiàn)細(xì)節(jié)及算法分析1). void jishu(int n)該函數(shù)實現(xiàn)“左上斜行法”。該方法的算法(基本思想)如下。a)在1到n2的數(shù)字中,選擇1開始填充魔方,將數(shù)字1填入第1行的中間方格中,即(0,n/2)位置。b)向已填充的前一個數(shù)字位置(p,q)的左上角(p-1,q-1)填入下一個數(shù)字。如果出現(xiàn)以下情況,則修改填充位置:)若填充位置超出上邊界,則修改為下邊界的相應(yīng)位置,即把p-1修改為n-1;)若填充位置超出左邊界,則修改為最右邊的相應(yīng)位置,即把q-1修改為n-1;)若該位置已有數(shù)字,則填充位置修改為
9、下一行,同一位置。c)重復(fù)以上過程,直至將n2個數(shù)字全部填入魔方中。2) . void shuang(int n)此函數(shù)主要采用了二維矩陣的算法將雙偶數(shù)魔幻方陣填入并輸出。其具體算法如下:當(dāng)n能被4整除時,n為雙偶數(shù),a)把1到n2依次填入nn的n階方陣中;b)方陣行數(shù)與列數(shù)之和除4取余為3或者行數(shù)除4的余數(shù)等于列數(shù)除4的余數(shù),則此位置上數(shù)不變,c)將其余數(shù)apq 與an-1-pn-1-q位置對調(diào)即可得到雙偶數(shù)n階魔幻方陣。3) . void dan(int n) 此函數(shù)依然采用了二維矩陣的算法將雙偶數(shù)魔幻方陣填入并輸出。其具體算法如下:當(dāng)n能被2整除但不能被4整除時,n為單偶數(shù),此時a)將n
10、階單偶幻方表示為4m+2階幻方。將其等分為四分,成為如下圖所示a、b、c、d四個2m+1階奇數(shù)幻方。 a c d b b)用1至(2m+1)*(2m+1)填寫成(2m+1)階幻方;b用(2m+1) *(2m+1)+1至2*(2m+1) *(2m+1)填寫成2m+1階幻方;c用2*(2m+1) *(2m+1) +1至3*(2m+1) *(2m+1)填寫成2m+1階幻方;d用3*(2m+1) *(2m+1)+1至4*(2m+1) *(2m+1)填寫成2m+1階幻方;c)在中間一行取m個小格,其中1格為該行居中1小格,另外m-1個小格任意,其他行左側(cè)邊緣取m列,將其與d相應(yīng)方格內(nèi)交換;與接近右側(cè)m-
11、1列相互交換,即的n階魔幻方陣。4) . out(n,a)此函數(shù)調(diào)整方陣元素位置,將魔幻方陣以nn形式輸出。5) . check(n,a)此函數(shù)計算并輸出n階魔幻方陣每一行、每一列、每條對角線上的數(shù)字累加和。 2.各函數(shù)具體實現(xiàn)代碼:1). void jishu(int n) 具體實現(xiàn)代碼void jishu(int n)int p,q,i,a1515;p=0;q=(n-1)/2;a0q=1; for(i=2;i0)p=(p+2)%n;q=(q+1)%n;apq=i;2). void shuang(int n) 具體實現(xiàn)代碼void shuang(int n)int a1515,i=1,p,q
12、;for(p=0;pn;p+)for(q=0;qn;q+)apq=i;i+;for(p=0;pn;p+)for(q=0;qn/2;q+)if(p+q)%4=3|p%4=q%4)/apq=apq;elsei=apq;apq=an-1-pn-1-q;an-1-pn-1-q=i;3) . void dan(int n) 具體實現(xiàn)代碼void dan(int n)int m=n/4,k=n/2,j=m-2;int a1515,p=0,q=(n/2-1)/2,i=1;q=(n/2-1)/2;a0q=1;for(i=2;i0)p=(p+2)%k;q=(q+1)%k;apq=i;for(p=k;pn;p+)
13、for(q=k;qn;q+)apq=ap-kq-k+n*n/4;for(p=0;pk;p+)for(q=k;qn;q+)apq=ap+kq+n*n/4;for(p=k;pn;p+)for(q=0;qk;q+)apq=ap-kq+k+n*n/4; i=amm;amm=am+km;am+km=i; for(q=0;qm;q+)for(p=0;pn-m;q-)for(p=0;p=0)for(q=0;q=j;q+)p=m;i=apq; apq=ap+kq; ap+kq=i;4) . out(n,a) 具體實現(xiàn)代碼void out(int n,int a1515)int p,q;for(p=0;p=n-
14、1;p+)for(q=0;q=n-1;q+)coutsetw(4)apq ;coutendlendl;5) . check(n,a) 具體實現(xiàn)代碼void check(int n,int a1515)int p,q,sum1=0,sum2=(n*n+1)*n/2,k;cout此幻方的每行、每列、兩條對角線的和應(yīng)為:sum2endl;for(p=0;pn;p+)for(q=0;qn;q+) sum1=apq+sum1;if(sum1!=sum2)cout橫行縱行計算結(jié)果與標(biāo)準(zhǔn)不符,請修改程序錯誤endl;break;sum1=0;for(k=0;kn;k+)sum1=akk+sum1;if(su
15、m1!=sum2)cout主對角線計算結(jié)果與標(biāo)準(zhǔn)不符,請修改程序錯誤endl;sum1=0;for(k=0;kn;k+)sum1=akn-k-1+sum1; if(sum1!=sum2)cout次對角線計算結(jié)果與標(biāo)準(zhǔn)不符,請修改程序錯誤endl;四程序清單#include#include #includevoid jishu(int n);void shuang(int n);void dan(int n);void out(int n,int a1515);void check(int n,int a1515);void main()clock_t start,end;int n;while
16、(n!=0) cout*endl; cout*本程序用于輸出3到15階幻方,即將1到n平方的數(shù)填入n乘n的方陣中*endl; cout* 使所有的橫行,縱行及兩對角線上所有數(shù)字之和相等。 *endl;cout* 當(dāng)輸入0時本程序結(jié)束 *endl; cout*endl; coutn; while(n15)if(n=0)break;/*n=0,本程序結(jié)束*/ coutn;if(n=0)break;/*n=0,本程序結(jié)束*/ cout所得的幻方為:endl;start=clock(); if(n%4=1|n%4=3)/*n為奇數(shù),調(diào)用奇數(shù)魔方函數(shù)jishu(n)*/ jishu(n); if(n%4
17、=0)/* n為雙偶數(shù),調(diào)用雙偶數(shù)魔方函數(shù)shuang(n)*/ shuang(n); if(n%4=2)/* n為單偶數(shù),調(diào)用單偶數(shù)魔方函數(shù)dan(n)*/ dan(n);end=clock();cout所花費的時間為end-start毫秒endl;cout謝謝您的使用endl;void jishu(int n)/*奇數(shù)*/int p,q,i,a1515;p=0;q=(n-1)/2;a0q=1; /*第一個數(shù)字的填入位置*/for(i=2;i0)/*如果填入位置上已有數(shù)字,則重新計算填入位置*/p=(p+2)%n;/*由于前面p減了1,因此p應(yīng)該加2,才能表示下一行*/q=(q+1)%n;/
18、*由于前面q減了1,因此q應(yīng)該加1,才能表示同一列*/apq=i;/*填入數(shù)字*/out(n,a);/*調(diào)用輸出函數(shù)*/check(n,a);/*調(diào)用驗證函數(shù)*/void shuang(int n)/*雙偶數(shù)*/ int a1515,i=1,p,q;for(p=0;pn;p+)/*將1到n*n依次填入n階矩陣*/for(q=0;qn;q+)apq=i;i+;for(p=0;pn;p+)for(q=0;qn/2;q+)if(p+q)%4=3|p%4=q%4)/*方陣行數(shù)與列數(shù)之和除4取余為3或者行數(shù)除4的余數(shù)等于列數(shù)除4的余數(shù),則此位置上數(shù)不變*/apq=apq;elsei=apq;/*對應(yīng)換位
19、*/apq=an-1-pn-1-q;an-1-pn-1-q=i;out(n,a);/*調(diào)用輸出函數(shù)*/check(n,a);/*調(diào)用驗證函數(shù)*/void dan(int n)/*單偶數(shù)*/int m=n/4,k=n/2,j=m-2;int a1515,p=0,q=(n/2-1)/2,i=1;q=(n/2-1)/2;a0q=1;for(i=2;i0)p=(p+2)%k;q=(q+1)%k;apq=i;for(p=k;pn;p+)for(q=k;qn;q+)apq=ap-kq-k+n*n/4;for(p=0;pk;p+)for(q=k;qn;q+)apq=ap+kq+n*n/4;for(p=k;p
20、n;p+)for(q=0;qk;q+)apq=ap-kq+k+n*n/4; i=amm;amm=am+km;am+km=i; for(q=0;qm;q+)for(p=0;pn-m;q-)for(p=0;p=0)for(q=0;q=j;q+)p=m;i=apq; apq=ap+kq; ap+kq=i;out(n,a);check(n,a);void out(int n,int a1515)/*輸出函數(shù)*/int p,q;for(p=0;p=n-1;p+)for(q=0;q=n-1;q+)coutsetw(4)apq ;coutendlendl;void check(int n,int a1515
21、)/*驗證函數(shù)*/int p,q,sum1=0,sum2=(n*n+1)*n/2,k;cout此幻方的每行、每列、兩條對角線的和應(yīng)為:sum2endl;for(p=0;pn;p+)for(q=0;qn;q+) sum1=apq+sum1;if(sum1!=sum2)cout橫行縱行計算結(jié)果與標(biāo)準(zhǔn)不符,請修改程序錯誤endl;break;sum1=0;for(k=0;kn;k+)sum1=akk+sum1;if(sum1!=sum2)cout主對角線計算結(jié)果與標(biāo)準(zhǔn)不符,請修改程序錯誤endl;sum1=0;for(k=0;kn;k+)sum1=akn-k-1+sum1; if(sum1!=sum
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 私立華聯(lián)學(xué)院《電腦效果圖制作》2023-2024學(xué)年第一學(xué)期期末試卷
- 墊付借款合同范例
- 板式櫥柜采購合同范例
- 農(nóng)村荒山合同范例
- 企業(yè)年金制度與實施方案研究
- 違約解除租賃合同范例
- 廣州廣東廣州科技貿(mào)易職業(yè)學(xué)院非事業(yè)編制專職督導(dǎo)招聘筆試歷年參考題庫頻考點試題附帶答案詳解
- 高校周邊餐飲市場的競爭格局研究
- 教學(xué)器材采購合同范例
- 汽車自駕租賃合同范例
- 2023-2024學(xué)年滬教版(上海)七年級數(shù)學(xué)上冊 期末復(fù)習(xí)題
- 2024-2025學(xué)年高二上學(xué)期期末復(fù)習(xí)【第五章 一元函數(shù)的導(dǎo)數(shù)及其應(yīng)用】十一大題型歸納(拔尖篇)(含答案)
- 湖北省咸寧市通城縣2022-2023學(xué)年八年級上學(xué)期期末質(zhì)量檢測數(shù)學(xué)試卷(含解析)
- 【MOOC】法理學(xué)-西南政法大學(xué) 中國大學(xué)慕課MOOC答案
- 2024年新湘教版七年級上冊數(shù)學(xué)教學(xué)課件 第4章 圖形的認(rèn)識 章末復(fù)習(xí)
- 2024年民用爆炸物品運輸合同
- 2024-2030年中國離合器制造行業(yè)運行動態(tài)及投資發(fā)展前景預(yù)測報告
- 【MOOC】大學(xué)生創(chuàng)新創(chuàng)業(yè)教育-云南大學(xué) 中國大學(xué)慕課MOOC答案
- 《個體防護裝備安全管理規(guī)范AQ 6111-2023》知識培訓(xùn)
- 客戶管理系統(tǒng)技術(shù)服務(wù)合同
- 北京交通大學(xué)《成本會計》2023-2024學(xué)年第一學(xué)期期末試卷
評論
0/150
提交評論