Discussion :

[toulouseadr]

Bonjour à tous,

je suis tombé sur un algo pas très compliqué, mais j'ai du mal à comprendre l'explication de fréquence, voici l'ago:

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
 
public static int count(int[] a) {
        int n = a.length;
        int count = 0;
        for (int i = 0; i < n; i++) {
1]           for (int j = i+1; j < n; j++) {
2]              for (int k = j+1; k < n; k++) {
3]                   if (a[i] + a[j] + a[k] == 0) {
                        count++;
                    }
                }
            }
        }
        return count;
    }

et ils expliquent que les fréquences de calcul pour les 1], 2], 3] ème lignes sont:
1] N
2] N^2 / 2 - N/2
3] N^3/6 - N^2/2 + N/3


Je me demande pourquoi N^2 est divisé par 2, le N^3 par 6 et N par 3
Ensuite pourquoi c'est N^3/6 - N^2/2 et pas N^3/6 + N^2/2 alors que c'est +N/3 ?


Merci beaucoup :-)

Adrien

[tbc92]

On va regarder le comptage qui donne N²/2-N/2

En fait, ce n'est pas vraiment une question d'algorithme, mais une question de maths.

Recherche 'Somme des n premiers entiers', et tu tomberas assez vite sur la formule S(n) = n(n+1)/2. Dans notre exercice, on ne calcule pas tout à fait la somme des n premiers entiers, mais la somme des n-1 premiers entiers. Ce qui donne (n-1)n/2, ou encore n²/2-n/2.

Et comment on tombe sur cette somme des n-1 premiers entiers ?
Quand i vaut 0, j prend toutes les valeurs entre 1 et n-1, donc n-1 valeurs possibbles.
Puis i vaut 1, j a alors n-2 valeurs possibles,
Et ainsi de suite.
Le nombre de passages dans cette boucle est donc (n-1)+(n-2)+ ... +2+1 : somme des n-1 premiers entiers.

Pour le second calcul, c'est un peu plus compliqué.

[Flodelarab]

Bonjour

Tu utilises 3 fois le mot "fréquence", mais je ne comprends pas ce que c'est. À mon avis, le terme est impropre.
De la même façon, j'imagine que le grand N de ton texte est le petit n de ton code.
Et la variable count n'a rien à voir avec la fonction count. Joyeuses Pâques à tous.



Lorsque je lis le code, je vois un tableau d'entiers "a" et on tire 3 indices parmi N, pour faire la somme des valeurs du tableau à ces indices, indépendamment de l'ordre et sans répétition : c'est donc une combinaison.


Le reste, ce sont des simplifications.

Libre à toi de calculer les étapes intermédiaires en tirant 1 parmi N, et 2 parmi N.