[Math]Petit problème de math à résoudre en java

**kloss** · 22/12/2005, 17h29

Bonjour à tous,
On m'a soumis ce problème de math : dans une usine, les ouvriers travaillent toute l'année, sauf quand c'est l'anniversaire de l'un d'eux. Combien d'ouvriers faut-il embaucher pour maximiser la production ?
Mathématiquement, je trouve 364 ouvriers. Mais j'avais envie de vérifier ça et comme je me suis mis au java, je me suis dit : vérifions tout cela avec un petit programme java.
Malheureusement le programme indiquait une maximisation pour 365. Je me suis dit, c'est louche. Testons avec des chiffres simples : une année de deux jours, deux ouvriers. Il y a une chance sur deux pour qu'ils aient leur anniversaire le même jour, et qu'ils travaillent donc chacun une journée, et une chance sur deux pour qu'ils ne fassent rien de l'année. Donc l'espérance mathématique du nombre de journées travaillées et de 1. Le programme ci-dessous donne ~ 1,15... (faux résultat, donc). Je ne comprends pas pourquoi.

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
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.Random;
 
class probleme_de_math {
 
    public static void main(String[] args) {
 
        final long ITERATIONS = 100000;  // à réduire si on travaille avec une année de 365 jours
        final int JOURS_ANNEE = 2;       // 365, par exemple                             
        final int MIN_OUVRIERS = 2;      // 300, par exemple 
        final int MAX_OUVRIERS = 2;      // 400, par exemple
        int i, k; long j;                // compteurs                                                               
        // jours_chomes[] prend la valeur 1 quand le jour est chômé et 0 s'il est travaillé
        // Par exemple, jours_chomes[4] = 1 signifie que le 5ème jour de l'année est chômé
        int jours_chomes[] = new int[JOURS_ANNEE];
 
        // Boucle sur les ouvriers...
            for (i = 0; i <= MAX_OUVRIERS - MIN_OUVRIERS; i++) {
            // Cette variable donne l'espérance mathématique du volume total de jours travaillés
            double moy_jours_travailles_tous_ouvriers = 0;
            for (j = 0; j < ITERATIONS; j++) {
               // Initialisation du décompte des jours travaillés / chômés :
               // Pour l'instant pas d'ouvrier, donc pas de chômage ;)
                int jours_travailles_1_ouvrier = JOURS_ANNEE;
                for (k = 0; k < JOURS_ANNEE; k++) {
                    jours_chomes[k] = 0;
                }
                // Chaque ouvrier chôme un jour au hasard
                for (k = 0; k < MIN_OUVRIERS + i; k++) {
                    jours_chomes[new Random().nextInt(JOURS_ANNEE)] = 1;
                }
                // On obtient le nombre de jours travaillés en soustrayant le nombre de jours chômés au nombre de jours dans une année.
                    for (k = 0; k < JOURS_ANNEE; k++) {
                    jours_travailles_1_ouvrier = jours_travailles_1_ouvrier - jours_chomes[k];
                }
                // moy_jours_travailles_tous_ouvriers contient la somme des résultats de chaque itération
                moy_jours_travailles_tous_ouvriers = moy_jours_travailles_tous_ouvriers + jours_travailles_1_ouvrier;
            }
            // Pour obtenir notre espérance mathématique, on divise par le nombre d'itérations et on multiplie par le nombre d'ouvriers.
            moy_jours_travailles_tous_ouvriers = moy_jours_travailles_tous_ouvriers * (MIN_OUVRIERS + i) / ITERATIONS;
            // Affichage du résultat
            System.out.println(MIN_OUVRIERS + i + " ouvriers : " + moy_jours_travailles_tous_ouvriers + " jours oeuvrés");
        }
    }
 
}

Merci d'avance pour vos éclaircissements.
++

**BiM** · 22/12/2005, 17h37

Comme nous l'avons dit précedemment, Java n'est pas trop fait pour les maths

**kloss** · 22/12/2005, 17h42

Ah si Java ne peut pas nourrir ma fainéantise...

Non, sérieux, il doit pouvoir faire ça. Basiquement, comme il s'agit d'un problème de proba, je demande à Java de prendre des valeurs au hasard quelques dizaines de milliers de fois, de les mouliner et de me renvoyer une moyenne...

**BiM** · 22/12/2005, 17h49

Et bien regarde quelques sujets plus bas, quand il s'agissait d'une addition ou d'une multiplication, il faisait des erreurs alors bon...

**kloss** · 22/12/2005, 17h59

Mmm... Ca ne peut pas être ça. Le programme ne fait que des additions et des soustractions, sauf une fois, à la fin. Et l'erreur est de 15% ! Dans le poste que tu cites c'est 1 qui est évalué comme 0.99999999999999999999999999999, ça n'est pas la même marge d'erreur !

**kloss** · 22/12/2005, 20h36

J'ai écrit la même chose en python, ça marche

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
#!/usr/bin/python
# -*- coding: latin-1 -*-
import os, sys
from random import randrange
 
iterations = 100000
jours_annee = int(raw_input("Nombre de jours dans l'année ? : "))
min_ouvriers = int(raw_input("Nombre minimum d'ouvriers ? : "))
max_ouvriers = int(raw_input("Nombre maximum d'ouvriers ? : "))
 
for i in range(max_ouvriers - min_ouvriers + 1) :
    esperance = 0.0
    for j in range(iterations) :
        jours_travail = jours_annee
        jours_chomes = [0] * (jours_annee)
        for k in range(min_ouvriers + i) :
            jours_chomes[randrange(jours_annee)] = 1
        for k in range(jours_annee) :
            jours_travail -= jours_chomes[k]
        esperance += jours_travail
    esperance = esperance * (min_ouvriers + i) / iterations
    print min_ouvriers + i, 'ouvriers:', esperance

C'est pas fait pour moi le java...

++

**BiM** · 23/12/2005, 09h11

Wé mais des addition des soustractions et des multiplications qui se suivent, ca finit par faire beaucoup d'erreurs. Java n'est tout simplement pas fait pour les maths et puis c'est tout lol.

Après tu peux rechercher un package spécialisé dans les maths pour éviter ce genre d'erreur, ça doit probablement exister.

**dr00w** · 23/12/2005, 16h05

Pour toutes les opérations mathématiques avec des valeurs en virgule flottante, il faut faire les calculs et arrondir aux nombre de décimales requis lors de la dernière opération. Java est utilisé dans nombres d'applications scientifiques utilisant les calculs en virgule flottante. Si tu fais une recherche dans Google : "java rounding double" tu vas trouver plusieurs méthodes pour arrondir tes valeurs.

**kloss** · 23/12/2005, 16h50

Salut,
Ok pour les arrondis mais en l'occurence le problème reste le même. J'ai complètement épuré le code, voilà ce qu'il en reste :

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
import java.util.Random;
 
class foo {
 
    public static void main(String[] args) {
 
        final long ITERATIONS = 100000;
        double mean = 0;
 
        for (long i = 0; i < ITERATIONS; i++) {
            if (new Random().nextInt(2) == new Random().nextInt(2)) {mean +=2;}
        }
 
        mean /= ITERATIONS;
        System.out.println(mean);
    }
 
}

Ca me renvoit environ 1,15 au lieu de 1. Si j'arrondis à deux décimales le résultat est toujours faux...

++

**kloss** · 23/12/2005, 16h57

Tiens, ça a l'air d'être la fonction random qui est mal fichue.
Si je remplace :

Code :

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

if (new Random().nextInt(2) == new Random().nextInt(2)) {mean +=2;}

par :

Code :

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

if (new Random().nextInt(2) == 1) {mean +=2;}

Ca me donne bien une moyenne de 1.
J'ai l'impression qu'appeler deux fois de suite cette fonction dans un intervalle court fausse la donne... Si elle génère les nombres à partir de l'horloge du processeur ça peut éventuellement se comprendre...

**beb-mbs** · 23/12/2005, 17h19

slt
ton probleme tel qu'enonce n'accepte pas la virgule tu ne devrais meme pas a avoir a faire de conversions les jour sont des entiers, les "man" sont des entiers a forcer des conversions inutiles dans des calculs ou en plus intervien l'aleatoire ne peut donner que des resultats approximatifs
si le .05 te gene dit toi que tu peut avoir des pertes, un qui meurt par exemple......ou qui demissionne

**aDamas** · 23/12/2005, 17h25

A mon avis t'as qu'a engager des employés qui ont tous leur aniversaire le même jours...

**kloss** · 23/12/2005, 17h35

Envoyé par beb-mbs

a forcer des conversions inutiles dans des calculs ou en plus intervien l'aleatoire ne peut donner que des resultats approximatifs

J'ai mis 'mean' en integer ; maintenant il y a une unique conversion à la fin, et pourtant toujours 15% d'erreur. Moi je trouve ça énorme 15%, c'est pas comme si java me rajoutait une misérable décimale à la fin d'un nombre qui fait une page. Par ailleurs l'erreur est toujours vers le haut (je n'ai jamais 0.85). Quand au côté aléatoire de la chose, il est sacrément diminué par le million d'itérations. Je devrais normalement trouver quelque chose entre, disons, 0.98 et 1.02.

Envoyé par aDamas

A mon avis t'as qu'a engager des employés qui ont tous leur aniversaire le même jours...

C'est ce qu'on appelle du sens pratique...

**beb-mbs** · 23/12/2005, 17h52

Slt.
Pardon, une conversion....

Code :

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

1
2
 
         final long ITERATIONS = 100000;

Code :

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

1
2
 
         double moy_jours_travailles_tous_ouvriers = 0;

Code :

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

1
2
 
         int jours_travailles_1_ouvrier = JOURS_ANNEE;

java est (au -) aussi bon que n'importe quel autre langage pour les maths le tout etant de bien saisir ses rouages

**beb-mbs** · 23/12/2005, 17h55

Juste pour le fun compile et fais tourner

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
34
35
 
import java.util.Random; 
 
class Probleme_De_Comprehention_Resolu { 
 
    public static void main(String[] args) { 
 
        final int ITERATIONS = 100000;  // à réduire si on travaille avec une année de 365 jours 
        final int JOURS_ANNEE = 2;       // 365, par exemple                              
        final int MIN_OUVRIERS = 2;      // 300, par exemple 
        final int MAX_OUVRIERS = 2;      // 400, par exemple 
        int i, k; long j;                // compteurs                                                                
        int jours_chomes[] = new int[JOURS_ANNEE]; 
 
            for (i = 0; i <= MAX_OUVRIERS - MIN_OUVRIERS; i++) { 
            int moy_jours_travailles_tous_ouvriers = 0; 
            for (j = 0; j < ITERATIONS; j++) { 
               int jours_travailles_1_ouvrier = JOURS_ANNEE; 
                for (k = 0; k < JOURS_ANNEE; k++) { 
                    jours_chomes[k] = 0; 
                } 
                for (k = 0; k < MIN_OUVRIERS + i; k++) { 
                    jours_chomes[new Random().nextInt(JOURS_ANNEE)] = 1; 
                } 
                    for (k = 0; k < JOURS_ANNEE; k++) { 
                    jours_travailles_1_ouvrier = jours_travailles_1_ouvrier - jours_chomes[k]; 
                } 
                moy_jours_travailles_tous_ouvriers = moy_jours_travailles_tous_ouvriers + jours_travailles_1_ouvrier; 
            } 
            moy_jours_travailles_tous_ouvriers = moy_jours_travailles_tous_ouvriers * (MIN_OUVRIERS + i) / ITERATIONS; 
            System.out.println(MIN_OUVRIERS + i + " ouvriers : " + moy_jours_travailles_tous_ouvriers + " jours oeuvrés"); 
        } 
    } 
 
}

**kloss** · 23/12/2005, 18h18

Envoyé par beb-mbs

Slt.
Pardon, une conversion....

Je parlais du programme réécrit (qui ne résout plus le problème mais contient encore l'erreur et est plus lisible).

Juste pour le fun compile et fais tourner

Vraiment pour le fun alors, parce qu'en mettant en integer la variable qui renvoie le résultat (ie un nombre avec des décimales, le fameux 1.15), c'est clair qu'il n'y a plus de problème.
Tu as proposé ça sérieusement ?? Ou c'était une plaisanterie ?

**plegat** · 23/12/2005, 19h31

Salut,

C'est ton utilisation de Random qui pose problème... là, tel que tu l'utilises, tu crées un objet à chaque boucle avec le constructeur par défaut... donc la "graine" du générateur est basée sur l'horloge de ta machine, avec une résolution d'une milliseconde... et en une milliseconde, tu as le temps d'en faire des boucles! Donc l'aléatoire n'est plus vraiment assuré!

Pour résoudre le problème, crée un objet Random avant le début de ta boucle, par exemple après la ligne:

Code :

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

int jours_chomes[] = new int[JOURS_ANNEE];

rajoute:

Code :

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

Random generateur=new Random();

Ensuite, remplace:

Code :

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

jours_chomes[new Random().nextInt(JOURS_ANNEE)] = 1;

par:

Code :

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

jours_chomes[generateur.nextInt(JOURS_ANNEE)] = 1;

En utilisant ça, je tombe sur ta valeur de 1.00 (en passant, je ne trouvais pas ton 1.15 avec ton code initial...)

**kloss** · 23/12/2005, 19h45

Oui ça marche ! Merci beaucoup plegat !
Compris pour l'initialisation. Comme tu t'en doutes en voyant les erreurs, je débute

++

[Math]Petit problème de math à résoudre en java

Java

Discussions similaires

Partager

Partager