算法導論士兵站隊課程設計

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

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

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

4、： 信息與計算科學：1001,1002,1003，2、 主講教師：陽衛(wèi)鋒3、 時間安排：第 16 周 星期一 8時：30分11時：30分 星期二 8時：30分11時：30分 星期四 8時：30分11時：30分 星期五 8時：30分11時：30分目錄一、任務書1二、問題描述5三、算法設計與分析6四、程序調試7五、附件8六、評分表13三、問題描述 在一個劃分成網(wǎng)格的操場上，n個士兵散亂地站在網(wǎng)格點上。網(wǎng)格點由整數(shù)坐標(x,y)表示。士兵們可以沿網(wǎng)格邊上、下、左、右移動一步，但在同一時刻任一網(wǎng)格點上只能有一名士兵。按照軍官的命令，士兵們要整齊地列成一個水平隊列，即排列成(x,y),(x+1,y),(

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

6、描述為：網(wǎng)格點由整數(shù)坐標(x,y)表示。士兵們可以沿網(wǎng)格邊上、下、左、右移動一步，但在同一時刻任一網(wǎng)格點上只能有一名士兵。按照軍官的命令，士兵們要整齊地列成一個水平隊列，即排列成(x,y),(x+1,y),(x+n-1,y)。求需要移動的最少步數(shù)。首先用兩個一維數(shù)組an,bn分別表示n個士兵的x,y坐標,再把表示士兵的y軸坐標的數(shù)組用選擇排序從小到大排序，找出中位數(shù)b(n-1)/2,(這里減一是因為數(shù)組的下標是從0開始的)以此確定士兵的y軸坐標，然后再構造一個新的一維數(shù)組cn,ci=ai-i,(這樣就可以錯開相同的x軸也可以減少士兵之間間距，找出合適的中位數(shù)。)再把數(shù)組cn用選擇排序從小到大排

7、序，找出中位數(shù)c(n-1)/2以此確定第一個士兵的x軸坐標，第二個士兵的x軸坐標為c(n-1)/2+1,依次類推第n個士兵的x軸坐標為c(n-1)/2+(n-1)。最后再計算這些士兵移動的步數(shù)和得到移動的最少步數(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("需要移動的最少步數(shù)是"+sum+"步");算法分析時間復雜度分析：首先使用選擇排序對一維數(shù)組a,b,c排序，由于選擇排序是一個嵌套循環(huán)主循環(huán)for i= 0.n-1子循環(huán)for j=1.n-1所以選擇排序的

9、時間復雜度為O(n2-n)因為要遍歷三個數(shù)組并對其排大小所以時間復雜度變?yōu)镺(3n2-3n)，數(shù)組c是遍歷數(shù)組a得到的所以此時時間復雜又變?yōu)镺(3n2-2n)最后我們要同時遍歷數(shù)組a和數(shù)組b以求出士兵移動后的坐標和士兵需要移動的最少步數(shù)。所以最后得到的時間復雜度為O（3n2-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("士兵站隊");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);/設置輸入的文本長度 這里 int 指列數(shù)Button button = new Button("排序");/設置一個按鈕final TextArea ta = new TextArea(); /構造一個新字符串作為新文本的文本區(qū)/水平布局添加一個文本區(qū) 和一個按鈕vertical.add(tf1);v

12、ertical.add(tf2);vertical.add(tf3);vertical.add(button);vertical.add(ta);/窗口添加一個水平文本區(qū)和一個按鈕f.add(vertical);/在窗口上添加一個垂直文本區(qū)tf1.setText("請輸入一個整數(shù)表示士兵的個數(shù)");tf2.setText("請輸入輸入士兵的X軸坐標，以空格隔開");tf3.setText("請輸入士兵的Y軸坐標，以空格隔開");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("輸入有誤，請重新輸入"); tf2.setText("請輸入輸入士兵的X軸坐標數(shù)與士兵數(shù)不符，請重新輸入，以空格隔開"); tf3.setText("請輸入士兵的Y軸坐標數(shù)與士兵數(shù)不符，請重新輸入，以空格隔開"); 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 = "需要移動的最少步數(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)隊，先找出中位數(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_