Introduction: Divide Et Impera
Objectives:
- To know the general routine of the method divide et impera;
- To explain the conditions under which the divid et impera method can be applied;
- To correctly apply the divide et impera method for the proposed problem;
- To correctly establish the continuation conditions for a given application;
- Choosing correctly the values that the solution vector elements can take;
- Establish under what conditions a solution is obtained;
- Use the debug system to detect any syntax errors;
- To solve correctly, through independent activity, the applications proposed for solving
.- To argue the value of the method used in writing programs;
- To correctly identify the problems that require the implementation of the Divide et Impera method;
Material Resources:
Black Board/white board;
chalk/marker
computer running Microsoft Windows 10 on which is installed Visual Studio 2019 Community
video projector
Procedural Resources: conversation, explanation, demonstration, problematization, exercise, discovery learning.
Step 1: Let's Get Started
download project from git link: https://github.com/nick11235/programe-divide-et-im...
or write in git bash the following command: git clone https://github.com/nick11235/programe-divide-et-im...
start visual studio
open project programare divide et impera vs
build and run
make sure that you understand how the algorithm works
you are ready to teach your students about divite et impera
Step 2: Organization of the Lesson Class
Notation of absences. Preparing the students for the lesson
Step 3: Checking the Homework
The theme is checked both quantitatively and qualitatively, correcting any errors;
Step 4: Updating Knowledge
It will be done through the following set of questions and applications:
1. When is the Divide et Impera method used?
A. The divide et impera method is used when the number of iterations required to solve the problem is not known, but the condition of validating the solution and the iteration for the first step is known. By mathematical induction it can be generalized, and at the next step the metote will be called on a half interval.
2. How many solutions does this method offer?
A. The method finds the solution to the problem.
3. In what ways is the Divide et Impera method?
A. There is only one implementation of Divide et Impera methods:- Appeal;
3.What is the routine divide and generalized impira.
int max (int i, int j)
{
int a, b, m;
if (i == j)
return v [i];
else
{
m = (i + j) / 2;
a = max (i, m);
b = max (m + 1, j);
if (a> b) return a;
else return b;
}
}
4. What is the role of the subprogram called by the routine divide et impera?
A. The role of the subprogram is to sum up the range in which the solution is sought.
5. What are the advantages of the method?
- Quickly find the solution
- Offer a solution for a given problem.
6. What is the disadvantage of the method?
- Due to the characteristic recursivity for a large number of iterations, the program stack is loaded.
Step 5: Application Statement
I write the title of the lesson on the board and dictate the statement of the first application. We read a vector with n components, natural numbers. It is required to print the maximum value.
Step 6: Communicating Knowledge and Discussing How to Solve Applications.
The search function will generate the maximum value between the numbers retained in the vector at a position between i and j (initially, i = 1, j = n).
To do this, proceed as follows:
• if i = j, the maximum value will be v [i];
• otherwise, divide the vector into two subvectors - suppose the variant for parallelization on 2 processors. Calculate the middle m of the interval [i, j]: m = (i + j) div 2.
The first subvector will contain the components from i to m, the second will contain the components from (m + 1) to j; the subproblems are solved (thus finding the maximum for each of the subproblems), and the current solution will be given by the maximum value between the results of the two subproblems.
#include
using namespace std;
int v [10], n;
int max (int i, int j)
{
int a, b, m;
if (i == j) return v [i];
else
{
m = (i + j) / 2;
a = max (i, m);
b = max (m + 1, j);
if (a> b) return a;
else return b;
}
}
int main ()
{
cout << "n =" cin >> n;
for (int i = 1; i <= n; i ++)
{
cout << "v [" << i << "] ="; cin >> v [i];
}
cout << "max =" << max (1, n);
return 0;
}
Step 7: Fixing the Knowledge and Carrying Out the Feed-back
In the same style (using divide et impera), solve the problems of the minimum of a vector and binary search.
Bonus the problem of Towers of Hanoi