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

1、<p>　　課 程 設(shè) 計(jì) 報(bào) 告</p><p>　　課程名稱 算法導(dǎo)論 </p><p>　　課題名稱 士兵站隊(duì)問題 </p><p>　　專 業(yè) 信息與計(jì)算科學(xué) </p><p>　　班 級(jí)

2、 </p><p>　　學(xué) 號(hào) </p><p>　　姓 名 </p><p>　　指導(dǎo)教師 </p><p>　　2012年 12

3、月 7 日</p><p>　　一、設(shè)計(jì)內(nèi)容與設(shè)計(jì)要求</p><p><b>　　1．設(shè)計(jì)內(nèi)容：</b></p><p>　　對(duì)課程《算法導(dǎo)論》中的常用算法進(jìn)行綜合設(shè)計(jì)或應(yīng)用（具體課題題目見后面的供選題目）。</p><p><b>　　2．設(shè)計(jì)要求：</b></p><p&

4、gt;　　課程設(shè)計(jì)報(bào)告正文內(nèi)容</p><p><b>　　(一)問題的描述；</b></p><p>　　(二)算法設(shè)計(jì)與分析，內(nèi)容包括</p><p>　　1， 算法設(shè)計(jì)，對(duì)問題的分析和算法的設(shè)計(jì)</p><p>　　2，算法描述，以偽代碼形式的算法</p><p>　　3，算法分析，主要是算

5、法的正確性和運(yùn)行時(shí)間的分析</p><p><b>　?。ㄈ┧惴▽?shí)現(xiàn)</b></p><p>　　所有程序的原代碼，要求用C語言程序?qū)崿F(xiàn)，并對(duì)程序?qū)懗霰匾淖⑨尅?lt;/p><p><b>　　書寫格式</b></p><p>　　a．要求用A4紙打印成冊(cè)</p><p>　

6、　b．正文格式：一級(jí)標(biāo)題用3號(hào)黑體,二級(jí)標(biāo)題用四號(hào)宋體加粗,正文用小四號(hào)宋體;行距為22。</p><p>　　c．正文的內(nèi)容:正文總字?jǐn)?shù)要求在3000字左右（不含程序原代碼）。</p><p>　　d．封面格式如下頁。</p><p><b>　　考核方式</b></p><p>　　指導(dǎo)老師負(fù)責(zé)驗(yàn)收程序的運(yùn)行結(jié)果，并

7、結(jié)合學(xué)生的工作態(tài)度、實(shí)際動(dòng)手能力、創(chuàng)新精神和設(shè)計(jì)報(bào)告等進(jìn)行綜合考評(píng)，并按優(yōu)秀、良好、中等、及格和不及格五個(gè)等級(jí)給出每位同學(xué)的課程設(shè)計(jì)成績。具體考核標(biāo)準(zhǔn)包含以下幾個(gè)部分：</p><p>　　a．平時(shí)出勤 （占10%）</p><p>　　b．系統(tǒng)需求分析、功能設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)及程序總體結(jié)構(gòu)合理與否（占10%）</p><p>　　c．程序能否完整、準(zhǔn)確地運(yùn)行，個(gè)人

8、能否獨(dú)立、熟練地調(diào)試程序（占40%）</p><p>　　d．設(shè)計(jì)報(bào)告（占30%）</p><p>　　e．獨(dú)立完成情況（占10%）。</p><p>　　注意：不得抄襲他人的報(bào)告（或給他人抄襲），一旦發(fā)現(xiàn)，成績?yōu)榱惴帧?lt;/p><p><b>　　課程驗(yàn)收要求</b></p><p>　　a．判

9、定算法設(shè)計(jì)的合理性，運(yùn)行相關(guān)程序，獲得正確的數(shù)值結(jié)果。</p><p><b>　　b．回答有關(guān)問題。</b></p><p>　　c．提交課程設(shè)計(jì)報(bào)告。</p><p>　　d．提交軟盤（源程序、設(shè)計(jì)報(bào)告文檔）。</p><p>　　e．依內(nèi)容的創(chuàng)新程度，完善程序情況及對(duì)程序講解情況打分。</p><

10、;p><b>　　3、進(jìn)度安排</b></p><p>　　班級(jí)： 信息與計(jì)算科學(xué)：1001,1002,1003，</p><p><b>　　主講教師 </b></p><p><b>　　時(shí)間安排：</b></p><p>　　第 16 周 星期一 8時(shí)：30分—

11、—11時(shí)：30分</p><p>　　星期二 8時(shí)：30分——11時(shí)：30分</p><p>　　星期四 8時(shí)：30分——11時(shí)：30分</p><p>　　星期五 8時(shí)：30分——11時(shí)：30分</p><p><b>　　目錄</b></p><p>　　一、任務(wù)書…………………………………

12、…………………1</p><p>　　二、問題描述…………………………………………………5</p><p>　　三、算法設(shè)計(jì)與分析…………………………………………6</p><p>　　四、程序調(diào)試…………………………………………………7</p><p>　　五、附件………………………………………………………8</p><

13、p>　　六、評(píng)分表……………………………………………………13</p><p><b>　　三、問題描述</b></p><p>　　在一個(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,

14、y),(x+1,y),…,(x+n-1,y)。如何選擇x和y的值才能使士兵們以最少的總移動(dòng)步數(shù)排成一列。</p><p><b>　　編程任務(wù)</b></p><p>　　計(jì)算使所有士兵排成一行需要的最少移動(dòng)步數(shù)。</p><p><b>　　數(shù)據(jù)輸入</b></p><p>　　由文件sol*.i

15、n提供輸入數(shù)據(jù)。文件的第1行是士兵數(shù)n，1n10000。接下來n行是士兵的初始位置，每行2個(gè)整數(shù)x和y，-10000x，y10000。</p><p><b>　　結(jié)果輸出</b></p><p>　　程序運(yùn)行結(jié)束時(shí)，將計(jì)算結(jié)果輸出到文件sol*.out中。文件的第1行中的數(shù)是士兵排成一行需要的最少移動(dòng)步數(shù)。</p><p><b>

16、　　四、算法設(shè)計(jì)與分析</b></p><p><b>　　算法設(shè)計(jì)</b></p><p>　　士兵站隊(duì)問題是一個(gè)排序問題，問題描述為：網(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)

17、。求需要移動(dòng)的最少步數(shù)。</p><p>　　首先用兩個(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,(這樣就可以錯(cuò)開相同的x軸也可以減少士兵之間間距，找出合適的中位數(shù)。)再把數(shù)組c[n]用選擇排序

18、從小到大排序，找出中位數(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ù)。</p><p><b>　　算法描述</b></p><p><b>　　選擇排序</b></p>

19、<p>　　for(int i=0;i<a.length;i++){</p><p>　　for(int j=i+1;j<a.length;j++){</p><p>　　if(a[i]>=a[j]){</p><p>　　int temp = 0;</p><p>　　temp = a[i];</p&g

20、t;<p>　　a[i] = a[j];</p><p>　　a[j] = temp;</p><p><b>　　} </b></p><p><b>　　}</b></p><p><b>　　找中位數(shù)</b></p><p>　　fo

21、r(int i=0;i<a.length;i++){</p><p>　　c[i] = a[i]-i;</p><p><b>　　}</b></p><p>　　selectSort(c);</p><p>　　if(n%2==0){</p><p>　　mid_a = c[(n-1)/2

22、];</p><p>　　mid_b = b[(n-1)/2];</p><p><b>　　}</b></p><p><b>　　else{</b></p><p>　　mid_a = c[n/2];</p><p>　　mid_b = b[n/2];</p>

23、<p><b>　　}</b></p><p>　　for(int i = 0;i<n;i++)</p><p>　　sum = Math.abs( b[i] - mid_b ) +Math.abs( a[i] - mid_a -i) + sum;</p><p>　　System.out.println("需要移

24、動(dòng)的最少步數(shù)是"+sum+"步");</p><p><b>　　}</b></p><p><b>　　算法分析</b></p><p>　　時(shí)間復(fù)雜度分析：首先使用選擇排序?qū)σ痪S數(shù)組a[],b[],c[]排序，由于選擇排序是一個(gè)嵌套循環(huán)主循環(huán)for i= 0..n-1子循環(huán)for j=1.

25、.n-1所以選擇排序的時(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）。</p><p><b>　　五、程序調(diào)試</b></p>

26、<p><b>　　初始化窗口</b></p><p><b>　　運(yùn)行后窗口</b></p><p><b>　　六、附件</b></p><p><b>　　源程序 </b></p><p>　　import java.awt.Button;

27、</p><p>　　import java.awt.Frame;</p><p>　　import java.awt.TextArea;</p><p>　　import java.awt.TextField;</p><p>　　import java.awt.event.ActionEvent;</p><p>

28、　　import java.awt.event.ActionListener;</p><p>　　import javax.swing.Box;</p><p>　　import javax.swing.JFrame;</p><p>　　public class TheSoldierCorps extends JFrame{</p><p&g

29、t;　　public static void main(String[] args){</p><p>　　launchFrame();</p><p><b>　　}</b></p><p>　　public static void launchFrame(){</p><p>　　Frame f = new JFra

30、me("士兵站隊(duì)");</p><p>　　f.setBounds(350, 150, 450, 300);</p><p>　　Box vertical = Box.createVerticalBox();</p><p>　　final TextField tf1 = new TextField(50);</p><p&g

31、t;　　final TextField tf2 = new TextField(50);</p><p>　　final TextField tf3 = new TextField(50);</p><p>　　//設(shè)置輸入的文本長度 這里 int 指列數(shù)</p><p>　　Button button = new Button("排序");&l

32、t;/p><p><b>　　//設(shè)置一個(gè)按鈕</b></p><p>　　final TextArea ta = new TextArea();</p><p>　　//構(gòu)造一個(gè)新字符串作為新文本的文本區(qū)</p><p>　　//水平布局添加一個(gè)文本區(qū) 和一個(gè)按鈕</p><p>　　vertica

33、l.add(tf1);</p><p>　　vertical.add(tf2);</p><p>　　vertical.add(tf3);</p><p>　　vertical.add(button);</p><p>　　vertical.add(ta);</p><p>　　//窗口添加一個(gè)水平文本區(qū)和一個(gè)按鈕&l

34、t;/p><p>　　f.add(vertical);</p><p>　　//在窗口上添加一個(gè)垂直文本區(qū)</p><p>　　tf1.setText("請(qǐng)輸入一個(gè)整數(shù)表示士兵的個(gè)數(shù)");</p><p>　　tf2.setText("請(qǐng)輸入輸入士兵的X軸坐標(biāo)，以空格隔開");</p><

35、;p>　　tf3.setText("請(qǐng)輸入士兵的Y軸坐標(biāo)，以空格隔開");</p><p>　　button.addActionListener(new ActionListener() {</p><p>　　public void actionPerformed(ActionEvent e) {</p><p>　　int n = 0;

36、</p><p>　　String sum ;</p><p>　　String str1 = tf1.getText();</p><p>　　String str2 = tf2.getText();</p><p>　　String str3 = tf3.getText();</p><p>　　int[ ] m

37、= new TheSoldierCorps().getArr(str1);</p><p>　　int[ ] a = new TheSoldierCorps().getArr(str2);</p><p>　　int[ ] b = new TheSoldierCorps().getArr(str3);</p><p>　　if(m.length!=1 || m[0]

38、!=a.length || a.length!=b.length){</p><p>　　tf1.setText("輸入有誤，請(qǐng)重新輸入");</p><p>　　tf2.setText("請(qǐng)輸入輸入士兵的X軸坐標(biāo)數(shù)與士兵數(shù)不符，請(qǐng)重新輸入，以空格隔開");</p><p>　　tf3.setText("請(qǐng)輸入士兵的

39、Y軸坐標(biāo)數(shù)與士兵數(shù)不符，請(qǐng)重新輸入，以空格隔開");</p><p><b>　　try {</b></p><p>　　Thread.sleep(10000);</p><p>　　} catch (InterruptedException e1) {</p><p>　　e1.printStackTrace

40、();</p><p><b>　　}</b></p><p>　　System.exit(-1);</p><p><b>　　}else{</b></p><p><b>　　n = m[0];</b></p><p><b>　　}<

41、;/b></p><p>　　int[ ] c = new int[a.length];</p><p>　　Crops crops = new Crops();</p><p>　　crops.selectSort(a);</p><p>　　crops.selectSort(b);</p><p>　　Str

42、ing str = "需要移動(dòng)的最少步數(shù)是 "+crops.standInLine(a, b, c, n);</p><p>　　ta.setText(str);</p><p><b>　　}</b></p><p><b>　　});</b></p><p>　　f.setV

43、isible(true);</p><p><b>　　}</b></p><p>　　public int[ ] getArr(String str){</p><p>　　String[ ] strArr = str.split(" ");</p><p>　　int [ ] a = new in

44、t[strArr.length];</p><p>　　for(int i = 0;i<a.length;i++){</p><p>　　a[i] = Integer.valueOf(strArr[i]);</p><p><b>　　}</b></p><p><b>　　return a;</b

45、></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　class Crops{</p><p>　　private int[] a;</p><p>　　private int[] b;</p><p

46、>　　private int[] c;</p><p>　　private int n;</p><p>　　int sum = 0;</p><p>　　String str2;</p><p><b>　　//將數(shù)組排序</b></p><p>　　public int[] selec

47、tSort(int[ ] a){</p><p>　　for(int i=0;i<a.length;i++){</p><p>　　for(int j=i+1;j<a.length;j++){</p><p>　　if(a[i]>=a[j]){</p><p>　　int temp = 0;</p><p

48、>　　temp = a[i];</p><p>　　a[i] = a[j];</p><p>　　a[j] = temp;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b><

49、;/p><p><b>　　return a;</b></p><p><b>　　}</b></p><p>　　//士兵戰(zhàn)隊(duì)，先找出中位數(shù)</p><p>　　public String standInLine(int[] a,int[] b,int[] c,int n){</p>&

50、lt;p>　　int mid_a = 0; int mid_b = 0; </p><p>　　for(int i=0;i<a.length;i++){</p><p>　　c[i] = a[i]-i;</p><p><b>　　}</b></p><p>　　selectSort(c);</p>

51、;<p>　　if(n%2==0){</p><p>　　mid_a = c[(n-1)/2];</p><p>　　mid_b = b[(n-1)/2];</p><p><b>　　}</b></p><p><b>　　else{</b></p><p>

52、　　mid_a = c[n/2];</p><p>　　mid_b = b[n/2];</p><p><b>　　}</b></p><p>　　StringBuilder sb = new StringBuilder();</p><p>　　for(int i = 0;i<n;i++){</p>

53、<p>　　sum = Math.abs( b[i] - mid_b ) +Math.abs( a[i] - mid_a -i) + sum;</p><p>　　String str = "第"+(i+1)+"個(gè)士兵的坐標(biāo)： "+"（"+(mid_a+i)+","+mid_b+")";</p&g

54、t;<p>　　sb.append("\n" + str);</p><p><b>　　}</b></p><p>　　return sum + sb.toString();</p><p><b>　　}</b></p><p><b>　　} <