[PDF] TP n˚4 : corrigé - Normale Sup PDF TP4cor.pdf

pour gérer les puissances négatives en ajoutant simplement un inverse à la fin très rapide en utilisant la fonction précédente et une manipulation intelligente

R et n ∈ N? – Ce programme est-il correct ? – puiss4 est-il vraiment plus rapide que le procédé « naïf » ? Si oui, dans quelle mesure — peut-on le quantifier ?

[PDF] Exponentiation rapide - POLARIS

Un premier algorithme naïf (3 donne un coût en nombre d'opérations ⋆ en O(n) PUISSANCE-NAIF(x,n) Données : Un objet x et un entier n positif Résultat : La

[PDF] Puissances et polynômes

Estimer le nombre de multiplications effectuées pour calculer xn Pour quelles valeurs de n l'algorithme rapide est-il 10 fois plus rapide que l'algorithme naïf ? 5

[PDF] Chapitre 5 : « Puissances entières dun nombre »

Un produit est le résultat d'une multiplication Les nombres que l'on multiplie sont appelés les facteurs II Puissances d'un nombre relatif 1

[PDF] Algorithmique - LRDE - Epita

26 fév 2016 · xn−1 ⋆ x sinon L'algorithme d'exponentiation rapide peut alors être utilisé pour Il faut Θ(log b) multiplications pour calculer la puissance

[PDF] Multiplication rapide : Karatsuba et FFT

Nous présentons ici deux méthodes de multiplication rapide sur les polynômes Fourier rapide, dite FFT On suppose que n est une puissance de 2 Soit m

[PDF] TP n˚4 : corrigé - Normale Sup

pour gérer les puissances négatives en ajoutant simplement un inverse à la fin très rapide en utilisant la fonction précédente et une manipulation intelligente

[PDF] Le cours des parties calculatoires au TAGE MAGE - TageMajor

III – Fractions, puissances et racines Au TAGE MAGE, la manipulation rapide d'additions est fondamentale dans la réussite du sous-test Calcul Pour cela, il

[PDF] LORDRE DE GRANDEUR DU RÉSULTAT DUN CALCUL

Prérequis : il faut maîtriser la notion de puissance de dix, ainsi que les multiplications c'est qu'ils permettent de vérifier par un calcul rapide la cohérence d'un

[PDF] Multiplication rapide de matrices et applications - webusersimj-prgfr

Le premier est algorithme de multiplication rapide est dû à V STRASSEN (1969) et son amélioration à S taille une puissance de 2, c'est-à-dire n = 2

TP n°4 : corrigé

PTSI Lycée Eiffel

décembre 2014

1 Lecture et analyse de programmes

Il faut évidemment tester les fonctions avec votre Python préféré. La première fonction calcule

simplementf(x) = 3x23x. La deuxième affiche le nombre qui est le plus petit entrexetx2. La dernière calcule le plus petit entiernpour lequelnX k=1kdevient plus grand quex.

2 Quelques petits exemples pour commencer à programmer vous-

même

1. Un exemple parmi tant d"autres possibles pour la puissance :

def puissance(x,n) : p=1 for i in range(n) : p=p*x return p Cette version ne fonctionnera qu"avec un entiernpositif, on peut toujours rajouter un teste pour gérer les puissances négatives en ajoutant simplement un inverse à la fin.

2. Il faut simplement faire attention à bien garder en permanence deux termes de la suite en

mémoire, et à les modifier correctement. La solution classique pour cela est d"utiliser une variable temporaire, mais on peut en Python affecter simultanément deux variables, autant en profiter (bien sûr, en pratique, les affectations ne sont pas simultanément, c"est Python qui gère tout seul la variable temporaire). def fibonacci(n) : a,b=0,1 for i in range(n-1) : a,b=b,a+b return b

3. Plein de possibilités ici, notamment certaines qui utilisent un passage par les chaines de carac-

tères pour isoler les chiffres. Pour faire quelque chose de plus mathématique, on peut procéder

de la façon suivante : pour isoler le dernier chiffre d"un nombre, on prend le reste de sa division

par10, et pour supprimer ce dernier chiffre on divise le nombre (de façon euclidienne) par10. def sommechiffres(n) : a=n; s=0 1 while a!=0 : s=s+a%10 s=s//10 return s

3 Pour s"entraîner avec la récursivité

Pour le calcul de puissance, on peut faire une première version récursive simple, où on se contente

de multiplierxparxn1(quandn>1) pour calculerxn. En Python, cela peut donner ceci : def recpuiss(x,n) : if n==0 : return 1 else : return x*recpuiss(x,n-1)

Une autre version nettement plus efficace, où on divise la puissance par2à chaque fois que c"est

possible : def recpuiss(x,n) : if n==0 : return 1 elif n==0 : return x elif n%==2 : return recpuiss(x,n/2)**2 else : return x*recpuiss(x,(n-1)/2)**2

Le nombre de calculs nécessaires avec cette dernière méthode est de l"ordre de2log2(n)au pire.

Passons à un Fibonacci bêtement récursif : def recfibo(n) : if n==0 : return 0 elif n==1 : return 1 else : return recfibo(n-1)+recfibo(n-2)

Ce programme est en fait complètement minable, car il ne se rend pas compte qu"il va devoir recalculer

plein de fois les mêmes nombres. Par exemple, pour calculerF20, il va tenter de calculerF18+F19,

mais en calculant les deux morceaux de façon indépendate, donc en faisant deux nouveaux appels à

la fonction pourF18, et deux autres pourF19. En multipliant par deux le nombre d"appels à chaque

étape, le temps d"exécution du programme explose très rapidement. Dernier programme pour lequel

la récursion marche très bien, la somme des chiffres : def recsommechiffres(n) : if n<10 : return n else : return (n%10 + recsommechiffres(n//10)) 2

4 Amusons-nous un peu avec les nombres entiers

1. Le plus simple est évidemment de tester si notre nombre est divisible par chacun des entiers

plus petits que lui. Plus précisément, on fera varier les entiers à tester entre2etpn, ce qui

est suffisant. Si on trouve un diviseur, on sort de la boucle en retournant la valeur False. Si on arrive en fin de boucle, c"est que le nombre est premier, et on ressort la valeur True. def prems(n) : for i in range(2,int(sqrt(n))+1) : if n%i==0 : return False return True

2. On peut faire très rapide en utilisant la fonction précédente et une manipulation intelligente

des listes en Python def listeprems(n) : return [i for i in range(2,n+1) if prems(i)==True]

3. L"algorithme d"Euclide est très simple à programmer avec les doubles affectations de Python :

def euclide(n,p) : a,b=n,p while b!=0 : a,b=b,a%b return a Une version récursive est en effet possible quoique relativement superflue : def receuclide(n,p) : if p==0 : return n else : return receuclide(p,n%p)

4. On peut reprendre quasiment le même programme qu"à la première question : si on croise un

diviseur den(ce sera forcément le plus petit), on retourne sa valeur, sinon c"est quenest premier et on retourne tout simplement la valeur den. def facteurmin(n) : for i in range(2,int(sqrt(n))+1) : if n%i==0 : return i return n

5. Je donne directement une version récursive car c"est vraiment efficace pour un programme de

ce type : on cherche le plus petit facteur premier, et on recommence après avoir divisénpar ce facteur. def listefacteurs(n) : 3 if n==1 : return [] else : p=facteurmin(n) return [p]+listefacteurs(n/p)

5 Pour ceux qui ont tout trouvé trop facile

Bon, je n"ai pas tout trouvé facile, alors je ne fais pas cette partie! Plus sérieusement, je la mettrai

à jour, mais plus tard.

4quotesdbs_dbs2.pdfusesText_2

[PDF] [PDF] TP n˚4 : corrigé - Normale Sup

[PDF] Comment calculer les puissances dun nombre ?