Salut à tous (ça fait longtemps ),
l’objet de ce topic tient sur une question d’un exercice de spé maths (terminale S) que je n’arrive pas à traiter.
Voici la question en cause :
Établir un algorithme décomposant un entier N non nul en une somme de puissances de 2 distinctes. Justifier que cet algorithme s’arrête.
Pour ce qui est de l’algorithme : aucun problème, le voici en langage naturel (je l’ai programmé et testé sur ma calculette) :
Demander N
1 -> K
Tant que N ≥ K
2*K -> K
Fin Tant que
Tant que N ≠ 0
K/2 -> K
Si K ≤ N alors
N-K -> N
Afficher K
Fin Si
Fin Tant que
Le problème réside dans le fait de montrer que ce programme s’arrête, et plus particulièrement la seconde boucle.
En effet, pour la première on sait que limx→+∞2x=+∞ et donc par définition il existe K∈N tel que 2K>N.
Pour la seconde, cela revient à montrer que tout entier (naturel) peut être exprimé comme une somme de puissances de 2 distinctes. Et pour cela je galère pas mal. À mon avis il faut quelque part utiliser le fait que :
∀n∈N,2n+2n=2×2n=2n+1
j’ai aussi pensé utiliser une preuve par récurrence mais je n’arrive pas à faire aboutir l’hérédité et je pense que mon plus gros problème est que je ne sais pas vraiment comment écrire la somme de puissances de 2 distinctes mathématiquement.
Merci d’avance pour votre aide.