- 2020-06-03 05:10
*views 4*- C++( Data structure and algorithm )

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

- Java378 articles
- Python197 articles
- Linux110 articles
- MySQL83 articles
- Vue78 articles
- SpringBoot68 articles
- Spring61 articles
- javascript56 articles
- more...

Daily Recommendation

views 4

©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