Puisssance d'un nombre(fonction récursive) - Java - Programmation
Marsh Posté le 26-12-2019 à 15:30:59
Bonjour,
Il te suffit de partir de l'exposant 0 et de l'augmenter à chaque nouvel appel de la fonction au lieu de le diminuer. Faut aussi changer la condition dans ta fonction pour qu'elle corresponde à supérieur ou égale à ton nombre limite.
Marsh Posté le 29-12-2019 à 13:31:47
La récursivité, c'est une obligation ? Parce que c'est pas le plus optimisé. Même avec des petits nombres, tu arriveras vite à faire péter la pile d'appels et de sauvegarde du contexte.
Marsh Posté le 03-01-2020 à 19:10:25
Salut
J'ai fait une méthode non récursive et une récursive. Mais je ne sais pas pourquoi celle récursive donne le résultat plusieurs fois
Code :
|
Code :
|
Marsh Posté le 03-01-2020 à 20:53:52
Dans ta fonction récursive il faut virer le while (même s'il ne fait qu'un tour en fin de compte, il n'a pas de sens).
En fait tu as deux cas (à ce moment là tu sais que tu faire un IF ... ELSE ...), soit ton résultat de calcule est inférieur à celui demandé et donc tu rappelles ta fonction en incrémentant l'exposant, soit ton résultat est supérieur ou égale à celui demandé, auquel cas tu affiches la valeur atteinte de l'exposant.
Marsh Posté le 04-01-2020 à 18:04:56
Merci, j'ai viré le while, et j'ai le résultat une seule fois maintenant, niquel
Edit : c'est vrai aussi que dans l'énoncé du posteur il faut afficher le résultat dès qu'on atteint la valeur testée, qu'on soit égal ou supérieur
Code :
|
Marsh Posté le 09-01-2020 à 15:48:28
Salut,
Niveau perf, cela ne me semble pas super judicieux de recalculer à chaque fois la nouvelle valeur avec avec pow :-/
Je ne sais pas comment c'est codé pow, mais si c'est une fonction "con", chaque tour de récursion reviennent à faire en gros :
3*3
3*3=9 puis 9*3=27
3*3=9 puis 9*3= 27 puis 27*3= 81
Si on cherche un grand nombre, je pense que c'est rapidement pas terrible comme solution :-/
alors qu'en gardant en mémoire le précédent résultat, on doit pouvoir se contenter de faire à chaque tour de récursion :
3*3 =9
9*3 = 27
27*3 = 81
81*3 = 243
243*3=729
729*3=2187
Après si on cherche à faire encore des économies sur le nombre de calcul à faire, on doit pouvoir essayer de s'inspirer de la recherche dichotomique pour s'approcher plus vite de la valeur mais ça va compliqué l'algo (et pas être super intéressant dans pour des valeurs assez basses)
Exemple :
3*3=9
9*9=81 (on économise le calcul de 3*9)
81*81= 6561 (on économise le calcul de 243, 729 , 2187 mais au final on est trop haut et on est obligé de vérifié l'intervalle (en recherche dichotomique on le coupe en 2 donc on calcul 729 qui est trop bas puis on calcul 2187 qui est la bonne solution, dans ce cas la on a juste économisé le calcul de 243 mais on y a perdu a faire le calcul de 6561 par rapport a l'algo précédent donc c'est kifkif, mais pour des plus grandes valeurs ça doit être rapidement rentable je pense :-)
Marsh Posté le 11-01-2020 à 15:29:01
J'ai fait une methode comme tu le dis (moulinetteMod).
Et j'ai implémenté un "contrôle" du temps, mais je ne sais pas si je l'ai fait correctement car j'ai eu ces valeurs hier :
moulinette : 2 998 300
moulinetteMod : 2 010 400
Puis aujourd'hui :
moulinette : 1 001 300
moulinetteMod : 1 000 500 et aussi un truc dans les 2 000 000
Et mon contrôle du temps ne fonctionne pas avec moulinetteRec la méthode récursive, je pense qu'il me faut des variables globales à ce niveau
Code :
|
Marsh Posté le 20-01-2020 à 17:58:49
Pour les calculs de durée tu devrais sortir le code qui calcul la durée du code qui appelle la fonction de calcul du resultat.
En mini solution récursive en javascript parce que plus simple pour moi de faire ça dans le navigateur même si c'est pas vraiment adapté au sous forum java... c'est juste pour montrer le principe de la récursion :
Code :
|
Cela retourne l'indice qui va bien en faisant une seule multiplication par récursion. Faudra que je vois pour de la recherche dichotomique mais je pense que ca risque de compliquer :-/
Marsh Posté le 20-01-2020 à 18:36:29
En plus chui con, ma moulinetteMod elle n'est pas récursive
Marsh Posté le 20-01-2020 à 20:15:37
Voilà ma dernière méthode, récursive.
J'ai sorti le calcul du temps pour toutes mes méthodes. (je prends l'heure, j'appelle ma methode, je reprends l'heure et je fais la différence). J'ai toujours des différences (+50%) d'un lancement à un autre pour une même méthode avec les mêmes nombres entrés.
Code :
|
La console :
Marsh Posté le 21-01-2020 à 00:10:26
Je suis en train de tester, avec une boucle for je viens de lancer 1 million de fois chaque méthode, séparément, ça met 3 secondes a se faire environ, c'est pas assez, les scores sont trop proches pour départager ! Demain je lance des boucles de 10 ou 20 millions de fois
Marsh Posté le 21-01-2020 à 07:56:42
Plutôt que d'augmenter le nombre de boucle il faudrait augmenter le nombre à atteindre, la il arrive très vite à 500 : 2, 4, 8, 16, 32, 64, 128, 256, 512
Il faudrait plutôt atteindre des millions voire des milliards pour que l'on puisse finir par voir une différence minime je pense
Marsh Posté le 21-01-2020 à 11:27:12
Oui j'avais déjà augmenté à 5 millions j'ai oublié de dire. Je viens de mettre 999 millions (j'arrive pas à mettre plus même avec un type long) mais c'est atteint très rapidement tout de même j'avais fait l'essai (500 millions = exposant 29 seulement)
Donc : base 2, nombre a atteindre 999 999 999, 10 millions de boucles
Résultats de 2 essais par méthode, en secondes :
Méthode pow non récursive
28
28,2
Méthode pow récursive
30
30,7
Méthode base*base non récursive
26
26,5
Méthode base*base récursive
26
26,7
Je crois donc que tu avais bien raison, pow coute plus que de multiplier simplement
Marsh Posté le 21-01-2020 à 11:56:38
Oui la fonction puissance augmente très rapidement en valeur du coup on atteint très rapidement le nombre à atteindre.
Il faudra que je prenne le temps de regarder dans chrome, il me semble qu'on peut aller beaucoup plus haut en valeur (2^999 ?) avant que cela considère que c'est une valeur infini.
Hop mini edit pour la fonction recursive avec un timer a mettre dans la console javascript (f12 sur firefox ou chrome)
Code :
|
Marsh Posté le 21-01-2020 à 13:01:00
Ça me sort ça
Mais j'ai eu une fois 1ms et une fois 2ms
997 c'est l'exposant ?
Faut que je regarde comment dépasser 999 999 999 en JAVA
Marsh Posté le 21-01-2020 à 13:50:23
Oui c'est l'exposant obtenu (et donc le nombre de fois que la fonction s'appelle à elle même en gros)
J'ai aussi vite fait réadapté pour passer l'exposant et recalculer avec pow :
Code :
|
Marsh Posté le 21-01-2020 à 14:06:54
Et mini bout de code pour comparer les appels aux 2 fonctions de 2 jusqu’à 10m :
Code :
|
J'obtiens :
Puissance_recursive: 4686.41796875ms
Puissance_recursive_pow: 16878.303955078125ms
Soit environ 4 fois mieux en passant le résultat de la multiplication a chaque itération plutôt qu'en passant l'exposant et en recalculant la multiplication (et je m'attendais à mieux xD)
Au départ j'ai mis la boucle jusqu'à 1milliard mais c'est trop long j'ai eu la flemme d'attendre donc j'ai diminué ^^
Edit : avec 100million :
Puissance_recursive: 42656.34716796875ms
Puissance_recursive_pow: 148851.09619140625ms
Encore un peu moins de 4 fois mieux
Marsh Posté le 30-01-2020 à 10:15:26
Bon, j'ai amélioré mon code, à savoir que j'affichais 10 millions de fois le résultat dans la console puisque l'affichage se faisait dans mes méthodes. J'ai donc sorti l'affichage et il ne se fait plus qu'une seule fois à la fin.
Ça n'a plus rien à voir, le prog est bien plus rapide et les méthodes base*base sont 3x plus rapides qu'avec pow tu as raison
pow : 15,3sec
pow recursive : 16,5sec
base*base : 5,1sec
base*base recursive : 5,5sec
Edit :
Nombre à atteindre : 8 999 999 999 999 999 999
base : 2
10 millions de boucles
Marsh Posté le 26-12-2019 à 14:56:54
Bonjour,
Je voudrais ecrire une fonction qui fait la puissance d'un nombre jusqu'à que ce nombre soit egale a une valeur a tester.
Par exemple,
valeur a tester = 1455
Nombre = 3
Le programme doit faire 3×3×3...×3 jusqu'à que le result soit superieure ou egale a 1455.
Avez vous une idée ?
Je sais faire pour la puissance d'un nombre avec l'exposant deja connu a l'avance ca donne ceci mais pour mon exemple a faire je bloque.