log binaire et registres

[invite397ab838]

Bonjour

Le logarithme binaire entier d’un entier n >0 est l’entier k tel que
2^k.< n <2^k+1

Voilà avec unemachine à registre je doit
Ecrire un programme pour la machine qui calcule dans R2 le logarithme binaire entier de l’entier contenu initialement dans
R1 . Si le registre R1 contient initialement 0, le resultat est indeterminé mais il est interdit d’utiliser l’exponentiationNB : on pourra utiliser sans plus de justification la construction
Tant que
Ri<= Rj faire I;


J'ai fait ça j'aimerais savoir si c'est juste

D'après l'énnoncer R1:n
on crée les registres suivant : R2<-0 R3<-2 R4<-1

Tant que R4<=R1 faire:
si R4<=R2 alors
++R4
R4<-R4*R3
sinon R4<-R4*R3
++R2


Ainsi à l'arivée R1 a pas bougé et on a bien R2 k non?


Est ce bon? merci d'avance
-----

[Dlzlogic]

Bonjour,
Votre utilisation du terme "registre" prête vraiment à confusion. Il faut utiliser le terme "variable"
D'autre part, ce que je crois être l'affectation d'une valeur à un variable est peu utilisée et donc difficile à lire.
Apparemment, il s'agit d'un exercice, vous verrez bien la correction.

[invite4492c379]

Bonjour

Le logarithme binaire entier d’un entier n >0 est l’entier k tel que
2^k.< n <2^k+1

Hello,

avec cette relation aucune puissance de 2 n'a de logarithme binaire entier ... Utilisons par exemple :

Voilà avec unemachine à registre je doit
Ecrire un programme pour la machine qui calcule dans R2 le logarithme binaire entier de l’entier contenu initialement dans
R1 . Si le registre R1 contient initialement 0, le resultat est indeterminé mais il est interdit d’utiliser l’exponentiationNB : on pourra utiliser sans plus de justification la construction
Tant que
Ri<= Rj faire I;


J'ai fait ça j'aimerais savoir si c'est juste

D'après l'énnoncer R1:n
on crée les registres suivant : R2<-0 R3<-2 R4<-1

Tant que R4<=R1 faire:
si R4<=R2 alors
++R4
R4<-R4*R3
sinon R4<-R4*R3
++R2


Ainsi à l'arivée R1 a pas bougé et on a bien R2 k non?


Est ce bon? merci d'avance

En indentant ton algocode :

R1 <- n
R2 <- 0
R3 <- 2
R4 <- 1
Tant que R4 <= R1 faire:
  si R4 <= R2 alors 
    ++R4
    R4 <- R4*R3
  sinon
    R4 <- R4*R3
    ++R2
  fin si
fin tant que

On remarque :
Si R4 est plus grand que R2 alors tu doubles R4 et tu incrémentes R2 ... et du coup R4 ne pourra jamais être plus petit que R2 ... ça ressemble à une boucle inifinie. Or dès le départ R4>R2, je te laisse conclure.

Passons maintenant à la partie Tips & Tricks

Il est toujours utile de tester un algocode dont on est pas sûr à la main ... Essaye de le faire tourner avec n=9 par exemple pour voir si ça a l'air de coller ...

Il est toujours utile d'écrire dans un premier temps en Français ce que tu veux faire, de faire un algo puis de le traduire en code

Il est toujours utile de bien indenter son code, de bien délimiter les conditionnelles, etc ...

Il est peut être intéressant de formuler quelques propriétés du logarithme binaire entier, notons lbe si tu veux pour la suite.

[invite4492c379]

(...)

Parfois il vaut mieux lire que de raconter des bêtise

oublie une partie de ce que j'ai baraguouiné sur la boucle infinie ...

Essaye avec n=1,2,9 ... trouves-tu les bons résultats ?

[A voir en vidéo sur Futura]

[invite397ab838]

Bonjour en effet ça marche pas mon truc et je n'ai pas de correction car c'est un controle d'une autre université que la mienne: Je repart chercher mais si je n'ai rien posté avant 19 heure, pouvez vous m'indiquer la réponse

Merci d'avance

[invite397ab838]

Je propose ça maintenant:

Si R1=R4 
    alors R2
sinon   
    tant que R1<R4 faire: 
                       si R4<=R3 alors
                          ++R4
                          R4<-R4*R3
                          ++R2
                      sinon R4<-R4*R3
                      ++R2
    Fin tant que
fin si

C'est mieux avec les balises, non?


Pour moi ça marche la non?? mais est ce que j'ai bien le droit d'écrire un inférieur strict? Car non on a toujours marqué que des inférieur ou égal en td

[invite397ab838]

désolé mais il prend pas les vides pour la présentation donc la je mets des letttrs en blancs devant pour faire les espaces


Si R1=R4 alors R2
sinon tant que R1<R4 faire:
yyyyyyyyyyyyysi R4<=R3 alors
yyyyyyyyyyyyyyyyyy++R4
yyyyyyyyyyyyyyyyyyR4<-R4*R3
yyyyyyyyyyyyyyyyyy++R2
yyyyyyyyyyyyysinon R4<-R4*R3
yyyyyyyyyyyyyyyyyyy++R2
Fin tant que
fin si


les <- c'est des affectations et initialisations

On prend toujours

R1<-n
R2<-0
R3<-2
R4<-1



ça marche ?

[Jack]

désolé mais il prend pas les vides pour la présentation donc la je mets des letttrs en blancs devant pour faire les espaces

C'est pour celà qu'il faut encadrer le code par les balises code
(voir ton message #6)

A+

[invite397ab838]

d'accord merci bien ^^ je le saurai maintenant

et c'est juste?

[invite4492c379]

d'accord merci bien ^^ je le saurai maintenant

et c'est juste?

à vue de nez je ne pense pas que ce soit bon ... as-tu fait des tests à la main ?

peux-tu juste me dire ce que tu essayes de faire avec des phrases en Français ?

[invite397ab838]

Bah en gros la si n=O le résultat est indeterminé ce qui correspond à l'énnoncer

si n=1 R1=R4 donc R2=0 R2 renvoi bien le bon k
Si n=2 R1>R4 donc on fait R4++=2 puis R4*R3 =2*2=4 et R2++=1 On recommance le test et la R4>R1 donc on stop on trouve bien R2=1
si n=3 idem
...

Qu'est ce qui cloche?

[invite4492c379]

Je n'ai que survolé le code ... le ++R4 suivi d'un R4*2 me paraît louche ...
je jette un coup d'oeil un peu plus tard et je reposterai ici ...

[invite4492c379]

Donc, comme je le rappelais dans une autre discussion, il ne sert à rien de partir d'un truc qui semble fonctionner mais pas vraiment en essayant de le modifier au petit bonheur la chance.

Une méthode simple pour calculer le lbe est par exemple :

on doit calculer le lbe de n un entier > 0
on commence avec k=0

on calcule 2^k
si n>=2^k alors on continue
sinon 2^k est le premier trop grand alors la réponse est k-1
on reccommence trois lignes au-dessus

Un problème potentiel : on peut dépasser la limite matérielle de la représentation des entiers.

Si on prend le problème autrement, le lbe est tout simplement la position du bit à 1 le plus significatif (avec un +1 suivant la manière de numéroter) ... une idée comment le trouver ?

[invite397ab838]

désolé je sais pas ce que c'est qu'un bit à 1 ...

[invite4492c379]

Alors reprend l'explication au-dessus et essaye de le faire à la main puis de décrire ce que tu fais ...