Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Maths sup ConcoursTopics traitant de concours [tout]Lister tous les topics de mathématiques

1 2 +

Posté par
Ramanujanre : Entier en base deux 12-10-18 à 18:54

luzak @ 12-10-2018 à 18:48

Bref, mauvaise volonté à tous les étages !
Et tu as écrit "honnêtement c'est trop compliqué", sans faire le moindre effort !

Quelle différence entre ce qu'a écrit mousse42 à 16:41 et ce que j'ai dit à 13:27 ?
n (ou n-1 : énoncé original) est une partie entière d'où unicité.

@carpediem :
il refuse ton approche parce qu'il a un corrigé qui fait une récurrence.
Sauf que son corrigé fait une démonstration d'unicité par récurrence ce qui est souvent contestable.


Je fais des efforts mais j'y peux rien si je comprends pas vos posts. Votre récurrence me déstabilise, elles ressemble pas aux récurrences classiques. Je suis perdu dès la 1ère ligne.

Non mon corrigé a rien à voir avec la méthode de Mousse que je trouve la plus intuitive et celle que je comprends le mieux.
Mais je sais pas comment poursuivre pour démontrer le résultat.

Posté par
malou Webmasterre : Entier en base deux 12-10-18 à 18:56

Ramanujan @ 12-10-2018 à 18:50

....Généralement ces gens là n'arrivent pas à se mettre au niveau des autres moins doués.


que de certitudes, que d'affirmations gratuites, que ....

Posté par
carpediemre : Entier en base deux 12-10-18 à 18:56

luzak : oui bien sur ...

en même tempq quand on apprend seul on s'adapte et on s'ouvre ... à la diversité ...

Ramanujan @ 12-10-2018 à 18:50

Vous sortez tous d'une ENS ou quoi ? Généralement ces gens là n'arrivent pas à se mettre au niveau des autres moins doués.
non juste du collège .... et encore à peine pour résoudre cet exo ...

à 15h33 je te montre/fait la récurrence ... plus les commentaires qui montrent que cette récurrence est inutile ...

Posté par
mousse42re : Entier en base deux 12-10-18 à 19:01

Heureusement quil est là le mousse

Posté par
luzakre : Entier en base deux 12-10-18 à 20:40

Sans savoir de quel message tu parles, difficile de te répondre : les lignes 1,2 il y en a une certaine quantité !

Posté par
Schtromphmolre : Entier en base deux 12-10-18 à 23:22

Citation :
Vous sortez tous d'une ENS ou quoi ? Généralement ces gens là n'arrivent pas à se mettre au niveau des autres moins doués.

Ah bon.

Posté par
Ramanujanre : Entier en base deux 13-10-18 à 05:06

@Luzak

Si tu as démontré que d_0 est le reste de la division de N par 2, tu as forcément d_0=d'_0 (les divisions euclidiennes définissent un reste unique  et un quotient unique).
En supposant 0\leqslant k\leqslant p<n\implies d_k=d'_k, tu notes  

N'=\dfrac{N-\sum_{0\leqslant k\leqslant p}d_k2^k}{2^p}

et tu vois que N' admet les développements d_{p+1},\dots,d_n,\;\;d'_{p+1},\dots,d'_n et c'est fini!

Pourriez vous m'expliquer ? C'est quoi ce N' ?
Quelle est l'hypothèse de récurrence ?
Pourquoi montrez que c'est vrai de p+1 à n et pas seulement en n ?

Posté par
Ramanujanre : Entier en base deux 13-10-18 à 05:07

mousse42 @ 12-10-2018 à 19:01

Heureusement quil est là le mousse


Vous avez pas répondu pour la récurrence

Posté par
luzakre : Entier en base deux 13-10-18 à 06:53

Hypothèse de récurrence : égalité des chiffres d_k=d'_k pour 0\leqslant k<p

vrai pour p=1 : unicité du chfifre des unités

Pour passer à p+1 j'enlève la partie formée par les chiffres égaux, donc je pose N1=N-\sum_{0\leqslant k<p}d_k2^k. C'est un entier divisible par 2^{p-1} et N'=2^{1-p}N_1 est représenté par les chiffres d_p,\dots,d_n et d'_p,\dots,d'_n, le chiffre des unités étant d_p ou d'_p.
On sait que pour l'entier N' ce chiffre est unique (si tu veux c'est le c_0 de N') donc d_p=d'_p : hérédité terminée.

Posté par
carpediemre : Entier en base deux 13-10-18 à 08:56

en plus c'est ce que j'ai écrit à 15h33 et l'hérédité consiste à répéter l'initialisation que j'ai faite : pour passer d'un rang au suivant on enlève le chiffre de droite qui est le même dans les deux écritures

luzak l'écrit simplement de façon condensée avec un n pour dire : ho le n de la récurrence !!! il est là !!!!

Posté par
luzakre : Entier en base deux 13-10-18 à 09:39

Pas tout à fait : "ma" récurrence porte sur p car n est une donnée de l'énoncé et ne peut être modifiée.

Posté par
carpediemre : Entier en base deux 13-10-18 à 10:54

oui pardon !!! remplacer dans ma dernière ligne n par p ...

Posté par
Ramanujanre : Entier en base deux 13-10-18 à 13:28

@Luzak

Merci. J'ai compris l'hypothèse de récurrence et l'initialisation mais à partir de l'égalité je vois pas.

N1=N-\sum_{0\leqslant k<p}d_k2^k

Je le réécris sous la forme : N_1 = N - \sum_{k=0}^{p-1}d_k 2^k

Je ne comprends pas pourquoi N_1 est divisible par 2^{p-1}

Et pourquoi : N' = 2^{1-p} N_1

Je vois pas où vous introduisez le N' avec les coefficients d'_k ?

Puis la fin j'ai pas compris non plus pourquoi d_p est le chiffre des unités ?

Bref, vous allez trop vite je suis déjà bloqué à la première égalité

Posté par
Ramanujanre : Entier en base deux 13-10-18 à 13:38

J'ai simplifié votre N_1 je trouve :

N_1 = \sum_{k=p}^{n-1} d_k 2^k

J'essaie de démontrer que N_1 est divisible par 2^{p-1}

N_1 = 2^{p-1} \sum_{k=p}^{n-1} d_k  2^{k-p+1}

Or k-p+1 \geq 1 donc N_1 divisible par 2^{p-1}

Par contre à partir du N' je vois pas trop :

Votre N' c'est \sum_{k=0}{n-1} d'_k 2^{k}

C'est quoi le rapport avec N' = 2^{1-p}N_1 ?

Posté par
luzakre : Entier en base deux 13-10-18 à 14:02

Désolé, le 2^{1-p} est une erreur, c'est 2^{-p}.

Si tu n'es pas capable de manipuler des  "sommes indexées" fais comme les débutants, écris tout avec des points de suspension :
N_1=d_p2^p+d_{p+1}2^{p+1}\cdots+d_{n-1}2^{n-1}=2^p(d_p+2d_{p+1}+\cdots+d_{n-1}2^{n-1-p})
donc N'=d_p+2d_{p+1}+\cdots+d_{n-1}2^{n-1-p}

Et, en recommençant avec N=\sum_{0\leqslant k<n}d'_k2^k=\sum_{0\leqslant k<p}d_k2^k+\sum_{p\leqslant k<n}d'_k2^k (hypothèse de récurrence donnant l'égalité des chiffres jusqu'à l'ordre p-1) tu te retrouves avec N'=\sum_{p\leqslant k<n}d'_{k}2^{p-k} et, par comparaison des restes de division par 2, d_p=d'_p .
Tu as l'hérédité de récurrence.

Posté par
carpediemre : Entier en base deux 13-10-18 à 15:01

il est quand même triste de ne pas voir (parce que ne pas faire et écrire) :

n = \sum_0^m a_k2^k = a_0 + 2a_1 + 2^2a_2 + 2^3a_3 + ...

n - a_0 = 2 (...) \\ n  - a_0 - 2a_1 = 2^2 (...) \\ n - a_0 - 2a_2 - 2^2a_2 = 2^3(...) \\ ...

Posté par
Ramanujanre : Entier en base deux 13-10-18 à 15:11

J'arrive bien à manipuler les sommes aucun souci avec ça.

Vous avez pas fait une erreur au N' ? Pourquoi vous factorisez par 2^{-p} et pas 2^p ?

Je réécris tout :

Jusque ici on est d'accord :

N=\sum_{k=0}^{p-1} d_k 2^k + \sum_{k=p}^{n-1} d'_k 2^k

En factorisant par 2^p on trouve :

N=\sum_{k=0}^{p-1} d_k 2^k + 2^p ( \sum_{k=p}^{n-1} d'_k 2^{k-p})

J'ai pas compris la fin comment obtenir : d_p = d'_p

Posté par
Ramanujanre : Entier en base deux 13-10-18 à 15:39

Pour la fin j'ai une idée c'est ça ?

On obtient alors :

N'=\sum_{k=p}^{n-1} d'_k 2^{k-p} =\sum_{k=p}^{n-1} d_k 2^{k-p} = d'_p +2 \sum_{k=p+1}^{n-1} d'_k 2^{k-p-1}  = d_p + 2 \sum_{k=p+1}^{n-1} d_k 2^{k-p-1}

Le reste de la division euclidienne de N' par 2 est unique ainsi : d_p = d'_p

Posté par
luzakre : Entier en base deux 13-10-18 à 16:30

Je l'avais déjà dit (14:02!
L'erreur du 2^{1-p} vient de ce que j'avais commencé une récurrence portant sur p-1 chiffres identiques. J'ai changé en p chiffres identiques en oubliant de corriger l'exposant !

Non le 2^{-p} n'est pas une erreur : moi je multiplie par 2^{-p} et toi tu divises par 2^p. Je pense que c'est exactement la même chose !

Posté par
Ramanujanre : Entier en base deux 13-10-18 à 17:20

Merci beaucoup Luzak ! Vous m'avez beaucoup aidé.

Si j'appelle P(p) la propriété.

Juste une dernière question : la récurrence est faite pour 0 \leq k < p

Le p vérifie la condition p \leq n-1 ?

Comme ça on aura d'après la récurrence forte P(p) valable pour tout p.

Posté par
Ramanujanre : Entier en base deux 13-10-18 à 18:03

En fait j'ai compris c'est le principe de récurrence forte on a montré :

(\forall k \in [|0,p-1|] : d_k = d'_k) \Rightarrow d_p = d'_p

Donc \forall p \in [|1,n-1|] : d_p = d'_^p

C'était difficile cette question quand même... Y a k,n et p dans la récurrence, puis les récurrences fortes c'est jamais simple.

Posté par
luzakre : Entier en base deux 13-10-18 à 18:38

YApas n c'est une donnée de l'énoncé !
Yapas k ce n'est qu'un indice de sommation ou d'écriture d'un "quelque soit" : indice muet.
La récurrence porte sur l'entier p, point barre !

Et une récurrence forte n'est qu'une récurrence !

Posté par
Ramanujanre : Entier en base deux 13-10-18 à 18:45

Oui la récurrence porte sur p mais faut bien préciser que p est un entier qui est compris entre 0 et n-1 non ?

Vous avez écrit au départ : 0 \leq k < p

Faudrait t-il pas mettre :  0 \leq k < p \leq n-1 ?

Comme ça on a démontré le résultat pour tout p donc pour tout entier entre 0 et n-1

Posté par
Ramanujanre : Entier en base deux 13-10-18 à 18:46

carpediem @ 13-10-2018 à 15:01

il est quand même triste de ne pas voir (parce que ne pas faire et écrire) :

n = \sum_0^m a_k2^k = a_0 + 2a_1 + 2^2a_2 + 2^3a_3 + ...

n - a_0 = 2 (...) \\ n  - a_0 - 2a_1 = 2^2 (...) \\ n - a_0 - 2a_2 - 2^2a_2 = 2^3(...) \\ ...


En fait je voulais rester sur une seule méthode sinon je pars dans tous les sens et après je me mélange les pinceaux.

Posté par
carpediemre : Entier en base deux 13-10-18 à 18:55

je ne change pas de méthode !!!

je détaille simplement ce que dit luzak ...

Posté par
Ramanujanre : Entier en base deux 13-10-18 à 19:01

Ok j'ai réussi à comprendre en réécrivant tout au propre la démonstration.

En fait je préfère l'utilisation des symboles somme c'est plus rapide pour factoriser. J'ai directement factoriser par 2^p pour faire apparaître le coefficient d_p

Posté par
Ramanujanre : Entier en base deux 13-10-18 à 20:40

La suite.

1/ On définit 2 suites d'entiers (y_k) et (d_k) par y_0 =N et pour tout entier naturel k y_{k+1} et d_k désignent respectivement le quotient et le reste de la division euclidienne de y_k par 2.

1/ On fixe k \in \N^* Exprimer N en fonction de  k,d_0,...,d_{k-1},y_k

J'ai trouvé : N=y_k 2^k + \sum_{l=0}^{k-1} d_l 2^l et j'ai démontré le résultat par récurrence.

Je bloque sur la question suivante :

2/ Démontrer que la suite (y_k) est nulle à partir d'un certain rang et qu'il existe un entier n \geq 1 tel que \bar{d_{n-1}....d_0} soit l'écriture de N en base 2.

Posté par
Ramanujanre : Entier en base deux 14-10-18 à 00:11

Finalement j'ai réussi.

Posté par
Ramanujanre : Entier en base deux 14-10-18 à 00:23

verdurin @ 12-10-2018 à 13:57

Si \bigl(U_n\bigr)_{n\in\N} est une suite d'entiers strictement croissante alors quelque soit l'entier N il existe un unique entier n tel que UnN<Un+1.


Ce théorème est-il au programme de MPSI ?

Posté par
carpediemre : Entier en base deux 14-10-18 à 00:41

c'est d'une telle trivialité ....

Posté par
Ramanujanre : Entier en base deux 14-10-18 à 00:45

Je trouve pas que ce soit trivial.

Posté par
Ramanujanre : Entier en base deux 14-10-18 à 01:01

Je bloque sur la question suivante où il faut faire un algorithme :

Ecrire un algorithme qui pour tout entier naturel N supérieur ou égal à 2 donné renvoie la suite (d_0,...,d_{n-1}) des chiffres de son écriture en base 2.

Faut juste donner l'algorithme qui donne le reste de la division euclidienne de y_0 par 2 ?

Posté par
luzakre : Entier en base deux 14-10-18 à 08:32

Je te souhaite bien du plaisir si tu veux écrire l'algorithme de division par deux vu qu'elle est cœur de tous les processeurs qui fonctionnent en numération binaire !

Comment peux-tu, à partir d'une question aussi claire que (il suffit d'une simple lecture mot à mot sans aucun commentaire)

Citation :

Ecrire un algorithme qui pour tout entier naturel N supérieur ou égal à 2 donné renvoie la suite (d_0,...,d_{n-1}) des chiffres de son écriture en base 2.

demander s'il faut écrire un algorithme de division euclidienne ?

Posté par
Ramanujanre : Entier en base deux 14-10-18 à 12:32

Après avoir testé sur un exemple N=5 je crois avoir compris le principe.

y_0 = N = 5
On va diviser y_0 par 2 et le quotient va s'appeler y_1, le reste d_0. Puis on va diviser y_1 par 2 etc... Dès que y_n=0 on s'arrête et on aura d_{n-1}

y_n = 2 y_{n+1} + d_n

Entrées :
N entier
D liste
y entier
d entier

Initialisation :
Saisir N
Saisir D vide
Affecter à y la valeur de N

Traitement :
Tant que y \ne 0
Affecter à d le reste de la division de y par 2.
Affecter à y le quotient de la division euclidienne de d par 2
Affecter à D la concaténation des valeurs de D et d

Sorties:
Afficher D

Vous pensez-quoi de mon algo ?

Posté par
luzakre : Entier en base deux 14-10-18 à 12:57

Semble tenir la route !
en principe, dans les algos, on écrit d\gets au lieu de "affecter à d"...

Posté par
Ramanujanre : Entier en base deux 14-10-18 à 13:49

D'accord

On demande quel est le nombre d'opérations (additions et multiplications) doit-on effectuer pour calculer N ?

N=\sum_{k=0}^{n-1}d_k 2^k

Il y a au plus : n-1 additions

Pour les multiplications : faut-il compter la multiplication par les d_k qui valent 0 ou 1 ? Faut-il compter la multiplication des 2 dans 2^k ?

Posté par
luzakre : Entier en base deux 14-10-18 à 15:10

Il me semble que l'énoncé impose deux procédés de calcul et veut comparer leur "coût" en nombre d'opérations !
Tu es en train de répondre à quelle question exactement ?

Posté par
Ramanujanre : Entier en base deux 14-10-18 à 16:27

VI Méthode naive

J'essaie de calculer le nombre d'opérations ....

Faut il compter une multiplication pour 1 \times 2^k ou 0 \times 2^k

Faut il compter k-1 multiplication pour 2^k ?  Ou bien la fonction puissance est intégrée ?

Posté par
luzakre : Entier en base deux 14-10-18 à 18:39

Si on te dit de compter les additions et multiplications, ta question sur la fonction puissance est infondée.
Prends toi par la main et fais des calculs "naïfs" pour des petites valeurs de n : tu verras bien...Si tu as peur de mal compter les produits pour 2^k (parce que tu aurais tendance à faire les produits de tête) fais les calculs en mettant un x pas simple (par exemple x=14) et écris une liste arbitraire de d_k moins simple que seulement des 0,1.
Bref fais comme si tu voulais calculer la valeur de P(x)=3x^+24x+37 pour x=14. Tu utilises une calculette, sans utiliser la touche "puissance", mais tu comptabilises toutes les fois où tu appuies sur les touches "multiplier, ajouter"...

Posté par
Ramanujanre : Entier en base deux 14-10-18 à 23:14

N=\sum_{k=0}^{n-1}d_k 2^k

Exemple :

Si N=5
5=1 \times 2^0 + 0 \times 2^1 + 1 \times 2 \times 2
On a n=3

On a : n-1 additions

Pour les multiplications je suis bloqué.

Posté par
luzakre : Entier en base deux 14-10-18 à 23:29

Tu as fait le calcul du polynôme que je t'ai donné ?
Compter le nombre d'appuis sur une touche de calculette te donne des boutons ?
...........................................
Compter le nombre de multiplications pour obtenir le terme d_k2^k est facile (peut-être trop ?).

Posté par
Ramanujanre : Entier en base deux 14-10-18 à 23:36

Bah votre polynôme c'est plus simple 2 multiplications et 2 additions.

Mais dans le sujet déjà faut-il compter une multiplication pour d_0 \times 2^0 alors que 2^0 = 1 ?

Posté par
Ramanujanre : Entier en base deux 14-10-18 à 23:39

Je dirais il faut : k multiplications pour obtenir le terme d_k 2^k

Exemple k=2 on a : d_2 \times 2^2 = d_2 \times 2 \times 2 soit 2 multiplications.

Posté par
Ramanujanre : Entier en base deux 15-10-18 à 00:44

J'ai 2 corrigés un corrigé dit qu'il y  a n multiplications et l'autre \dfrac{(n-1)(n-2)}{2}

Bref je suis perdu.

Posté par
luzakre : Entier en base deux 15-10-18 à 04:58

k multiplications à chaque passage dans la boucle, oui et combien de fois le fait-on sinon 1+2+\dots+n-1 fois  ?
De sorte que ni n ni \dfrac{(n-1)(n-2)}2 n'est le bon compte !

Posté par
Ramanujanre : Entier en base deux 15-10-18 à 12:20

Voilà pourquoi je me méfie des corrigés sur internet. A mon avis ils n'ont pas compter la multiplication par d_k de toute façon l'énoncé est trop vague.

Je suis d'accord avec votre réponse ça donne : \dfrac{n(n-1}{2}

Pour le suivant c'est :

N=((((d_{n-1} \times 2 + d_{n-2}) \times 2 +d_{n-3}) \times 2 + ...) \times 2 + d_0

Je dirais n-1 multiplications (de d_1 à d_{n-1}) et n-1 additions (d_0 à d_{n-2})

Vous trouvez la même chose ?

Posté par
luzakre : Entier en base deux 15-10-18 à 12:43

Je ne trouve rien puisque je n'ai rien fait mais ton compte me semble exact !

.......................................
Pour ton corrigé, s'ils n'ont pas compté le produit par d_k c'est qu'ils ont pris un autre algorithme. Mais croire que d_k\in\{0,1\} permet de "zapper " ce produit est un peu "cavalier".
Sans faire la multiplication il faudrait faire un branchement "SI" dans l'algorithme mais le compte devrait alors ajouter celui des tests et branchements (à mon avis aussi coûteux qu la multiplication).
Et puis, dans ce cas, pour quoi compter toutes les additions puisque les additions avec 0 ne "comptent pas".
Bref, je reste d'accord avec moi pour le compte définitif de \dfrac{n(n-1)}2 multiplications.

Posté par
Ramanujanre : Entier en base deux 16-10-18 à 20:37

D'accord merci

1 2 +


Rechercher
Menu
Espace membre
29 visiteurs
Changer d'île

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 1720 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 !