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

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

2、。2設(shè)計(jì)要求：l 課程設(shè)計(jì)報(bào)告正文內(nèi)容(一)問題的描述；(二)算法設(shè)計(jì)與分析，內(nèi)容包括1， 算法設(shè)計(jì)，對(duì)問題的分析和算法的設(shè)計(jì)2，算法描述，以偽代碼形式的算法3，算法分析，主要是算法的正確性和運(yùn)行時(shí)間的分析（三）算法實(shí)現(xiàn)所有程序的原代碼，要求用C語言程序?qū)崿F(xiàn)，并對(duì)程序?qū)懗霰匾淖⑨?。l 書寫格式a要求用A4紙打印成冊(cè)b正文格式：一級(jí)標(biāo)題用3號(hào)黑體,二級(jí)標(biāo)題用四號(hào)宋體加粗,正文用小四號(hà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í)際動(dòng)手能力、創(chuàng)新精神和設(shè)計(jì)報(bào)告等進(jìn)行綜合考評(píng)，

3、并按優(yōu)秀、良好、中等、及格和不及格五個(gè)等級(jí)給出每位同學(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%）e獨(dú)立完成情況（占10%）。注意：不得抄襲他人的報(bào)告（或給他人抄襲），一旦發(fā)現(xiàn)，成績?yōu)榱惴?。l 課程驗(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)新程度，完善程序情況及對(duì)程序講解情況打分。3、進(jìn)度安排1、 班級(jí)

4、： 信息與計(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分目錄一、任務(wù)書1二、問題描述5三、算法設(shè)計(jì)與分析6四、程序調(diào)試7五、附件8六、評(píng)分表13三、問題描述 在一個(gè)劃分成網(wǎng)格的操場上，n個(gè)士兵散亂地站在網(wǎng)格點(diǎn)上。網(wǎng)格點(diǎn)由整數(shù)坐標(biāo)(x,y)表示。士兵們可以沿網(wǎng)格邊上、下、左、右移動(dòng)一步，但在同一時(shí)刻任一網(wǎng)格點(diǎn)上只能有一名士兵。按照軍官的命令，士兵們要整齊地列成一個(gè)水平隊(duì)列，即排列成(x,y),(x+1,y),(

5、x+n-1,y)。如何選擇x和y的值才能使士兵們以最少的總移動(dòng)步數(shù)排成一列。編程任務(wù)計(jì)算使所有士兵排成一行需要的最少移動(dòng)步數(shù)。數(shù)據(jù)輸入 由文件sol*.in提供輸入數(shù)據(jù)。文件的第1行是士兵數(shù)n，1£n£10000。接下來n行是士兵的初始位置，每行2個(gè)整數(shù)x和y，-10000£x，y£10000。結(jié)果輸出程序運(yùn)行結(jié)束時(shí)，將計(jì)算結(jié)果輸出到文件sol*.out中。文件的第1行中的數(shù)是士兵排成一行需要的最少移動(dòng)步數(shù)。輸入文件示例輸出文件示例sol0.insol0.out51 22 21 33 -23 38四、算法設(shè)計(jì)與分析算法設(shè)計(jì)士兵站隊(duì)問題是一個(gè)排序問題，問題

6、描述為：網(wǎng)格點(diǎn)由整數(shù)坐標(biāo)(x,y)表示。士兵們可以沿網(wǎng)格邊上、下、左、右移動(dòng)一步，但在同一時(shí)刻任一網(wǎng)格點(diǎn)上只能有一名士兵。按照軍官的命令，士兵們要整齊地列成一個(gè)水平隊(duì)列，即排列成(x,y),(x+1,y),(x+n-1,y)。求需要移動(dòng)的最少步數(shù)。首先用兩個(gè)一維數(shù)組an,bn分別表示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ù)組cn,ci=ai-i,(這樣就可以錯(cuò)開相同的x軸也可以減少士兵之間間距，找出合適的中位數(shù)。)再把數(shù)組cn用選擇排序從小到大排

7、序，找出中位數(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-1)/2+(n-1)。最后再計(jì)算這些士兵移動(dòng)的步數(shù)和得到移動(dòng)的最少步數(shù)。算法描述 選擇排序for(int i=0;i<a.length;i+)for(int j=i+1;j<a.length;j+)if(ai>=aj)int temp = 0; temp = ai; ai = aj; aj = temp; 找中位數(shù)for(int i=0;i<a.length;i+) ci = ai-i; selectSort(c);if(n%2=

8、0) mid_a = c(n-1)/2; mid_b = b(n-1)/2; elsemid_a = cn/2; mid_b = bn/2;for(int i = 0;i<n;i+) sum = Math.abs( bi - mid_b ) +Math.abs( ai - mid_a -i) + sum; System.out.println("需要移動(dòng)的最少步數(shù)是"+sum+"步");算法分析時(shí)間復(fù)雜度分析：首先使用選擇排序?qū)σ痪S數(shù)組a,b,c排序，由于選擇排序是一個(gè)嵌套循環(huán)主循環(huán)for i= 0.n-1子循環(huán)for j=1.n-1所以選擇排序的

9、時(shí)間復(fù)雜度為O(n2-n)因?yàn)橐闅v三個(gè)數(shù)組并對(duì)其排大小所以時(shí)間復(fù)雜度變?yōu)镺(3n2-3n)，數(shù)組c是遍歷數(shù)組a得到的所以此時(shí)時(shí)間復(fù)雜又變?yōu)镺(3n2-2n)最后我們要同時(shí)遍歷數(shù)組a和數(shù)組b以求出士兵移動(dòng)后的坐標(biāo)和士兵需要移動(dòng)的最少步數(shù)。所以最后得到的時(shí)間復(fù)雜度為O（3n2-n）。五、程序調(diào)試初始化窗口 運(yùn)行后窗口六、附件源程序 import java.awt.Button;import java.awt.Frame;import java.awt.TextArea;import java.awt.TextField;import java.awt.event.ActionEvent;impo

10、rt java.awt.event.ActionListener;import javax.swing.Box;import javax.swing.JFrame;public class TheSoldierCorps extends JFramepublic static void main(String args) launchFrame();public static void launchFrame()Frame f = new JFrame("士兵站隊(duì)");f.setBounds(350, 150, 450, 300);Box vertical = Box.cr

11、eateVerticalBox();final TextField tf1 = new TextField(50);final TextField tf2 = new TextField(50);final TextField tf3 = new TextField(50);/設(shè)置輸入的文本長度 這里 int 指列數(shù)Button button = new Button("排序");/設(shè)置一個(gè)按鈕final TextArea ta = new TextArea(); /構(gòu)造一個(gè)新字符串作為新文本的文本區(qū)/水平布局添加一個(gè)文本區(qū) 和一個(gè)按鈕vertical.add(tf1);v

12、ertical.add(tf2);vertical.add(tf3);vertical.add(button);vertical.add(ta);/窗口添加一個(gè)水平文本區(qū)和一個(gè)按鈕f.add(vertical);/在窗口上添加一個(gè)垂直文本區(qū)tf1.setText("請(qǐng)輸入一個(gè)整數(shù)表示士兵的個(gè)數(shù)");tf2.setText("請(qǐng)輸入輸入士兵的X軸坐標(biāo)，以空格隔開");tf3.setText("請(qǐng)輸入士兵的Y軸坐標(biāo)，以空格隔開");button.addActionListener(new ActionListener() public v

13、oid actionPerformed(ActionEvent e) int n = 0; String sum ; String str1 = tf1.getText(); String str2 = tf2.getText(); String str3 = tf3.getText(); int m = new TheSoldierCorps().getArr(str1); int a = new TheSoldierCorps().getArr(str2); int b = new TheSoldierCorps().getArr(str3); if(m.length!=1 | m0!=a

14、.length | a.length!=b.length) tf1.setText("輸入有誤，請(qǐng)重新輸入"); tf2.setText("請(qǐng)輸入輸入士兵的X軸坐標(biāo)數(shù)與士兵數(shù)不符，請(qǐng)重新輸入，以空格隔開"); tf3.setText("請(qǐng)輸入士兵的Y軸坐標(biāo)數(shù)與士兵數(shù)不符，請(qǐng)重新輸入，以空格隔開"); try Thread.sleep(10000); catch (InterruptedException e1) e1.printStackTrace();System.exit(-1); else n = m0; int c = new

15、 inta.length; Crops crops = new Crops(); crops.selectSort(a); crops.selectSort(b); String str = "需要移動(dòng)的最少步數(shù)是 "+crops.standInLine(a, b, c, n); ta.setText(str);); f.setVisible(true);public int getArr(String str)String strArr = str.split(" ");int a = new intstrArr.length;for(int i =

16、0;i<a.length;i+)ai = Integer.valueOf(strArri);return a;class Cropsprivate int a;private int b;private int c;private int n;int sum = 0; String str2;/將數(shù)組排序 public int selectSort(int a) for(int i=0;i<a.length;i+) for(int j=i+1;j<a.length;j+) if(ai>=aj) int temp = 0; temp = ai; ai = aj; aj =

17、 temp; return a; /士兵戰(zhàn)隊(duì)，先找出中位數(shù) public String standInLine(int a,int b,int c,int n) int mid_a = 0; int mid_b = 0; for(int i=0;i<a.length;i+) ci = ai-i; selectSort(c); if(n%2=0) mid_a = c(n-1)/2; mid_b = b(n-1)/2; else mid_a = cn/2; mid_b = bn/2; StringBuilder sb = new StringBuilder(); for(int i = 0;i<n;i+) sum = Math.abs( bi - mid_b ) +Math.abs( ai - mid_