当前位置:网站首页>Ideas and examples of divide and conquer
Ideas and examples of divide and conquer
2022-06-25 01:16:00 【Lutrra】
Divide and conquer method
Quick sort
decompose a[s…t] Decompose into a[s…i-1] and a[i+1…t], among i Is the basis of division
Solving subproblems : If the length of the subsequence is 0 Or for 1, Then he is orderly , Go straight back to ; Otherwise, each subproblem is solved recursively .
Merge : Because the whole sequence is stored in an array a in , The sorting process is in place , The merge step does not require any action .
example :
int Partition(int a[],int s,int t){ // Partition algorithm int i=s,j=t; int tmp=a[s]; // Use the first record of the sequence as the benchmark while(i!=j){ // Scan alternately from both ends of the sequence to the middle , until i=j until while(j>i&&a[j]>=tmp) j--; // Scan from right to left for keywords less than tmp Of a[j] a[i]=a[j]; // take a[j] Migrate to a[i] Location while(i<j&&a[i]<=tmp) i++; // From left to right , The first keyword found is greater than tmp Of a[i] a[j]=a[i]; // take a[i] Move back to a[j] The location of } a[i]=tmp; return i; } /*{2,5,1,7,10,6,9,4,3,8} With 2 Cardinal number Two pointers : Left sub needle left, Right sub needle right Search from right to left for numbers less than cardinality , Search from left to right for the number whose prime is greater than the benchmark a[i]=a[j]; // take a[j] Migrate to a[i] Location a[j]=a[i]; // take a[i] Move back to a[j] The location of 1<2 i=0,j=2 1,5,1,7,10,6,9,4,3,8 And then from left,5>2,j=3,i=1 1,5,5,7,10,6,9,4,3,8 Loop search i=1,j=3 There is no less than cardinal number in the rear 2 The number of will i=1 Set as 2 1,2,5,7,10,6,9,4,3,8 perform QuikSort(a,s,i-1) i The left side of the does not change i To the right of 5 Benchmarking perform QuickSort(a,i+1,t);// */ void QuikSort(int a[],int s,int t){ if(s<t){ int i=Partition(a,s,t); QuikSort(a,s,i-1);// Recursively sort the left subsequence QuickSort(a,i+1,t);// Recursive sorting of right subsequences } }Seek before k individual
void QuickSort(T a[],int s,int t,int k){ int i; if(s<t){ i=Partition(a,s,t); if(k<i+1) QuickSort(a,s,i-1,k); else if(k>i+1) QuickSort(A,i+1,k) } } T solve(T a[],int n,int k){ QuickSort(a,0,n-1,k); for(int i=0;i<k;i++) printf("%d",a[i]); printf("\n"); }
Merge sort
take a[0…n-1] as n A length of 1 The order sheet , Will be adjacent to k(k>=2) An ordered list is merged in pairs , obtain k/n A length of k The ordered sub table of ; Then we continue to merge the western Zhejiang ordered subsequences , obtain n/k Ordered sub table of the square of , It goes on and on , Finally, we get a length of n The order sheet ,k by 2 It is a two-way merge sort
example :
2,5,1,7,10,6,9,4,3,8 2,5 1,7 10,6 9,4 3,8 1,2,5,7 4,6,9,10 3,8 1,2,4,5,6,7,9,10 3,8 1,2,3,4,5,6,7,8,9,10The divide and conquer strategy is as follows :
- loop log2 n,length Take... In turn 1、2、4、.... Each time, execute the following
- decompose : Decompose the original sequence into length Some subsequences of length
- Merge : Call two adjacent subsequences Merge Algorithm sorting produces an ordered subsequence
Algorithm design :
- Bottom up
void Merge(int a[],int low ,int mid ,int high) { int *tmpa; int i=low,j=mid+1,k=0; tmpa=(int *)malloc((hight-low+1)*sizeof(int)); while(i<=mid&&j<=high) { if(a[i]<=a[j])// Put the elements in the first child table into tmpa { tmpa[k]=a[i]; i++; k++; } else { tmpa[k]=a[j];// Put the elements in the second sub table into tmpa j++; k++; } } while(i<=mid)// Copy the rest of the first sub table to tmpa { tmpa[k]=a[i];i++;k++} while(j<=high)// Copy the rest of the second sub table to tmpa { tmpa[k]=a[j];j++;k++} for(k=0;i=low;i<=high;k++,i++)// take tmpa Copy back a in a[i]=tmpa[k]; free(tmpa);// Release tmpa Occupied memory space } void MergePass(int a[],int length,int n) { int i; for(int i=0;i+2*length-1<n;i=i+2*length)// Merger length Long two-phase adjacent sub table Merge(a,i,i+length-1,i+2*length-1); if(i+length-1<n) // The remaining two sub tables , The latter is less than length Merge(a,i,i+length-1,n-1);// Merge these two sub tables } void MergeSort(int a[],int n) { int length; for(length=1;length<n;length=2*lenth) MergePass(a,length,n); }- The top-down
/*2,5,1,7,10,6,9,4,3,8 2,5,1,7,10 6,9,4,3,8 2,5,1 7,10 6,9,4 3,8 2,5 1 7,10 6,9 4 3 8 2 5 7 10 6 9 2,5 6,9 1,2,5 4,6,9 1,2,5,7,10 3,4,6,8,9 1,2,3,4,5,6,7,8,9 */ void MergeSort(int a[],int low,int high) { int mid; if(low<high)// A subsequence has two or more elements { mid=(low+high)/2;// Take the middle position MergeSort(a,low,mid);// Yes a[low..mid] Subsequence sorting MergeSort(a,mid+1,high);// Yes a[mid+1...high] Subsequence sorting Merge(a,low,mid,high);// Merge two subsequences , See the previous algorithm } }Find the maximum and the second largest
decompose : Press the middle position mid=(low+high)/2 Divided into a[low…mid] and a[mid+1…high] Left and right intervals ( Note that the left section contains a[mid])
Solve the decomposition subproblem : Find the maximum value of the left interval lmax1 And the second largest value lmax2, Find the maximum value of the right interval rmax1 And the second largest value rmax2
Merge : if lmax1>rmax1, be max1=lmax1,max2=MAX{lmax2,rmax1}m otherwise max1=rmax1,max2={
lmax1,rmax2}
#include<algorithm> #include<iostream> #include<stdio.h> using namespace std; #define INF 600000; // stay vs6 in max want _cpp_max void solve(int a[],int low,int high,int &max1,int &max2) { if(low==high) // There is only one element in the interval { max1=a[low]; max2=-INF; } else if(low==high-1) // The interval has only two elements { max1=_cpp_max(a[low],a[high]); max2=_cpp_min(a[low],a[high]); } else { int mid=(low+high)/2;// An interval has more than two elements int lmax1,lmax2; solve(a,low,mid,lmax1,lmax2);// Left interval lmax1 and lmax2 int rmax1,rmax2; solve(a,mid+1,high,rmax1,rmax2);// Find the right interval rmax1 and rmax2 if(lmax1>rmax1) { max1=lmax1; max2=_cpp_max(lmax2,rmax1);//lmax2,rmax1 Find the next largest element in } else { max1=rmax1; max2=_cpp_max(lmax1,rmax2); //lmax1、rmax Find the next largest element in } } }Binary search


边栏推荐
- Scala classes inherit multiple attributes
- ContentResolver,拿到手机短信内容
- 对技术的乐观,正让戴尔取得比想象中更多的成就
- Library management system code source code (php+css+js+mysql) complete code source code
- 网上开户选哪个证券公司?网上开户安全么?
- Bi-sql like
- Bi-sql create
- Activity lifecycle
- I'd like to ask how to open an account at industrial securities? Is it safe to open a stock account through the link
- 程序员:是花光积蓄在深圳买房?还是回到长沙过“富余”生活?
猜你喜欢

Library management system code source code (php+css+js+mysql) complete code source code

Bi-sql top

天书夜读笔记——内存分页机制

Deep learning LSTM model for stock analysis and prediction

Text editor of QT project practice ---------- episode 11

108 pages (40000 words) proposal for future apartment intelligent design platform project (version 2022)

重磅:国产IDE发布,由阿里研发,完全开源!(高性能+高定制性)

Bi-sql Union

汇编语言(2)基础知识-debug

Cobalt strike installation tutorial
随机推荐
新手看过来,带你一次性了解“软考”
Première application de l'informatique quantique à la modélisation des flux de puissance dans les systèmes énergétiques à l'Université technique danoise
Syntax highlighting of rich text
卷积与反卷积关系超详细说明及推导(反卷积又称转置卷积、分数步长卷积)
If the order has not been paid for 30 minutes, it will be automatically cancelled. How can I achieve this?
Contentresolver, get the SMS content
MySQL common basic statements (collation)
丹麥技術大學首創將量子計算應用於能源系統潮流建模
2022 simulated 100 questions of safety officer-c certificate examination and online simulated examination
Add information on the left and add parts on the right of the status bar
“一个优秀程序员可抵五个普通程序员!”
LLVM TargetPassConfig
丹麦技术大学首创将量子计算应用于能源系统潮流建模
Yasea APK Download Image
Scala template method pattern
Bi SQL constraints
Start service 11111
腾讯云WeCity解决方案
15.线程同步的几种方法
天书夜读笔记——深入虚函数virtual