# Divide Et Impera

765

## 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

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

## 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 , 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

https://github.com/nick11235/Hanoi-VS Participated in the
Teacher Contest