ALGORITHME II
PRESENTATION DE MINI PROJET
PRESENTE PAR:
BELHAOUS ABDELADIM
EL BIKARI ZINEB
JERAIDI OUMAIMA
LGUERBAHI HAFSA
SALLAMA ABDESSAMAD
ALGORITHME 1
On ce algorithme en peut calculer la somme maximale de la
sequence par calculer la somme de sous sequence comme {Xi},
{Xi,Xi+1},…,{Xi,Xi+1,Xi+2,…,Xn} et prendre le plus grand somme
comme une somme maximal
ALGORITHME 1
L’entrer de
• sequence
•
•
• Determiner les sous sequence
•
•
• {xi} {Xi,Xi+1} {Xi,Xi+1,Xi+2} … {xi,xi+1,…xn}
•
•
•
Calculer la somme maximale de tout sous sequence
Choisissez le plus grand somme
Afficher la somme maximale et sa sous sequence
AGORITHME 1
VARIABLES
max , sub_sequence_si , sub_sequence_len : INTEGER ;
DEBUT
FIN POUR
max <- arr[0]
sub_sequence_si <- 0 FIN POUR
sub_sequence_len <- 1
ECRIRE max
POUR si = 0 A [Link] - 1 ECRIRE sub_sequence_si
ECRIRE sub_sequence_len - 1
POUR len <- 1 A [Link] - si
FIN
sum <- 0
POUR i <- si A si + len - 1
sum <- sum + arr[i]
FIN POUR
SI sum > max
max <- sum
sub_sequence_si <- si
sub_sequence_len <- len
FIN SI
ALGORITHME 1 EN C
#include <stdio.h>
if (sum > max)
int main() {
{ max = sum;
int arr[] = {1, 2, 3, -2, 5}; sub_sequence_si = si;
int max, sub_sequence_si, sub_sequence_len; sub_sequence_len = len;
}
max = arr[0]; }
sub_sequence_si = 0; }
sub_sequence_len = 1;
printf(" %d is the max value \n", max);
for (int si = 0; si < sizeof(arr) / sizeof(arr[0]); si++) printf(" %d is the start index \n", sub_sequence_si);
{ printf(" %d is the end index \n", sub_sequence_len - 1);
for (int len = 1; len < sizeof(arr) / sizeof(arr[0]) - si; len++)
{ return 0;
int sum = 0; }
for (int i = si; i < si + len; i++)
{
sum += arr[i];
}
ALGORITHME 2
Algorithme 2 C'est une autre méthode de trouver la somme maximale mais plus simple que celle du 1er [Link]
parle ici du fait de d'utiliser la somme précédemment obtenue pour calculer une autre somme afin de trouver la Somme
maximale
•
ALGORITHME 2 •
•
x1 x2 x3 x4 x5
X1+x2=S1
S1+X3=S2
S2+x4=s3
S2+x5=s4
AGORITHME 2
VARIABLES
max , sub_sequence_len , sub_sequence_len , prev_sum : INTEGER;
FSI
DEBUT
FINPOUR
max <- arr[0]
FINPOUR
sub_sequence_si <- 0
sub_sequence_len <- 1
ECRIRE max , sub_sequence_si ,
sub_sequence_si + sub_sequence_len - 1
POUR si <- 0 À [Link] - 1 FAIRE
FIN
prev_sum <- 0
POUR len <- 1 À [Link] - si FAIRE
sum <- 0
sum <- prev_sum + arr[si + len - 1]
prev_sum <- sum
SI sum > max ALORS
max <- sum
sub_sequence_si <- si
sub_sequence_len <- len
ALGORITHME 2
si [Link] = 1
alors rss <- getLargestSum(right, right_s)
// instantiate structure css <- getCSS(left, right, left_s, retourner css
data : Donnees right_s) fin fonction
[Link] <- arr[0]
data.start_index <- 0 si [Link] >= [Link] ET [Link] >=
data.end_index <- 0 [Link] VARIABLES
retourner data alors arr : tableau entier
fin si retourner lss res : Donnees
sinon si [Link] >= [Link] ET DEBUT
// get the size of the left and right [Link] >= [Link] arr <- [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
subarrays alors res <- getLargestSum(arr)
left_s <- [Link] / 2 data : Donnees
right_s <- [Link] - left_s [Link] <- [Link] ECRIRE [Link]
data.start_index <- rss.start_index ECRIRE res.start_index
// get the left and right subarrays + left_s ECRIRE res.end_index
left <- [Link](0, left_s) data.end_index <- rss.end_index + FIN
right <- [Link](left_s, [Link]) left_s
retourner data
lss <- getLargestSum(left, left_s)
ALGORITHME 2 EN C
#include <stdio.h> if (sum > max)
{
int main() max = sum;
{ sub_sequence_si = si;
int arr[] = {1, 2, 3, -2, 5}; sub_sequence_len = len;
int max, sub_sequence_si, sub_sequence_len, }
prev_sum; }
}
max = arr[0];
sub_sequence_si = 0; printf(" %d is the max value \n", max);
sub_sequence_len = 1; printf(" %d is the start index \n", sub_sequence_si);
printf(" %d is the end index \n", sub_sequence_si +
for (int si = 0; si < sizeof(arr) / sizeof(arr[0]); si++) sub_sequence_len - 1);
{
prev_sum = 0; return 0;
for (int len = 1; len < sizeof(arr) / sizeof(arr[0]) - }
si; len++)
{
int sum = 0;
sum = prev_sum + arr[si + len - 1];
prev_sum = sum;
ALGORITHME 3
On ce algorithme on diviser la sequence en 3 sous sequence et eon
calcul la somme maximale et prendre le plus grand somme
ALGORITHME 3 L’entrer de
sequence
SCHEMA : Diviser la sequence au 3 sous sequence
Sous sequence 1 Sous sequence 2 Sous sequence 3
Determiner les sous sequence
{xi {Xi,Xi … {xi,xi+1,… {xi {Xi,Xi … {xi,xi+1,… {xi {Xi,Xi … {xi,xi+1,…
} +1} xn} } +1} xn} } +1} xn}
Calculer la somme maximale de tout Calculer la somme maximale de tout Calculer la somme maximale de tout
sous sequence sous sequence sous sequence
Choisissez le plus grand somme Choisissez le plus grand somme Choisissez le plus grand somme
Choisissez le plus grand somme
Afficher la somme maximale et sa sous sequence
ALGORITHME 3
structure Donnees { si sum > l_max alors
max : ENTIER; alors r_max <- sum
start_index : ENTIER; l_max <- sum r_max_start_index <- 0
end_index : ENTIER; l_max_start_index <- i r_max_end_index <- i
} l_max_end_index <- left_s - 1 fin si
fin si fin pour
fonctions getCSS(left : tableau entier, right : fin pour
tableau entier, left_s : ENTIER, right_s : data : Donnees
ENTIER) : Donnees r_max <- right[0] [Link] <- r_max + l_max
début r_max_start_index <- 0 data.start_index <- l_max_start_index
l_max <- left[left_s - 1] r_max_end_index <- 0 data.end_index <- r_max_end_index +
l_max_start_index <- left_s - 1 left_s
l_max_end_index <- left_s - 1 pour i <- 1 à right_s retourner data
faire
prev_sum <- 0 sum <- 0 fin fonction
pour j <- 0 à i
pour i <- left_s - 2 à 0 par -1 faire fonction getLargestSum(arr : tableau entier
faire sum <- sum + right[j] ) : Donnees
sum <- prev_sum + left[i] fin pour début
ALGORITHME 3
arr[1] <- 2;
arr[2] <- 3;
arr[3] <- 4;
arr[4] <- 5;
arr_len <- 5;
lss <- getLargestSum2(arr,arr_len);
ECRIRE([Link]);
ECRIRE(lss.start_index);
ECRIRE(lss.end_index);
FIN
ALGORITHME 3
int main(int argc, char *argv[]) // o(n²)
result r = {r_max + l_max,
{
l_max_start_index, r_max_end_index +
left_s};
algo3();
return r;
}
return 0;
}
void algo3()
{
// get current time
int arr_s = sizeof(arr) / sizeof(arr[0]);
result r = getLargestSum(arr, arr_s);
printf("Max: %d from index %d to %d \n",
[Link], r.start_index, r.end_index);
}
ALGORITHME 4
Après avoir résolu les trois algorithmes précédents, nous
avons obtenu une somme totale. Dans cet algorithme,
nous allons comparer chaque valeur avec cette somme, et
à la fin, la valeur égale reste.
Max : 11 | SI : 2 & EI : 3
ALGORITHME 4
x1 x2 x3 x4 x5 x6
getLargestSum Max : 11
SI : 2 & EI : 3
Is the len = 1
x1 x2 x3 x4 x5
getLargestSum
Is the len = 1
Max : arr[0] = 1
… SI : 0 & EI : 0
x1
getLargestSum
Is the len = 1
ALGORITHME 4
structure Donnees { // get the largest sum of the new [Link] <- sum;
max : ENTIER; array lss.start_index <-
start_index : ENTIER; lss <- getLargestSum2(arr,arr_len - arr_len - 1 - s;
end_index : ENTIER; 1); lss.end_index <- arr_len
} - 1;
// calculate the sum of elements in FINSI
fonction getLargestSum2(arr : ENTIER[], the array starting from the last FINPOUR
arr_len : ENTIER) : Donnees element
DEBUT POUR s <- 1 A arr_len - 1 - retourner lss;
SI (arr_len == 1) ALORS lss.start_index + 1 FAIRE
max <- arr[0]; // sum FINFONCTION
start_index <- 0; sum <- 0;
end_index <- 0; POUR i <- arr_len - 1 A arr_len - 1 // test
retourner {max, start_index, end_index}; - s - 1 PAR -1 FAIRE VARIABLES
FINSI sum <- sum + arr[i]; arr : ENTIER[5];
FINPOUR arr_len : ENTIER;
// create a new array without the last lss : Donnees;
element // compare the last max value DEBUT
// let arr2 = [Link](0, arr_len - 1); with sum of the current sub-sequence
SI (sum > [Link]) ALORS arr[0] <- 1;
ALGORITHME 4
DEBUT
arr[0] <- 1;
arr[1] <- 2;
arr[2] <- 3;
arr[3] <- 4;
arr[4] <- 5;
arr_len <- 5;
lss <- getLargestSum2(arr,arr_len);
ECRIRE([Link]);
ECRIRE(lss.start_index);
ECRIRE(lss.end_index);
FIN
for (int s = 0; s < a_s; s++) // o(n)
int max = a[a_s - 1]; {
ALGORITHME 4 int maxStart = a_s - 1; int sum = 0;
for (int j = a_s - 1; j >= a_s - 1 - s;
int maxEnd = a_s - 1;
for (int s = 0; s < a_s; s++) // o(n) j--) // o(n)
{ {
int sum = 0; sum += a[j];
} for (int j = a_s - 1; j >= a_s - 1 - s; }
return r; j--) // o(n) if (sum > max)
result r = {a[0], 0, 0}; { {
{ sum += a[j]; max = sum;
if (a_s == 1) } maxStart = a_s - 1 - s;
if (sum > max) maxEnd = a_s - 1;
* n ) = o(n³) { }
result getLargestSum2(int a[], int a_s){ // o(n² max = sum; }
maxStart = a_s - 1 - s;
} result; maxEnd = a_s - 1; // remove the last element from
int end_index; } the array
int start_index; } int last = a[a_s - 1];
int max; a_s--;
{ // remove the last element from the
typedef struct array
int last = a[a_s - 1];
23, 84}; a_s--;
ALGORITHME 4
// previous max subarray sum
result prevMax = getLargestSum2(a,
a_s); // o(n)
if ([Link] > max) int main(int argc, char *argv[])
{ {
return prevMax;
} algo4();
result r = {max, maxStart, maxEnd}; return 0;
return r; }
}
void algo4(){
int arr_s = sizeof(arr) / sizeof(arr[0]);
result r = getLargestSum2(arr, arr_s);
printf("Max: %d from index %d to %d \
n", [Link], r.start_index, r.end_index);
THANK YOU!
