Racine carré successive
Résolu/Fermé
PyXo
-
Modifié le 23 avril 2021 à 19:48
mamiemando Messages postés 33079 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 23 avril 2024 - 22 avril 2021 à 17:51
mamiemando Messages postés 33079 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 23 avril 2024 - 22 avril 2021 à 17:51
A voir également:
- Racine carré python sans sqrt
- Racine carré en c ✓ - Forum C
- Point d'interrogation dans un carré ✓ - Forum Samsung
- Symbole racine carré clavier téléphone - Forum C#
- Parenthese carré ✓ - Forum MacOS
- Carré en c ✓ - Forum Programmation
1 réponse
mamiemando
Messages postés
33079
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
23 avril 2024
7 749
Modifié le 22 avril 2021 à 18:03
Modifié le 22 avril 2021 à 18:03
Bonjour,
Réponse courte
La mnière la plus simple se résout en écrivant une fonction récursive, mais tu peux également accumuler le résultat du calcul en partant de la racine la plus imbriquée et remonter de racine en racine.
Réponse détaillée
Prenons un exemple plus simple, suppons qu'on veuille calculer la somme des entiers de 0 à n exclu. En python on écrirait bien sûr
Dans ce cas tu vas vouloir écrire une fonction (appelons-la
Pour réaliser une telle itération, il y a deux écoles.
Si on prend le temps de regarder la forme récursive :
Ce sont donc deux manières différentes de calculer la même chose. Comme tu l'as compris, cette exemple peut facilement s'adapter pour calculer des factorielles.
Récursif ou itératif
Selon ce que tu as faire, il est plus facile/naturel d'écrire la version itérative ou récursive d'un problème.
Il faut garder que d'un point de vue informatique, si tu appelles récursivement une fonction un trop gros nombre de fois, python peut planter. Ceci est inhérent à la manière dont marche un programme. Quand on appelle une fonction le runtime garde trace de la pile d'appel des fonctions (ce qui permet, quand une sous fonction se termine, de reprendre le programme où il faut et comme il faut dans la fonction appelante). Comme d'un point de vue système, la taille de la pile d'appel est limité, un trop grand nombre d'appel récursif peut saturer la pile d'appel. On parle alors de débordement de pile (stack overflow en anglais, terme à l'origine d'un célèbre site). De plus cette mise en pile réclame du "travail" à l'ordinateur et sera donc moins performante qu'une écriture itérative équivalente. C'est pourquoi les récursions doivent être utilisées avec parcimonie.
Au contraire, la version itérative ne met en jeu qu'un seul appel à la fonction
Pour aller plus loin: à noter que ça ne signifie pas qu'il faut systématiquement proscrire une écriture récursive. En particulier, toute la branche de la programmation dynamique, qui permet de décomposer un problème sous forme récursive en mémorisant des résultats intermédiaire, s'écrit en pratique sous forme récursive. Quelques exemples classiques : [les suites de Fibonnacci], la plupart des distances d'éditions, etc.
Retour à ton exercice
Dans ton cas, tu peux facilement adapter la récurrence pour calculer des racines carrées imbriquées et en utilisant la fonction
Une fois que ce sera bien clair pour toi, tu peux t'entraîner à écrire le programme dans sa version itérative.
Bonne chance
Réponse courte
La mnière la plus simple se résout en écrivant une fonction récursive, mais tu peux également accumuler le résultat du calcul en partant de la racine la plus imbriquée et remonter de racine en racine.
Réponse détaillée
Prenons un exemple plus simple, suppons qu'on veuille calculer la somme des entiers de 0 à n exclu. En python on écrirait bien sûr
sum(range(n))mais que se passe-t'il si on s'interdit d'utiliser
sumet
range?
Dans ce cas tu vas vouloir écrire une fonction (appelons-la
somme) dans laquelle tu itères de 0 à n, et au cours de laquelle tu mets progressivement à jour le résultat (appelons le
s).
Pour réaliser une telle itération, il y a deux écoles.
- La méthode itérative :
def somme(n):
s = 0
for i in range(n):
s += i
return s
- La méthode récursive (pense au "raisonnement par récurrence que tu as dû voir en cours de maths) :
def somme(n, i = 0):
if i > n - 1:
return 0
return i + somme(n, i + 1)
Si on prend le temps de regarder la forme récursive :
- le paramètre
i = 0
correspond à la première "moitié" defor i in range(n)
de la version itérative (on compte à partir de 0) - le test i > n -1 correspond à la seconde "moitié" de
for i in range(n)
de la version itérative (on compte s'arrête quand on dépasse n -1) - l'instruction
return 0
correspond às = 0
(quel est le résultat quand on n'a pas pu itérer), c'est l'initialisation du raisonnement par récurrence. - l'instruction
i + somme(n, i + 1)
, c'est la récurrence elle-même. Elle signifie dans cette exemple : la somme des entiers de 0 à n est égale à "0 + somme(k = 1 à n) = 0 + (1 + somme(k = 2 à n)) = 0 + (1 + (2 + ... + (i + (somme(k = i + 1 à n))...)"
Ce sont donc deux manières différentes de calculer la même chose. Comme tu l'as compris, cette exemple peut facilement s'adapter pour calculer des factorielles.
Récursif ou itératif
Selon ce que tu as faire, il est plus facile/naturel d'écrire la version itérative ou récursive d'un problème.
Il faut garder que d'un point de vue informatique, si tu appelles récursivement une fonction un trop gros nombre de fois, python peut planter. Ceci est inhérent à la manière dont marche un programme. Quand on appelle une fonction le runtime garde trace de la pile d'appel des fonctions (ce qui permet, quand une sous fonction se termine, de reprendre le programme où il faut et comme il faut dans la fonction appelante). Comme d'un point de vue système, la taille de la pile d'appel est limité, un trop grand nombre d'appel récursif peut saturer la pile d'appel. On parle alors de débordement de pile (stack overflow en anglais, terme à l'origine d'un célèbre site). De plus cette mise en pile réclame du "travail" à l'ordinateur et sera donc moins performante qu'une écriture itérative équivalente. C'est pourquoi les récursions doivent être utilisées avec parcimonie.
Au contraire, la version itérative ne met en jeu qu'un seul appel à la fonction
sommeet ne maintient en mémoire que peut d'information (les valeurs de
s,
i, et
n) et donc passe mieux à l'échelle.
Pour aller plus loin: à noter que ça ne signifie pas qu'il faut systématiquement proscrire une écriture récursive. En particulier, toute la branche de la programmation dynamique, qui permet de décomposer un problème sous forme récursive en mémorisant des résultats intermédiaire, s'écrit en pratique sous forme récursive. Quelques exemples classiques : [les suites de Fibonnacci], la plupart des distances d'éditions, etc.
Retour à ton exercice
Dans ton cas, tu peux facilement adapter la récurrence pour calculer des racines carrées imbriquées et en utilisant la fonction
math.sqrtpour calculer des racines carrées :
from math import sqrt print(sqrt(9))
Une fois que ce sera bien clair pour toi, tu peux t'entraîner à écrire le programme dans sa version itérative.
Bonne chance
