[Précédent]
[Index] | [Enoncé] | [Version imprimable]
[Prochain]

3.9
   Permutations et combinaisons - Corrigé
Niveau 2
  
 
Fichiers:
   CombiPermu.java, CombiPermu2.java    

La façon intuitive de coder ce programme donne une solution ressemblant à celle-ci : 

 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
34
35
36
37
38
 
public class CombiPermu {

    public static void main(String[] args) {
        /* Formule mathématique de la permutation de k
         * élements parmi n: (n!)/(n-k)!
         * Formule mathématique de la combinaison de k
         * élements parmi n: (n!)/(k!*(n-k)!)
         */
        //valeurs à définir
        int n = 10;
        int k = 6;

        int n_factorial = 1;
        int k_factorial = 1;
        int n_minus_k_factorial = 1;

        //calcul des factoriels
        for (int i = 1; i <= n; i++) {
            n_factorial *= i;
        }
        for (int i = 1; i <= k; i++) {
            k_factorial *= i;
        }
        for (int i = 1; i <= (n - k); i++) {
            n_minus_k_factorial *= i;
        }

        //permutations
        System.out.println("Le nombre de permutations de " + k
                    + " elements parmi " + n + " est "
                    + (n_factorial / n_minus_k_factorial));

        //combinaisons
        System.out.println("Le nombre de combinaisons de " + k +
                    " elements parmi " + n + " est "
                    + (n_factorial / (k_factorial*n_minus_k_factorial)));
    }
}

Selon les valeurs de n et k les trois boucles calculant les factorielles font des calculs redondants.

Une version du code essayant d'éviter ces redondances serait : 

 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
public class CombiPermu2 {

    public static void main(String[] args) {
        // valeurs à définir
        int n = 10;
        int k = 6;

        int n_factorial, k_factorial, n_minus_k_factorial;
        n_factorial = 1;
        k_factorial = 1;
        n_minus_k_factorial = 1;

        //calcul amélioré des factoriels
        if (k < (n - k)) {
            for (int i = 1; i <= k; i++) {
                k_factorial *= i;
            }
            n_minus_k_factorial = k_factorial;

            for (int i = k + 1; i <= (n - k); i++){
                n_minus_k_factorial *= i;
            }
            n_factorial = n_minus_k_factorial;
            for (int i = (n - k) + 1; i <= n; i++){
                n_factorial *= i;
            }
        } else {
            for (int i = 1; i <= (n - k); i++){
                n_minus_k_factorial *= i;
            }
            k_factorial = n_minus_k_factorial;

            for (int i = (n - k) + 1; i <= k; i++){
                k_factorial *= i;
            }
            n_factorial = k_factorial;

            for (int i = k + 1; i <= n; i++){
                n_factorial *= i;
            }
        }
    
        //permutations
        System.out.println("Le nombre de permutations de " + k
                    + " élements parmi " + n + " est "
                    + (n_factorial / n_minus_k_factorial));
        
        //combinaisons
        System.out.println("Le nombre de combinaisons de " + k
                    + " élements parmi " + n + " est "
                    + (n_factorial / (k_factorial*n_minus_k_factorial)));
    }
}

 

[Précédent]
[Index] | [Enoncé] | [Version imprimable]
[Prochain]