整數(shù)因子團(tuán)問題報(bào)告

1、數(shù) 據(jù) 結(jié) 構(gòu)課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目: 整數(shù)因子團(tuán)問題 院 系： 經(jīng)濟(jì)管理學(xué)院 專業(yè)班級： 電子商務(wù)2011-2 學(xué)生姓名：于曉靜、侯金一、張慶振 指導(dǎo)教師： 周長紅 2013年7月5日指導(dǎo)教師評語 指導(dǎo)教師： 年 月 日成績評定學(xué) 號姓 名任務(wù)分工成績目 錄1.設(shè)計(jì)內(nèi)容11.1問題描述11.2設(shè)計(jì)要求11.3開發(fā)環(huán)境11.4研究思路12.設(shè)計(jì)步驟32.1需求分析32.2概要設(shè)計(jì)32.3詳細(xì)設(shè)計(jì)52.4調(diào)試分析102.5測試結(jié)果193.設(shè)計(jì)成果展示213.1用戶手冊213.2程序運(yùn)行部分截圖214.總結(jié)與心得體會24附 錄25整數(shù)因子團(tuán)問題1.設(shè)計(jì)內(nèi)容1.1問題描述給定由n個連續(xù)自然數(shù)組成的序列

2、1，n。從當(dāng)前序列中選擇一整數(shù)，它在當(dāng)前序列中至少有2個因子(該整數(shù)本身可以算作一個因子，例如，整數(shù)60的所有因子是：60，30，20，15，12，10，6，5，4，3，2，1。它們構(gòu)成整數(shù)60在當(dāng)前序列中的因子團(tuán) )。從當(dāng)前序列中刪去所選整數(shù)的所有因子。重復(fù)步驟和，直到空序列或當(dāng)前序列中所有數(shù)字在序列中僅有一個因子。其中游戲中的得分是步驟中所選擇的數(shù)字的總和。1.2設(shè)計(jì)要求用戶任意輸入一個整數(shù)n，得到自然數(shù)序列1，n；輸出該序列中依次選定的所有整數(shù)，并求出它們的和；刪除選定整數(shù)時(shí)，將其所有因子一起刪除得到新的序列；要求選定所有整數(shù)之和最大。1.3開發(fā)環(huán)境本程序采用C-Free開發(fā)環(huán)境。1.4

3、研究思路 要解決這個問題，第一件事情就是分析整數(shù)因子之間的關(guān)系。例如整數(shù)8，它的因子有4,2,1，而4的因子有2,1,用如下圖形表示：8412那么當(dāng)我們選定8時(shí)，4,2,1均被刪除；當(dāng)選定4時(shí)，2,1被刪除而8會被留下。另外，在一個序列中，后1/2個數(shù)的因子都可以在前1/2中找到（如果序列中數(shù)字的個數(shù)為奇數(shù)個，那么將總個數(shù)的1/2取整。例如設(shè)n為7,那么7/2為3，所以后1/2數(shù)字為4,5,6,7），所以如果在后1/2數(shù)中還有非素?cái)?shù)的情況下選定序列前1/2中的數(shù)，那么后1/2中會有選定數(shù)的倍數(shù)刪不掉，導(dǎo)致不能得到最大分?jǐn)?shù)。例如，n=8時(shí),有1 2 3 4 | 5 6 7 8如果選4，那么1,2

4、,4被刪除，剩下 3 | 5 6 7 8，得分為4，8被留下刪不掉；若選定8，那么1,2,4,8被刪除，剩下 3 | 5 6 7，得分為8。綜上所述，每次都要選定序列前1/2的數(shù)并刪除其因子團(tuán)得分才可能最大。 因?yàn)槌绦蛞蟮氖亲畲蠛?，所以首先選定的應(yīng)為兩個因子的整數(shù)。例如，在上面的1到8的序列中，7有兩個因子，而8有四個因子。若第一次選定7，那么還剩下2 3 4 | 5 6 8 共六個數(shù)字；若選定8，則剩下3 | 5 6 7共四個數(shù)字。顯然，第一次選8總的可刪除次數(shù)將小于第一次選7的總次數(shù)，由此得到的和會小于第一次選兩個因子的方法。綜上，解決這個題目的關(guān)鍵為兩個。一，只從序列前1/2的整數(shù)中選

5、；二，首先選擇因子為兩個的整數(shù)，每刪除一個數(shù)字就要判斷新序列中是否有含兩個因子的整數(shù)，有則繼續(xù)刪除，沒有兩個因子的則從小到大開始選擇超過兩個因子的整數(shù)。22.設(shè)計(jì)步驟2.1需求分析該程序主要設(shè)計(jì)整數(shù)因子團(tuán)求最大和問題。以整形數(shù)據(jù)格式輸入一個數(shù)，當(dāng)輸入其它非法字符（例如字母）時(shí)，程序?qū)⑻崾据斎胗姓`，需要用戶重新輸入正確的數(shù)據(jù)。輸入正確數(shù)據(jù)后，按Enter鍵，不需要用戶進(jìn)行任何操作，刪除的因子和最優(yōu)解將自動呈現(xiàn)。計(jì)算完成后，用戶按Enter鍵可退出程序。在程序上可以看到程序的說明和輸入提示。用戶將能看到每一次刪除的數(shù)和最優(yōu)解。當(dāng)用戶輸入程序規(guī)定1到9999以外的數(shù)字或字母標(biāo)點(diǎn)等時(shí)，程序?qū)⒆詣犹崾局?/p>

6、新輸入規(guī)定范圍內(nèi)的數(shù)字。2.2概要設(shè)計(jì)程序主要是利用循環(huán)來搜索最應(yīng)該刪除的數(shù)。刪除的數(shù)應(yīng)數(shù)越大，因子個數(shù)越小越好。從最大的數(shù)開始，從因子最少的數(shù)開始刪除。每次刪除后，由于其他數(shù)的因子個數(shù)也會減少，所以從最少因子個數(shù)重新開始搜索。程序中主函數(shù)實(shí)現(xiàn)程序的主要功能，CharToInt和Ten函數(shù)一起實(shí)現(xiàn)了將char型轉(zhuǎn)化為int型的功能。主函數(shù)mainCharToIntTen2.3詳細(xì)設(shè)計(jì)主程序n-s圖：輸入nj=1;j<=n;j+ ai=j c=2;c<=n/2;c+ i=1;i<x/2;i+j=1 j<=ai-1;m+bm=jak=j?YN ai-1%j=0? e+v=0

7、;v<=n;v+m>0q=q+ai-1w+刪除ai-1NYm=c?NYm>1Yk=0Nj+k=0;k<=n;k+m=0n=n-1z+az=az+1z<nz=vNYav=bm-1接上頁m-m=0c=2 i=n+1 t=0m=0Ye=0|e=nN break該程序主函數(shù)主要分成三個部分。對輸入的數(shù)，尋找刪除的最優(yōu)策略，使選擇的數(shù)之和盡量達(dá)到最大，即程序的主題思想。程序展示如下：x=n;a=(int*)malloc(n*sizeof(int);b=(int*)malloc(n*sizeof(int);for(j=1;j<=n;j+)aj-1=j;printf(&q

8、uot;初始序列為：n");for(j=1;j<=n;j+) printf("%d ",aj-1); /*輸出1到n之間的自然數(shù)*/printf("n");for(c=2;c<=n/2;c+) /*輸入的數(shù)的因子的個數(shù)*/e=0; /輸入的數(shù)n在an中的因子bnfor(i=n;ai-1>=x/2;i-) /判斷該因子是否在這個數(shù)組中j=1;while(j<=ai-1)if(ai-1%j=0) /找出該數(shù)的因子for(k=0;k<n;k+)if(ak=j) bm=j; /將該數(shù)的因子存在數(shù)組bn中m+;k=0;j+;

9、if(m>1)if(m=c) /將n在an中的因子數(shù)刪除，重新排列刪除因子之后的數(shù)組printf("第%d次刪除的數(shù)為：%dn",w,ai-1);w+;q=q+ai-1;while(m>0)for(v=0;v<n;v+) if(av=bm-1)z=v;while(z<n)az=az+1; /將刪除的av的后面的數(shù)az+1賦值給azz+;n=n-1;m-;c=2; /重置因子的個數(shù)i=n+1;e=0;m=0;elsee+;m=0;if(e=0|e=n)break;printf("最優(yōu)解為：%d",q);對輸入的非自然數(shù)做出的調(diào)整，程

10、序展示如下：int g,l,flag;while(1) /輸入for(g=0;g<MAX;g+)scanf("%c",&og);if(og='n')break;l=g;if(l>4) /長度超過4位，非法輸入printf("輸入非法，請重新輸入！n");continue;flag=0;for(g=0;g<l;g+) /判斷每個字符是否在09之間if(og<'0' | og>'9')flag=1;break;if(flag=1) /其中有一個不在，則輸入非法printf(

11、"輸入非法，請重新輸入！n");continue;break;n=CharToInt(o,l); /把字符型轉(zhuǎn)化為int型對程序界面的優(yōu)化和美觀的操作，包括通過字體顏色的設(shè)計(jì)對該程序色調(diào)的設(shè)計(jì)。程序代碼展示：system("color E");printf("nnnnnnnn");printf("ttt* n");printf("tt * * n");printf("tt * 歡迎進(jìn)入整數(shù)因子團(tuán)程序 *n");printf("tt * * n");prin

12、tf("ttt* n");printf("n");Sleep(2000);system("cls");printf("*n");printf("*->程序說明：tttttt*n*ttttttt*n");printf("*->任意指定一個整數(shù)nttttt*n*ttttttt*n*->得到初始自然數(shù)序列1. ntttt*n*ttttttt*n*->從中任意選定一個整數(shù)Atttt*n*ttttttt*n*->刪除A及其所有因子ttttt*n*ttttttt*n*

13、->循環(huán)前兩步。序列為空或剩余整數(shù)均只有一個因子結(jié)束t*n*ttttttt*n*->得分為所有選定整數(shù)A之和tttt*");printf("n*ttttttt*n");printf("*n");2.4調(diào)試分析一次調(diào)試：程序?qū)懲旰?，出現(xiàn)無法正常循環(huán)的情況，程序運(yùn)行后不按照我的想法循環(huán)，出現(xiàn)如下圖所示情況，程序到這一步就停止運(yùn)行。 見下頁。后經(jīng)調(diào)試的，程序的循環(huán)條件錯誤。調(diào)試過程：見下頁。程序主動跳至這一步。原循環(huán)為：for(i=n;ai-1>=n/2;i+)for(j=1;j<=n;j+)if(ai/j=0)更改后為：fo

14、r(i=n;ai-1>=x/2;i-)j=1;while(j<=ai-1)if(ai-1%j=0). j+; 二次調(diào)試：程序整體功能實(shí)現(xiàn)后，程序的穩(wěn)定性還存在問題。程序輸入字母或者其他符號時(shí)，程序會出現(xiàn)崩潰，如下圖所示：增加穩(wěn)定性需要判斷程序輸入是否非法。我們用了一個字符串?dāng)?shù)組來存儲輸入的字符，并逐個判斷字符是否為數(shù)字，若存在非法字符，則要求重新輸入。增加穩(wěn)定性后，程序效果為：見下頁。三次調(diào)試：程序運(yùn)行時(shí)發(fā)現(xiàn)當(dāng)輸入超過40時(shí)，結(jié)果明顯錯誤：接下頁。調(diào)試時(shí)，對各個數(shù)值進(jìn)行監(jiān)控，發(fā)現(xiàn)記錄質(zhì)數(shù)個數(shù)的e值有問題。e的值歸零的位置錯誤，將e的位置改動之后，重新調(diào)試，e的值恢復(fù)正常。接下頁。2

15、.5測試結(jié)果在程序中輸入：s回車后程序顯示：輸入非法請重新輸入。在程序中輸入：10回車后顯示：初始序列為：1 2 3 4 5 6 7 8 9 10第一次刪除的數(shù)為：7第二次刪除的數(shù)為：9第三次刪除的數(shù)為：6第四次刪除的數(shù)為：10第五次刪除的數(shù)為：8最優(yōu)解為：40在程序中輸入：6回車后顯示：初始序列為：1 2 3 4 5 6 第一次刪除的數(shù)為：5第二次刪除的數(shù)為：4第三次刪除的數(shù)為：6最優(yōu)解為：15在程序中輸入：12回車后顯示：初始序列為：1 2 3 4 5 6 7 8 9 10 11 12第一次刪除的數(shù)為：11第二次刪除的數(shù)為：9第三次刪除的數(shù)為：6第四次刪除的數(shù)為：12第五次刪除的數(shù)為：10

16、最優(yōu)解為：48在i3處理器的配置中，運(yùn)算10出最優(yōu)解需要大約20秒，運(yùn)算20出最優(yōu)解大約需要22秒，運(yùn)算50出最優(yōu)解大約需要24秒。輸入的數(shù)越大，需要運(yùn)算的次數(shù)越多，占用的時(shí)間越長。313.設(shè)計(jì)成果展示3.1用戶手冊用戶必須在Windows的環(huán)境下，雙擊“整數(shù)因子團(tuán).exe”即可運(yùn)行該程序。程序運(yùn)行后，首先進(jìn)入歡迎界面。暫停兩秒后進(jìn)入問題介紹及運(yùn)算界面。用戶在提示下輸入任意整數(shù)n（1<n<9999），按Enter鍵。如果輸入非法，程序?qū)⒆詣犹崾局匦螺斎?。在上一步后，程序自動根?jù)n給出原始連續(xù)自然數(shù)序列，并給出在最優(yōu)條件下每一步應(yīng)該選定的整數(shù)，和選定整數(shù)的和（如果輸入的整數(shù)n較大，程

17、序運(yùn)行耗時(shí)將變多，需要耐心等待）。完成以上操作后，程序會提示是否重新開始。若是，鍵盤輸入y，然后Enter，程序重新顯示請輸入整數(shù)n的界面，循環(huán)上面的操作；若否，按任意鍵結(jié)束程序。3.2程序運(yùn)行部分截圖見下頁。歡迎界面。程序說明及計(jì)算界面。輸入6，按Enter。按y之后，按Enter，重新開始界面。4.總結(jié)與心得體會通過這次歷時(shí)兩個周的課程設(shè)計(jì)，我們不僅僅學(xué)到了知識，更加體會到了團(tuán)隊(duì)合作的強(qiáng)大。剛看到題目的時(shí)候暗自慶幸，覺得不是特別難，比起貪吃蛇，老鼠走迷宮，五子棋人機(jī)對弈要容易很多，于是我們信心滿滿的開始了。但是，問題并不像我們想象的那么簡單。那些小游戲性質(zhì)的程序雖難，網(wǎng)上或者圖書館介紹C語

18、言實(shí)例的書上卻有很多介紹，甚至有可以運(yùn)行的源代碼。我們的雖然簡單一些，卻因?yàn)轭}目較新，在網(wǎng)上搜索時(shí)收獲寥寥無幾，幾乎沒有什么可用信息。在圖書館找了一上午，也沒有發(fā)現(xiàn)關(guān)于該問題的書籍。既然如此，我們只能完全靠自己了。信息收集是我們?nèi)艘黄疬M(jìn)行的，之后因?yàn)楹罱鹨痪幊绦虮容^在行，自然承擔(dān)了寫程序的重任。張慶振輔助侯金一寫了部分代碼，并負(fù)責(zé)了n-s圖的設(shè)計(jì)和報(bào)告的第二部分設(shè)計(jì)步驟，其中，調(diào)試部分是由熟悉程序的侯金一寫的。于曉靜則負(fù)責(zé)了程序美化，n-s圖的編輯以及報(bào)告第一、第三部分的書寫和排版。在完整的程序?qū)懗鰜?，看到它順暢的運(yùn)行時(shí)，我們長舒一口氣，感覺輕松了許多。眾人拾柴火焰高。一個人來做這些可能要很

19、久，但三人合作就可以勢如破竹。在這兩個周里我們的小團(tuán)隊(duì)一直都很和諧融洽，我們之間有了更深入的了解，增進(jìn)了友誼。在這一次團(tuán)隊(duì)合作的程序設(shè)計(jì)的過程中，我受益匪淺。剛剛接到題目的要求的時(shí)候，我感覺這看似是一個不可能完成的任務(wù)，因?yàn)檫@一程序和我們以往所設(shè)計(jì)的那些小程序比起來，它們的復(fù)雜程度簡直不是一個層次上的。我雖才疏學(xué)淺，卻并不畏懼挑戰(zhàn)。更重要的是，我們組有著自己的優(yōu)勢，擅長程序設(shè)計(jì)的成員侯金一，擅長組織設(shè)計(jì)和優(yōu)化的于曉靜。這提供了足夠的理由讓我對這一挑戰(zhàn)充滿自信。在程序設(shè)計(jì)之初，我們遇到的最大的困難時(shí)缺少與這一程序有關(guān)的資料。在稍顯簡陋的圖書館里翻閱了很久，卻找不到多少與這一程序相關(guān)的資料。在百度

20、的搜索中，整數(shù)因子團(tuán)的問題也是寥寥無幾。在這樣的情況下，我們只好靠我們自己去思考探索了?；蛟S我們當(dāng)時(shí)意識不到，但經(jīng)過一番的努力做出些效果的時(shí)候，我們才真正體會到這種難以言說的喜悅。我承認(rèn)自己在編程這一方面不感冒。但對于組長分配的任務(wù)和對程序的討論，我一直都在積極參與。我雖資質(zhì)平庸，卻會盡心盡力地輔佐金一編程和曉靜的報(bào)告，雖然我付出的努力不是最多的，卻為自己的付出感到欣喜。 張慶振經(jīng)過這次課程設(shè)計(jì)，我深刻的認(rèn)識到了團(tuán)隊(duì)合作的重要性，如果沒有兩位隊(duì)友的支持與幫助，是根本不可能完成的。這次的選題由于沒有在網(wǎng)上找到合適的源代碼，只好靠我們自己編。在編程的過程中，隊(duì)友給了我很大的幫助，幫我找程序的缺陷，

21、跟我一起想解決辦法。真的很感謝他們。這次編程不僅使我對數(shù)據(jù)結(jié)構(gòu)和c語言有了更深刻的認(rèn)識，更讓我認(rèn)識到了測試的重要性。很多問題編程人員自己是很難發(fā)現(xiàn)的，不過其他組的人都會積極地幫忙測試。編程是枯燥的，但當(dāng)你的程序調(diào)試成功時(shí)，那種喜悅又會給你莫大的鼓舞。這次課程設(shè)計(jì)使我收獲了太多太多，讓我有了一次永生難忘的經(jīng)歷。 侯金一 兩個周的課程設(shè)計(jì)讓我受益匪淺。雖然在編程上沒有幫上什么忙，但是我揚(yáng)長避短，在各種優(yōu)化、美化方面竭盡所能，甚至去好幾個論壇注冊了會員發(fā)帖求助，可惜并沒有什么收獲。美化執(zhí)行界面是最讓我覺得有趣的部分。一直想把執(zhí)行時(shí)那個黑色的窗口換個顏色，卻一直沒能找到方法，反而找到了讓屏幕暫停以及改變字體顏色的方法。記得那天我們?nèi)齻€一邊不停地?fù)Q顏色，一邊開心的討論怎樣設(shè)計(jì)會更好看。之后就給它設(shè)計(jì)了歡迎界面和程序說明的框框。做n-