Inscription / Connexion Nouveau Sujet
Niveau Licence Maths 1e ann
Partager :

Euclide Exo L1 - Arithmétique

Posté par
UneL1maths
02-10-23 à 00:06

Bonjour,

Je suis en licence de maths et j'ai vraiment du mal à démarrer cette exo. J'ai fais l'initialisation j'ai réussi (avec un peu bcp d'aide) a montrer dans la 1er récurrence que

(Complexité de l'algorithme d'Euclide)

On rappelle que l'algorithme d'Euclide peut être présenté par la fonction euclide(. , .)

euclide(a,b) =

a          
si  b=0,
                            
euclide(b,r)
si b != 0,  et où a=bq+r avec 0 <= r < b.

On appelle n'ombres d'étapes dans l'exécution de l'algorithme le nombre d'appel récursifs de la fonction euclide(a,0) s'effectue en 0 étapes
On définit la suite de Fibonacci (Fn)n>=0 par la relation de récurrence suivante:

F(0) = 0 , F(1)=1
Pour tout entiers naturel n supérieur ou égale à 0,
F(n+2) = F(n) + F(n+1)


1.  ✨Montrer par récurrence sur k>= 0 que si: a et b sont deux entiers positifs avec a>0 et a>=b et si euclide(a,b) s'effectue en k étapes alors a>= F(k+1) et b>=F(k)

2. ✨En déduire que pour tout entier k>=1 et pour tous entier a, b >= 0 avec a>=b, si b<F(k) alors(a,b) s'effectue au plus en k étapes

3. ✨Montrer par récurrence sur k que euclide F(k+1)* F(k) s'effectue en exactement k étapes.



4. ✨On note “…”
(Désolé je fuis latex)
(appelé nombre d'or).
En admettant les deux résultats suivants:

(a)lim n tend vers +infini de (F(n+1)/F(n) = nombre d'or)

(b) Fn est environ égale au (nombre d'or)**n divise par racine de 5

montrer que le nombre d'étapes pour effectuer euclide (a,b) est O(log b)c'est-à-dire qu'il existe une constante C>=O telle que, si N(a.b) désigne le nombre d'étapes dans l'évaluation de la fonction
euclidel4.0). 00 a
N(a, b) ≤ Clogb

Merciii infiniment vous me sauverez j'en ai marre d'enchaîner les corrections sans comprendre la matière que je fais. Vous me serez d'une grande aide ❤️

Posté par
UneL1maths
re : Euclide Exo L1 - Arithmétique 02-10-23 à 00:09

Du coup dans la récurrence j'ai montré que b >= F k+1 en réf lichissant par identification

Euclide(a,b) =euclide(b,r) j'ai posé b=a et j'ai fini avec a=b donc b>= Fk+1 d'après mon hypothèse de récurrence et pour montrer que a>= F(k+2)  je suis bloqué voili voilou

Posté par
psilm
re : Euclide Exo L1 - Arithmétique 01-12-23 à 12:02

Bonjour!
Je voulais te rédiger tout un message mais le site me l'a rejeté.
Je n'ai malheureusement pas le temps de le réécrire.
Tu trouveras donc une proposition de correction en pièce jointe sans explications.
Si jamais tu as des questions, n'hésite pas à réécrire sur ce forum. J'essaierai d'y répondre.
Bonne après-midi!

** Fichier supprimé **

Posté par
Sylvieg Moderateur
re : Euclide Exo L1 - Arithmétique 01-12-23 à 16:28

Bonjour,
@psilm,
Euclide Exo L1 - Arithmétique

Donner des pistes, oui ; mais pas "une proposition de correction".

Posté par
UneL1maths
re : Euclide Exo L1 - Arithmétique 09-12-23 à 23:03

Merci beaucoup à toi malheureusement je n'ai pas pu voir ta réponse (fichier supprimé) c'est très gentil de ta part d'avoir pris le temps de me répondre en tout cas. Merci merci beaucoup



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1687 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !