Discussion :

[ellgafsi]

Salut,

j ai ecris ce programme qu on donne une liste de N nombres entiers et un entier K. Le programme trouve la somme la plus grande d une suite K élements consécutifs.

exemple:

en entrée ...
6
3
12
42
33
8
22
54

en sortie ...
87

car on obtient 87 en additionnant 12, 42 et 33.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>
 
 
 
 
int main()
{
    int nombreElements;
    int valeurSuiteElements;
    scanf("%d%d", &nombreElements, &valeurSuiteElements);
    int valeurEntree;
    int max = 0;
    int TabValeursEntree[10000];
    int tabSomme[10000];
    int i;
    for (i = 0; i < nombreElements; i++)
    {
        scanf("%d", &valeurEntree);
        TabValeursEntree[i] = valeurEntree;
    }
    int j, k;
    for (j = 0; j < nombreElements-valeurSuiteElements+1; j++)
    {
        for (k = j; k < j+valeurSuiteElements; k++)
        {
            tabSomme[j] += TabValeursEntree[k];
        }
        if (tabSomme[j] > max)
            max = tabSomme[j];
    }
    printf("%d", max);
    return 0;
}

Pouvez vous m aider a calculer la complexitée de mon algo.
Ce que sais qu une affection simple coute un temps constant c.
mais j arrives pas a calculer la complexitée de mes boucles surtout les 2 boucles imbriquées.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 for (j = 0; j < nombreElements-valeurSuiteElements+1; j++)
    {
        for (k = j; k < j+valeurSuiteElements; k++)
        {
            tabSomme[j] += TabValeursEntree[k];
        }
        if (tabSomme[j] > max)
            max = tabSomme[j];
    }

Et donner moi votre avis sur mon algo svp.
Merci!

[Biribibi]

Bonjour.
Il y a N - K itérations de la première boucle et pour chaque itération, il y a K itérations de la seconde boucle.
La complexité de ton programme est donc en O( K (N - K) ) = 0 (N K).

Tu peux obtenir un algorithme en O(N) en optimisant un peu mais je n'ai pas le temps de détailler aujourd'hui.

edit: je ne vois nul part où tu initialises ton tableau tabSomme, tu es sûr que ton programme fonctionne ?

[ellgafsi]

Merci Biribibi!

Tu peux obtenir un algorithme en O(N) en optimisant un peu mais je n'ai pas le temps de détailler aujourd'hui.

-----> Merci pour l indication et je serais tres reconnaissant si, lorsque tu as un peu du temps, a m éclairer comment je peux l optimiser.

je ne vois nul part où tu initialises ton tableau tabSomme, tu es sûr que ton programme fonctionne ?

-----> Oui t as raison j ai pas initialié ni TabValeursEntree[10000] ni tabSomme[10000], mais ca marche j ai lui est compilé sur code::blocks et il marche.

Encore merci et bonne journée!

[Biribibi]

Bon le principe de l'algo, c'est que si on a calculé la somme du sous tableau de tab[i] à tab[i+k-1] (quand notera A) alors la somme du sous tableau de tab[i+1] à tab[i+k] est égale à A - tab[i] + tab[i+k].
On peut donc passer de l'un à l'autre en temps constant.

Ca donne un truc du genre (j'ai écrit l'algo en question dans une fonction pour le séparer de ce qui concerne les entrées/sorties):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
int somme(int [] tab, int len, int k) {
   int tabSomme = 0;
   int i = 0;
   int max = 0;
 
   for (i = 0; i < k; i++) {
        tabSomme += tab[i];
   }
   max = tabSomme;
 
   for (i = k; i < nombreElements; i++) {
          tabSomme = tabSomme + tab[i] - tab[i-k];
          if (tabSomme > max) {
                     max = tabSomme;
          }
    }
    return max;
}

-----> Oui t as raison j ai pas initialié ni TabValeursEntree[10000] ni tabSomme[10000], mais ca marche j ai lui est compilé sur code::blocks et il marche.

Alors, il y a vraiment un principe à ne pas appliquer, c'est "ça marche donc ce que j'ai programmé est juste".
Dans ce cas présent, si tu n'initialises pas ton tableau, il est possible que ça marche quand même en fonction du compilateur que tu utilises (ainsi que d'autres paramètres) mais ça ne marchera peut-être pas si tu changes de compilateur (voir si tu changes juste quelque chose dans ton programme).
C'est juste un coup de chance.
Donc ne pas initialiser tes variables n'est pas du tout conseiller si tu veux avoir un programme un tant soit peu portable.

[ellgafsi]

Salut Biribibi,

Merci pour ces explications!

Alors, il y a vraiment un principe à ne pas appliquer, c'est "ça marche donc ce que j'ai programmé est juste".
Dans ce cas présent, si tu n'initialises pas ton tableau, il est possible que ça marche quand même en fonction du compilateur que tu utilises (ainsi que d'autres paramètres) mais ça ne marchera peut-être pas si tu changes de compilateur (voir si tu changes juste quelque chose dans ton programme).
C'est juste un coup de chance.
Donc ne pas initialiser tes variables n'est pas du tout conseiller si tu veux avoir un programme un tant soit peu portable.

-----> T as totalement raison. Je vais prendre ton conseil la prochaine fois en compte. Merci!