IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Langage Java Discussion :

Problème mathématique avec les nombres


Sujet :

Langage Java

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre averti
    Inscrit en
    Janvier 2007
    Messages
    17
    Détails du profil
    Informations forums :
    Inscription : Janvier 2007
    Messages : 17
    Par défaut Problème mathématique avec les nombres
    bonjour a vous tous. J'essaye de develloper une application JAVA qui fera ce qui suit :

    1-Demander a l'usager de rentrer un nombre entier
    2-Determiner si le nombre est divisible (C'est a dire qu'on peut le diviser par lui même et par 1 seulement)
    3- Si le nombre n'est pas divisible c'est a dire si c'est un nombre composé qui peut être divisé par plusieurs facteurs il faut calculer les facteurs.

    Par exemple : 53 est un nombre divisible

    Par exemple : 18 est un nombre composé qui a les facteurs suivants :
    1 18
    2 9
    3 6

    Avez-vous des idées pour développer cette application????

    Merci de votre aide

  2. #2
    Membre éprouvé
    Avatar de mavina
    Homme Profil pro
    Développeur Java
    Inscrit en
    Octobre 2004
    Messages
    1 812
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : Chine

    Informations professionnelles :
    Activité : Développeur Java
    Secteur : Conseil

    Informations forums :
    Inscription : Octobre 2004
    Messages : 1 812
    Par défaut
    Bonjour,

    En gros, ce que tu souhaites, c'est savoir si un nombre N est premier ou pas.
    Un algorithme naïf serait de vérifier tous les diviseurs de 2 à N-1, mais ce serait beaucoup trop long. Mes souvenirs de terminale me disent que de 1 à racine(n) est suffisant. Enfin, on peut élaguer l'algorithme apres avoir vérifié par 2, on arrette les multiples de deux, par 3 les multiples de 3, par 5 les ...
    On a déja bien élagué avec juste ces 3 nombres

    Voilà, à toi de jouer

    Cordialement

    Fred

  3. #3
    Membre averti
    Inscrit en
    Janvier 2007
    Messages
    17
    Détails du profil
    Informations forums :
    Inscription : Janvier 2007
    Messages : 17
    Par défaut Ce n'est pas évident
    Merci pour ta réponse. Mais ce n'est pas évident. Ce qui me rend la vie difficile c'est comment commencer cet algorithme????. C'est le début qui est dûr. Je continue a faire de la recherche dans des livres JAVA et sur internet. Mais pour le moment je n'ai pas toujours la réponse.

    Toute aide est fortement apprécié. merci

  4. #4
    Membre émérite
    Inscrit en
    Janvier 2005
    Messages
    711
    Détails du profil
    Informations forums :
    Inscription : Janvier 2005
    Messages : 711
    Par défaut
    la factorisation des nombres est un domaine extremement vaste, et il existe des dizaine d'algorithme d'efficacité et de difficultés differentes. la solution que te donne mavina est simple sans etre naive et elle est a priori le meilleur compromis si tes nombres ne depassent pas une dizaine de chiffres. je ne vois donc pas pourquoi tu affirmes ne pas avoir de reponses on peut difficilement faire plus simple a implementer....

  5. #5
    Membre averti
    Inscrit en
    Janvier 2007
    Messages
    17
    Détails du profil
    Informations forums :
    Inscription : Janvier 2007
    Messages : 17
    Par défaut pas évi dent
    Salut les amis. J'aimerais vous rappeler que je suis débutant. Des choses qui pourront vous paraître faciles me prennent énormément de temps. Cet algorithme pour vous il est simple mais pour moi c'est u vrai casse tête.
    J'essaye toujours sans résultat........A suivre

  6. #6
    Membre émérite
    Inscrit en
    Janvier 2005
    Messages
    711
    Détails du profil
    Informations forums :
    Inscription : Janvier 2005
    Messages : 711
    Par défaut
    d'abord, tu n'a pas precisé que tu etais debutant... ensuite, debutant en quoi ? est l'algorithme qui te pose probleme ? ou le fait de le passer en java ? as tu compris "sur le papier" la methode de mavina ?

  7. #7
    Membre éprouvé
    Avatar de mavina
    Homme Profil pro
    Développeur Java
    Inscrit en
    Octobre 2004
    Messages
    1 812
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : Chine

    Informations professionnelles :
    Activité : Développeur Java
    Secteur : Conseil

    Informations forums :
    Inscription : Octobre 2004
    Messages : 1 812
    Par défaut
    Salut,

    Après tests sur mon centrino 1.7ghz, voici les resultats :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
     
    N               Temps mis en MilliSecondes
    1                 0.0
    10               0.0
    100              0.0
    1000            0.0
    10000           0.0
    100000          0.0
    1000000        47.0
    10000000      156.0
    100000000     1375.0
    1000000000   13953.0
    1410065408   20172.0
    Je trouve ca acceptable comme compléxité

    Cordialement

    Fred

  8. #8
    Membre émérite
    Inscrit en
    Janvier 2005
    Messages
    711
    Détails du profil
    Informations forums :
    Inscription : Janvier 2005
    Messages : 711
    Par défaut
    attention, la complexité ne depend pas seulement de la taille du nombre mais aussi, voire surtout dans certain cas, de la taille des facteurs. tout tes exemples sont des nombres paire, donc deja ca coupe pas mal, d'autant que le dernier est meme divisible 10 fois par 2 :-) donc meme avec l'algorithme naif ca fait tout au plus une vingtaine d'operation ! mais en effet, je doute que ramirami aie a factoriser des nombres gigantesques ! donc ca restera raisonnable dans tous les cas, meme en poussant au max de la capacite de base du langage.. par curiosité, essaie avec 3207711361.

    [edit]
    en fait, je me demandais meme pourquoi c'etait aussi long.. le fait est que ton nombre a tout de meme un grand facteur... donc forcement il va mouliner un peu avant de se rendre compte que ce facteur est le dernier ! c'est pour ca qu'a chaque fois que tu trouves un nombre, il faudrait que tu divise par ce facteur et que tu recommence a 0 avec le quotient, ca t'eviterai d'aller chercher trop loin des facteurs qui n'existent pas, et accessoirement de reperer les facteur multiples !! j'ai l'impression par exemple que tu n'attrappes le 2 qu'une seule fois, et pas 10 comme il faudrait.

  9. #9
    Membre éprouvé
    Avatar de mavina
    Homme Profil pro
    Développeur Java
    Inscrit en
    Octobre 2004
    Messages
    1 812
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : Chine

    Informations professionnelles :
    Activité : Développeur Java
    Secteur : Conseil

    Informations forums :
    Inscription : Octobre 2004
    Messages : 1 812
    Par défaut
    Coucou,

    oui en fait je ne factorise pas en facteurs de nombre premiers, je ne fais que lister tous les diviseurs.

    Une autre approche serait de prendre le truc à l'envers : pour chaque nombre en dessous de n, si il ne fait pas partie de la liste des diviseurs que j'ai déja mémorisé, je l'ajoute et j'ajoute tous les diviseurs de ce nombre à la liste des diviseurs de n.
    On voit là une recursivité se profiler, et ça n'est pas le fort de java.
    à tester :
    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
     
    	public List<Integer> getDiviseurs2(int n)
    	{
    		List <Integer>result=new ArrayList<Integer>();
    		for(int i=n-1;i>=1;i--)
    		{
    			if(i==1)
    					return result;
    			if(!result.contains(i))
    			{
     
    				if(n%i==0)
    				{
    					result.add(i);
    					result.addAll(getDiviseurs2(i));
    				}
    			}
    		}
    		return result;
    	}
    Cordialement

    Fred

  10. #10
    Membre émérite
    Inscrit en
    Janvier 2005
    Messages
    711
    Détails du profil
    Informations forums :
    Inscription : Janvier 2005
    Messages : 711
    Par défaut
    en effet, je pense que c'est mieux, mais ca n'est pas la peine d'aller a l'envers :-). le probleme venait surtout de la condition d'arret. dans tous les cas, ton algo boucle jusqu'a n. outre le fait qu'on peut se contenter de n'aller que jusqu'a racine de n, en divisant ton nombre a chqaue fois que tu trouves un diviseur, tu reduis d'autant la limite de ta boucle ! si tu cherches a factoriser 770, par exemple, tu peux boucler jusqu'a [racine (770)] = 28, donc 28 iterations. mais si, des que tu rencontre le diviseur 2, tu divise et tu recommence tu feras donc :

    1 iteration -> on trouve 2, on divise par 2 -> d'office tu n'as plus qu'a chercher des diviseurs que jusqu'a sqrt(385) ~ 20

    tu repars de 3 vers 5 -> 2 iterations (voire une si tu enses a aller de 2 en 2) tu divises, et tu sais que tu n'as plus qu'a chercher les diviseurs < sqrt(77) ~ 9

    tu repars de 6 vers 7 une iteration, tu divise et tu recherche jusqu'a racine (11)~4. tu fais 4 iteration, tu ne trouve rien, c'est que 11 est premier, tu as fini. soit environ 8 iterations au lieu de 28...
    en fait, a chaque fois que tu effectue une division tu reduis d'autant la borne sup de ta boucle, et donc le nombre d'iteration au final. je ne connais pas le java, donc je donne un pseudo code :

    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
     
    resultat <- []
     
    factorise(N, depart)
     
    //on traite le cas de 2 a part pour pouvoir ensuite avancer par pas de 2
    si depart == 2
      tant que 2 divise N
        resultat[] <- 2
        N=N/2
      fin tant que
      factorise(N,3) // on recurse
    sinon
      i<-depart
      tant que i ne divise pas N et i <= sqrt(N)+1// on cherche un diviseur
        i<-i+2
      fin tant que
      //si on en a trouvé un
      si i <= sqrt(N)+1
        tant que i divise N // on divise autant de fois que possible
          resultat[] <- i
          N=N/i
        fin tant que
        factorise(N, i+2) // on recurse
      sinon // c'est que N est premier, il n'y a plus de diviseurs
        resultat[] <- N // notre N est donc le dernier diviseur de notre nb de depart
      fin si
    fin fonction
    voila, c'est ecrit a la va vite mais l'idee y est. des qu'on trouve un diviseur, on en profite pour reduire N au maximum, et on repart de la ou on s'etait arrete vu qu'on sait qu'il n'y a pas de diviseur plus petit. dans le pire des cas, on sera en O(sqrt(N)) si N est premier, mais si ses diviseurs ne sont pas trop grand la complexité chute assez vite. par exemple, si N=2^10, ton algo fera 1024 iteration, 512 en prenant la racine comme limite, le mien en fera 12. j'ai ecrit ca vite fait, donc a mon avis on devrait souvent se retrouver avec un1 comme dernier diviseur, mais il suffit de rajouter quelques tests.

  11. #11
    Membre averti
    Inscrit en
    Janvier 2007
    Messages
    17
    Détails du profil
    Informations forums :
    Inscription : Janvier 2007
    Messages : 17
    Par défaut Pas évident
    Salut a vous tous,
    Je continue a bosser sur ce fameux problème. Voici le début de mon code JAVA. J'aurais besoin de votre aide pour l'améliorer

    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
    import java.util.Scanner; // program uses class Scanner
     
    public class PrimeNumbers
    {
       // main method begins execution of Java application
     
    public static void main( String args[] )
     
       {  
    int number;
     
       	  // create Scanner to obtain input from command window
          Scanner input = new Scanner( System.in );  	  
     
     
     
          System.out.print( "Please enter a positive integer greater than 2 or a -1 to quit.\n " ); // prompt 
          number = input.nextInt(); // read first number from user
     
     
         for ( int i = 1; i <= Math.sqrt(number); i++ ) 
             System.out.printf( "%d  ", i );
     
     
       	}
     }

Discussions similaires

  1. [VB6]Problème avec les Nombres de ma BD
    Par jfdmagic dans le forum VB 6 et antérieur
    Réponses: 9
    Dernier message: 04/07/2009, 11h40
  2. problème avec les nombres décimaux
    Par pierrot10 dans le forum Langage
    Réponses: 2
    Dernier message: 07/02/2008, 10h09
  3. Problème avec les nombres à virgule
    Par Lapicure dans le forum Modélisation
    Réponses: 5
    Dernier message: 01/06/2007, 15h37
  4. [débutant] problème avec les nombres aléatoires
    Par happylife925 dans le forum Débuter
    Réponses: 12
    Dernier message: 10/03/2006, 15h47
  5. problème avec les nombres à virgule
    Par shingo dans le forum Langage
    Réponses: 3
    Dernier message: 16/01/2006, 18h30

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo