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

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

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

2、的描述；(二)算法設(shè)計(jì)與分析，內(nèi)容包括1，算法設(shè)計(jì)，對問題的分析和算法的設(shè)計(jì)2，算法描述，以偽代碼形式的算法3，算法分析，主要是算法的正確性和運(yùn)行時(shí)間的分析（三）算法實(shí)現(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é)驗(yàn)收程序的運(yùn)行結(jié)果，并結(jié)合學(xué)生的工作態(tài)度、實(shí)際動手能力、創(chuàng)新精神和設(shè)計(jì)報(bào)告等進(jìn)行綜合考評，并

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

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

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

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

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

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