算法導(dǎo)論士兵站隊課程設(shè)計

《算法導(dǎo)論士兵站隊課程設(shè)計》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、課程設(shè)計報告課程名稱算法導(dǎo)論課題名稱士兵站隊問題專業(yè)信息與計算科學(xué)班級信科1002班學(xué)號023202180222姓名陽丹簡琵珍李志良指導(dǎo)教師陽衛(wèi)鋒2012年12月7日13湖南工程學(xué)院課程設(shè)計任務(wù)書課程名稱算法導(dǎo)論課題士兵戰(zhàn)隊問題專業(yè)班級信科1002班學(xué)生姓名陽丹簡琵珍李志良學(xué)號023202180222指導(dǎo)老師陽衛(wèi)鋒審批任務(wù)書下達(dá)日期2012年11月26日任務(wù)完成日期2012年12月7日13一、設(shè)計內(nèi)容與設(shè)計要求1．設(shè)計內(nèi)容：對課程《算法導(dǎo)論》中的常用算法進(jìn)行綜合設(shè)計或應(yīng)用（具體課題題目見后面的供選題目）。2．設(shè)計要求：l課程設(shè)計報告正文內(nèi)容(一)問題

2、的描述；(二)算法設(shè)計與分析，內(nèi)容包括1，算法設(shè)計，對問題的分析和算法的設(shè)計2，算法描述，以偽代碼形式的算法3，算法分析，主要是算法的正確性和運行時間的分析（三）算法實現(xiàn)所有程序的原代碼，要求用C語言程序?qū)崿F(xiàn)，并對程序?qū)懗霰匾淖⑨?。l書寫格式a．要求用A4紙打印成冊b．正文格式：一級標(biāo)題用3號黑體,二級標(biāo)題用四號宋體加粗,正文用小四號宋體;行距為22。c．正文的內(nèi)容:正文總字?jǐn)?shù)要求在3000字左右（不含程序原代碼）。d．封面格式如下頁。l考核方式指導(dǎo)老師負(fù)責(zé)驗收程序的運行結(jié)果，并結(jié)合學(xué)生的工作態(tài)度、實際動手能力、創(chuàng)新精神和設(shè)計報告等進(jìn)行綜合考評，并

3、按優(yōu)秀、良好、中等、及格和不及格五個等級給出每位同學(xué)的課程設(shè)計成績。具體考核標(biāo)準(zhǔn)包含以下幾個部分：a．平時出勤（占10%）b．系統(tǒng)需求分析、功能設(shè)計、數(shù)據(jù)結(jié)構(gòu)設(shè)計及程序總體結(jié)構(gòu)合理與否（占10%）c．程序能否完整、準(zhǔn)確地運行，個人能否獨立、熟練地調(diào)試程序（占40%）d．設(shè)計報告（占30%）13e．獨立完成情況（占10%）。注意：不得抄襲他人的報告（或給他人抄襲），一旦發(fā)現(xiàn)，成績?yōu)榱惴?。l課程驗收要求a．判定算法設(shè)計的合理性，運行相關(guān)程序，獲得正確的數(shù)值結(jié)果。b．回答有關(guān)問題。c．提交課程設(shè)計報告。d．提交軟盤（源程序、設(shè)計報告文檔）。e．依內(nèi)容的創(chuàng)新

4、程度，完善程序情況及對程序講解情況打分。3、進(jìn)度安排1、班級：信息與計算科學(xué)：1001,1002,1003，2、主講教師：陽衛(wèi)鋒3、時間安排：第16周星期一8時：30分——11時：30分星期二8時：30分——11時：30分星期四8時：30分——11時：30分星期五8時：30分——11時：30分13目錄一、任務(wù)書……………………………………………………1二、問題描述…………………………………………………5三、算法設(shè)計與分析…………………………………………6四、程序調(diào)試…………………………………………………7五、附件…………………………………………………

5、……8六、評分表……………………………………………………1313三、問題描述在一個劃分成網(wǎng)格的操場上，n個士兵散亂地站在網(wǎng)格點上。網(wǎng)格點由整數(shù)坐標(biāo)(x,y)表示。士兵們可以沿網(wǎng)格邊上、下、左、右移動一步，但在同一時刻任一網(wǎng)格點上只能有一名士兵。按照軍官的命令，士兵們要整齊地列成一個水平隊列，即排列成(x,y),(x+1,y),…,(x+n-1,y)。如何選擇x和y的值才能使士兵們以最少的總移動步數(shù)排成一列。編程任務(wù)計算使所有士兵排成一行需要的最少移動步數(shù)。數(shù)據(jù)輸入由文件sol*.in提供輸入數(shù)據(jù)。文件的第1行是士兵數(shù)n，1￡n￡10000。接下來n行

6、是士兵的初始位置，每行2個整數(shù)x和y，-10000￡x，y￡10000。結(jié)果輸出程序運行結(jié)束時，將計算結(jié)果輸出到文件sol*.out中。文件的第1行中的數(shù)是士兵排成一行需要的最少移動步數(shù)。輸入文件示例輸出文件示例sol0.insol0.out51222133-233813四、算法設(shè)計與分析算法設(shè)計士兵站隊問題是一個排序問題，問題描述為：網(wǎng)格點由整數(shù)坐標(biāo)(x,y)表示。士兵們可以沿網(wǎng)格邊上、下、左、右移動一步，但在同一時刻任一網(wǎng)格點上只能有一名士兵。按照軍官的命令，士兵們要整齊地列成一個水平隊列，即排列成(x,y),(x+1,y),…,(x+n-1,y

7、)。求需要移動的最少步數(shù)。首先用兩個一維數(shù)組a[n],b[n]分別表示n個士兵的x,y坐標(biāo),再把表示士兵的y軸坐標(biāo)的數(shù)組用選擇排序從小到大排序，找出中位數(shù)b[(n-1)/2],(這里減一是因為數(shù)組的下標(biāo)是從0開始的)以此確定士兵的y軸坐標(biāo)，然后再構(gòu)造一個新的一維數(shù)組c[n],c[i]=a[i]-i,(這樣就可以錯開相同的x軸也可以減少士兵之間間距，找出合適的中位數(shù)。)再把數(shù)組c[n]用選擇排序從小到大排序，找出中位數(shù)c[(n-1)/2]以此確定第一個士兵的x軸坐標(biāo)，第二個士兵的x軸坐標(biāo)為c[(n-1)/2]+1,依次類推第n個士兵的x軸坐標(biāo)為c[(n

8、-1)/2]+(n-1)。最后再計算這些士兵移動的步數(shù)和得到移動的最少步數(shù)。算法描述選擇排序for(inti