算法導論士兵站隊課程設計(編輯修改稿)
2025-07-10 10:51 本頁面
【文章內容簡介】 小到大排序，找出中位數(shù) b[(n1)/2],(這里減一是因為數(shù)組的下標是從 0 開始的 )以此確定士兵的 y 軸坐標，然后再構造一個新的一維數(shù)組 c[n],c[i]=a[i]i,(這樣就可以錯開 相同的 x 軸也可以減少士兵之間間距，找出合適的中位數(shù)。 )再把數(shù)組 c[n]用選擇排序從小到大排序，找出中位數(shù) c[(n1)/2]以此確定 第一個士兵的 x 軸坐標，第二個士兵的 x 軸坐標為 c[(n1)/2]+1,依次類推第 n 個士兵的 x軸坐標為 c[(n1)/2]+(n1)。最后再計算這些士兵 移動的步數(shù)和得到移動的最少步數(shù)。 算法描述 選擇排序 for(int i=0。i。i++){ for(int j=i+1。j。j++){ if(a[i]=a[j]){ int temp = 0。 temp = a[i]。 a[i] = a[j]。 a[j] = temp。 } } 找中位數(shù) for(int i=0。i。i++){ c[i] = a[i]i。 } 7 selectSort(c)。 if(n%2==0){ mid_a = c[(n1)/2]。 mid_b = b[(n1)/2]。 } else{ mid_a = c[n/2]。 mid_b = b[n/2]。 } for(int i = 0。in。i++) sum = ( b[i] mid_b ) +( a[i] mid_a i) + sum。 (需要移動的最少步數(shù)是 +sum+步 )。 } 算法分析 時間復雜度分析 ： 首先使用選擇排序對一維數(shù)組 a[],b[],c[]排序，由于選擇排序是一個嵌套循環(huán)主循環(huán) for i= 0..n1 子循環(huán) for j=1..n1 所以選擇排序的時間復雜度為 O(n2n)因為要遍歷三個數(shù)組并對其排大小所以時間復雜度變?yōu)?O(3n23n)，數(shù)組 c[]是遍歷數(shù)組 a[]得到的所以此時時間復雜又變?yōu)镺(3n22n)最后我們要同時遍歷數(shù)組 a[]和數(shù)組 b[]以求出士兵移動后的坐標和士兵需要移動的最少步數(shù)。所以最后得到的時間復雜度 為 O（ 3n2n） 。 五 、程序調試 初始化窗口 8 運行后窗口 六 、附件 源程序 import 。 import 。 import 。 import 。 import 。 import 。 9 import 。 import 。 public class TheSoldierCorps extends JFrame{ public static void main(String[] args){ launchFrame()。 } public static void launchFrame(){
畢業(yè)設計相關推薦
鄂ICP備17016276號-1