分治算法講解(編輯修改稿)
2025-09-01 03:31 本頁面
【文章內(nèi)容簡介】 int x。 cinx。 for(i=0。in。i++) { if(s[i]==x) { coutiendl。 break。 } } if(i==n) coutNot foundendl。 return 0。}二分寫法：includeiostreamusing namespace std。void erfen(int a[],int n,int key){ int low=0,high=n1,mid。 while(low=high) { mid=(low+high)/2。 if(a[mid]==key) { cout這個數(shù)的下標是：midendl。 break。 } else if(a[mid]key) high=mid1。 else low=mid+1。 } if(lowhigh) coutNot Found！endl。} int main(){ int a[100]。 int n,key,i。 cinn。 for(i=0。in。i++) cina[i]。 cinkey。 erfen(a,n,key)。 return 0。}二分遞歸：include iostreamusing namespace std。int search(int a[],int left,int right,int key){ if(leftright) { coutNot found!endl。 exit(0)。 } else { int middle=(left+right)/2。 if (a[middle]==key) { return middle。 } else if(keya[middle]) // 這里key是和a[middle]比較，而非middle。 { right=middle1。 return search(a,left,right,key)。 } else { left=middle+1。 return search(a,left,right,key)。 } } }int main(){ int a[100],n,x,left,right,i。 cinn。 for(i=0。in。i++) cina[i]。 left=0。 right=n1。 cinx。 cout這個數(shù)的下標是：search(a,left,right,x)endl。}專題二：分治算法之歸并排序歸并排序是分治算法的一個非常典型的應(yīng)用。歸并排序原理：歸并排序具體工作原理如下（假設(shè)序列共有n個元素）：將序列每相鄰兩個數(shù)字進行歸并操作（merge)，形成floor(n/2)個序列，排序后
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號-1