One , The thought of divide and rule

* The method of divide and rule is very similar to the modular method of software design
* Divide and rule is usually not used for small examples of problem solving , To solve a problem . The general steps are :
* ① Divide a large instance into two or more smaller instances
* ② Solve each small instance separately
* ③ Combine the solutions of these small instances into the solutions of the original large instances
Two , Practical application of finding counterfeit currency

Problem description

* One bag has 16 Coins , Only one of them is counterfeit , This counterfeit coin is lighter than other real coins ( All the other real coins are the same weight ), Now we need to find out the counterfeit currency
Common solutions

* The general method is to compare one by one , Once you meet the lighter ones, you'll find the counterfeit ones
* The steps are :
* ① Compare coins 1 And coins 2, If a coin is lighter , So this light coin is a counterfeit , End search ; Otherwise proceed to the next step
* ② Continue to compare coins 2 And coins 3, If a coin is lighter , So this light coin is a counterfeit , End search ; Otherwise proceed to the next step
* ...... and so on , Until the counterfeit money is found, terminate the search
The solution of divide and rule

* The idea of divide and rule is to decompose a large instance of a problem into two or more small instances , And then compare them
* Here we decompose the large instance into two small ones , The steps are :
* ① hold 16 Coins are divided into two groups A and B, Each group 8 Coins , Calculate and compare the total mass of each group of coins , The lighter group must have counterfeit money
* ② Continue to group the lighter group , Divided into A and B, Each group 4 Coins , Then calculate and compare the total mass of each group of coins , Homology , The lighter group must have counterfeit money
* ③ Continue to group the lighter group , Divided into A and B, Each group 2 Coins , Then calculate and compare the total mass of each group of coins , Homology , The lighter group must have counterfeit money
* ④ There are only two coins left , So there's no need to group anymore , Direct comparison , The lighter coin must be counterfeit
Three , The gold block problem of practical application

Problem description

* A boss has a bag of gold , The weight of each piece of gold is different , Now I want to find out the heaviest and lightest piece of gold
Common solutions

* The common solution is to compare one by one , Find the heaviest and lightest Nuggets
* The steps are generally :
* Suppose the total number of gold bullion is n
* Compare each gold piece one by one , Find the heaviest nugget
* After finding the heaviest Nuggets , From the rest n-1 Find the lightest nugget among the Nuggets
* Number of comparisons : Because the number of times to find the heaviest Nuggets is n-1 second , Find the lightest nugget out of the rest n-2 second , So the total number of comparisons is 2n-3
template<typename T> bool find_max_min(T arr[], int n,int &maxIndex,int
&minIndex) { if (n <= 0) return false; // Find the biggest maxIndex = 0; for (int i = 1; i
< n; ++i) { if (arr[maxIndex] < arr[i]) maxIndex = i; } // And find the smallest of the rest minIndex
= 0; for (int j = 1; j < n; j++) { if (j == maxIndex) continue; if
(arr[minIndex] > arr[j]) minIndex = j; } return true; } int main() { int arr[]
= { 1,4,2,5,1,8,5 }; int maxIndex, minIndex; if (find_max_min(arr, sizeof(arr)
/ sizeof(int), maxIndex, minIndex)) { std::cout << "max:" << arr[maxIndex] <<
endl; std::cout << "min:" << arr[minIndex] << endl; } return 0; }

The solution of divide and rule

* When n<=2 Time , One comparison is enough
* When n>2 Time , The overall steps are as follows :
* ① Divide gold into A and B Two parts
* ② Find out A and B The heaviest and lightest , set up A The heaviest and lightest gold pieces are Ha and La,A The heaviest and lightest gold pieces are Hb and Lb( This step can be realized by recursion )
* ③ compare Ha And Hb You can find the heaviest , compare La And Lb You can find the lightest
* Demo case :
* ① hypothesis n=8, Yes 8 Nugget
* ② take 8 The Nuggets are divided into two parts A and B, Each has its own 4 Nuggets of gold
* ③ because A Among them 4 Nuggets of gold , We divide it into two parts A1 and A2, Each part has 2 Nuggets of gold
* And then we can find out through a comparison A1 Medium to heavy Nuggets Ha1 and La1
* One more comparison will find out A2 Medium light gold Ha2 and La2
* And then through a comparison Ha1 And Ha2 find A The heaviest piece of gold Ha, Through a comparison La1 And La2 find A The lightest piece of gold La
* ④ because B Among them 4 Nuggets of gold , We divide it into two parts B1 and B2, Each part has 2 Nuggets of gold
* And then we can find out through a comparison B1 Medium to heavy Nuggets Hb1 and Lb1
* One more comparison will find out B2 Medium light gold Hb2 and Lb2
* And then through a comparison Hb1 And Hb2 find A The heaviest piece of gold Hb, Through a comparison Lb1 And Lb2 find A The lightest piece of gold Lb
* ⑤ Last comparison Ha and Hb Find the heaviest nugget , Another comparison La and Lb Find the lightest nugget . End of step
* We can see that in the above divide and rule, we need to compare 10 second

* set up c(n) For the number of comparisons required . for convenience , hypothesis n yes 2 Power of :
* If divide and rule : When n=2 Time ,c(n)=1; For larger n,c(n)=2c(n/2)+2
* If it is a case by case comparison method :c(n)=3n/2-2
* therefore , Using divide and conquer method is less than comparing one by one method 25% Comparison times of
Code implementation of divide and rule

* If recursion is used , The steps are as follows :
* ① In the binary tree above , Along the path from root to leaf , Divide a large instance into several sizes as 1 or 2 Small examples of
* ② At each size 2 In the , Compare and determine which is heavier and which is lighter . At node D,E,F,G Complete this comparison . Size is 1 There's only one nugget , It's the lightest and heaviest
* ③ Compare the lighter nuggets to determine which is the lightest , Compare the heavier nuggets to determine the heaviest . To node A,B,C Perform this comparison
* If you use a non recursive method , The code is as follows :
* Complexity analysis :
When n When even , stay for Another comparison outside the loop , Internal 3(n/2-1) Secondary comparison . The total number of comparisons is 3n/2. When n When it is odd , stay for No comparison outside the loop , Internal n(n-1)/2 Secondary comparison . therefore , whether n Odd or even , When n>0 Time , The total number of comparisons is [3n/2]-2. This is in the earliest algorithm of maximum and minimum , Algorithm with the least number of comparisons
template<typename T> bool find_max_min(T arr[], int n,int &maxIndex,int
&minIndex) { // If the array size is less than or equal to 0, immediate withdrawal if (n <= 0) return false;
// If there's only one nugget , So it's the heaviest and the lightest if (n == 1) { maxIndex = minIndex = 0; return true; }
// If the number of nuggets is greater than or equal to 2, Start the following section int s = 0;// Used to identify the starting point of the comparison if (n % 2 == 1) {
// If the number of nuggets is odd , Set the maximum index and the minimum index as 0, And then from s=1 Start comparison at index maxIndex = minIndex = 0; s = 1; }
else { // If the number of nuggets is even , Extract the index of smaller and larger elements from the first two elements , And then from s=2 Start comparison at index if (arr[0] > arr[1]) {
maxIndex = 0; minIndex = 1; } else { maxIndex = 1; minIndex = 0; } s = 2; }
// from s Start comparison , Compare every two elements for (int index = s; index < n; index += 2) { if
(arr[index] > arr[index +1]) { if (arr[index] > arr[maxIndex]) maxIndex =
index; if (arr[index + 1] < arr[minIndex]) minIndex = index + 1; } else { if
(arr[index] < arr[minIndex]) minIndex = index; if (arr[index + 1] >
arr[maxIndex]) maxIndex = index + 1; } } return true; } int main() { int arr[]
= { 1,4,2,5,0,1,8,3,8 }; int maxIndex, minIndex; if (find_max_min(arr,
sizeof(arr) / sizeof(int), maxIndex, minIndex)) { std::cout << "max:" <<
arr[maxIndex] << endl; std::cout << "min:" << arr[minIndex] << endl; } return
0; }
Four , Matrix multiplication in practical application

* To be continued

Technology
©2019-2020 Toolsou All rights reserved,
QCustomPlot series (5)- Real time dynamic curve python To solve the problem of dictionary writing list in GDOI2019 travels Java Basics ( Bubble sort )Unity Scene loading asynchronously ( Implementation of loading interface )" Cephalosporin wine Say go and go "? DANGER ! Don't drink alcohol when taking these drugs 2021 year 1 Monthly programmer salary statistics , average 14915 element Huawei certification HCIA-AI artificial intelligence java Simple lottery algorithm , luck draw DemoNOI2019 travels