Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 03-05-2020 15:34:56

Mouss
Membre
Inscription : 23-04-2020
Messages : 105

Algorithmique

Bonjour,

J'ai un exercice à faire mais je ne comprends pas. Voici l'algorithme.

Définir secret(x,y)
     Tant que x est non nul faire
          Si x est pair alors
                x = x/2
                y = 2y
          Sinon
                x=x-1
                z=z+y
         Fin si
      Fin tant que
Afficher z

Je ne comprends pas l'algorithme, je ne sais pas ce que fait la fonction secret et je ne comprends pas non plus pourquoi z=z+y.

merci pour votre aide

Hors ligne

#2 03-05-2020 16:26:26

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 947

Re : Algorithmique

Re,

1. Peut-être pourrais-tu nous dire ce qu'on attend de toi ?...
2. Cet algorithme est incorrect ; quel que soit le langage dans lequel je le traduirais, il déclencherait un message d'erreur.
    En effet pour pouvoir calculer z = z+y, il faut déjà connaitre une valeur pour z...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#3 03-05-2020 17:09:16

Mouss
Membre
Inscription : 23-04-2020
Messages : 105

Re : Algorithmique

Dans l'exercice on me demande de completer la dernière ligne du tableau suivant à l'aide de l'algorithme :

X      2         5           2           100          5
Y      3         15        -8           0,01         2,3
Z

Et deuxième question : que fait cette fonction ?

Hors ligne

#4 03-05-2020 18:21:48

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 947

Re : Algorithmique

Je regrette mais sans une valeur de départ de z, c'est impossible...
Voilà traduit en Python, ton algorithme :

def secret (x,y):
    z=0
    while x>0:
        if x%2==1: # si x impair
            x=x-1
            z=z+y    
        else:      # si x pair
            x=x/2
            y=y*2    
    return z

J'ai fixé z à 0, comme ça j'ai cru pouvoir comprendre ce que fait cet algo...
Et bien... je ne sais pas ! Mais j'ai peut-être une piste et ça m'apparaît bien compliqué pour des débutants en algorithmique...

Par contre, voilà ce qui arrive si je ne commence pas avec une valeur de z :

def secret (x,y):
    while x>0:
        if x%2==1: # si x impair          
            x-=1
            z+=y
        else:      # si x pair
            x/=2
            y*=2  
    return z

>>> secret(2,3)
Traceback (most recent call last):
  File "<pyshell#38>", line 1, in <module>
    secret(2,3)
  File "<pyshell#37>", line 5, in secret
    z+=y
UnboundLocalError: local variable 'z' referenced before assignment

Traduction de la dernière ligne :
la variable locale z utilisée avant qu'on lui ait fixé une valeur...
Tu vois : j'ai raison !

Donc je fixe z=0 puisque z n'est modifié que par addition de y : de cette façon je n'influe pas sur le résultat...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#5 03-05-2020 18:49:47

Mouss
Membre
Inscription : 23-04-2020
Messages : 105

Re : Algorithmique

C'est dans mon livre d'algo de 2nde.

J'ai également tester l'algo avec z=0 et je constate que ca me renvoie le produit de x et y.

Mais du coup pourquoi ce long programme difficile pour moi à comprendre seulement pour calculer un produit (s'il sagit de çà) ?

Hors ligne

#6 03-05-2020 19:12:59

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 947

Re : Algorithmique

Re,

Tu as raison, sur ce plan là, j'ai fait nawak :
pour mes tests j'avais écrit y=y+2...
Après correction et remplissage du tableau il y a bien une multiplication mais pas que ça...
Si la valeur de départ de z est $z_0$, le z retourné est $z=z_0+x\times y$
Teste successivement les valeurs du tableau avec comme valeur de départ z=-3,2,-5 et 7, tu verras...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#7 03-05-2020 19:58:29

Mouss
Membre
Inscription : 23-04-2020
Messages : 105

Re : Algorithmique

Je viens de tester avec des valeurs non nulles pour z, en effet je fais le meme constat. Merci.

Mais du coup, il y a bien une erreur dans l'exercice ils devaient ajouter z=0 dans l'algorithme écrit en langage naturel ?

et pourquoi pour multiplier deux nombres d'après l'algo il faut dissocier nombre pair et impair?

Hors ligne

#8 04-05-2020 14:08:28

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 947

Re : Algorithmique

Bonjour,

Alors, il faut comprendre ce qui se passe : y peut être n'importe quoi, x est obligatoirement un entier (même relatif) :
si est pair on peut le diviser par 2, un impair non, c'est pourquoi on soustrait un pour revenir à un nombre pair...
Si
- n impair on fait donc x-1 et z=r+y
- n pair on fais x=x/2 et y= y *2,
Les calculs se termineront toujours avec x=1 parce que 2/2 =1...
Prenons x=16 et y=5  avec z=0 on attend 5  * 16 = 80
16 /2 =8  y --> 10  $(5 \times 2)$
  8/2 = 4  y --> 20  $(10\times 2 =5 \times 2^2)$
  4/2 = 2  y --> 40  $(20\times 2 =5 \times 2^3)$
  2/2 = 1  y --> 80   $(40\times 2 =5 \times 2^4)$
  1-1 = 0  z --> 80
$16 = 2^4$ donc $y--> 5 \times 2^4$

Et si je prends x = 24 et y=5
$24 =2^3 \times 3$
24/ 2 = 12   y --> 10   $(5 \times 2)$
12/2  =  6    y --> 20   $(10\times 2  = 5 \times 2^2)$
  6/2  =  3    y --> 40   $(20\times 2  = 5 \times 2^3)$
3 - 1  = 2    z --> 40 
2/2   =1     y --> 80   $  (40\times 2 =5 \times 2^4)$
1 - 1  =0   z --> 120  $(40+80 = 5 \times 2^3 +5\times 2^4 = 5\times 2^3\times 3)$ 3 = 1+2 factorisation

A cause du 3  on va avoir une interruption avec y =40 puis une reprise et une 2e interruption y avec y=80 et z aura été abondé de 40 puis de 80 ce qui donne 120 pour z.
x devenu impair : interruption.  On ajoute y à z et on soustrait 1 à x qui devient pair
x pair on reprend les divisions par 2 et on reprend les multiplications de y par 2, jusqu' à l'interruption suivante où on va ajouter y à z...

C'est bon pour de la programmation...
Sauf cas particulier de x puissance de 2, à la main, il faudrait prévoir
- le nombre d'interruptions
- le nombres de divisions par 2 au total avec celles dues au x=x-1 qui force x à redevenir pair suite à une interruption...
J'essaierai à mes moments perdus de voir si c'est faisable...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#9 05-05-2020 13:55:35

Mouss
Membre
Inscription : 23-04-2020
Messages : 105

Re : Algorithmique

Merci beaucoup ! je comprends mieux l'algo mais c'est comme même difficile je trouve.
Et jai du mal comprendre l'interet car pour multiplier deux nombres, on n'a pas besoin d'un algorithme ?!

J'ai fait quelques recherches sur internet et j'aimerais savoir si cet algorithme a un rapport avec la methode egyptienne de multiplication ou alors l'algorithme de karatsuba ?

Hors ligne

#10 05-05-2020 16:23:18

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 947

Re : Algorithmique

\;salut,

Je ne suis pas loin de la solution
avec x=147 y=1  et z=0
DAns la première colonne sont les x successifs :
La 2e colonne donne les restes successifs dans la division par 2, la 4e colonne les x après traitement (soit x//2, soit x-1), les deux autres l'évolution de y et celle de z quand il change...


147 1  -->  146   1   1
146 0  -->   73   2
 73 1  -->   72   2   3
 72 0  -->   36   4
 36 0  -->   18   8
 18 0  -->    9  16
  9 1  -->    8  16  19
  8 0  -->    4  32
  4 0  -->    2  64
  2 0  -->    1 128
  1 1  -->    0 128 147
>>>

Ça  ressemble beaucoup à un traitement binaire (147 --> 10010011) en partant de la fin :


1 *   1  =   1
1 *   2  =   2
0 *   4
0 *   8
1 *  16  =  16
0 *  32
0 *  64
1 * 128  = 128
          -----
   Total = 147

Dans un octet, il y a 8 cases (bits) qui ne sont occupées par 0  ou  1.
La valeur de la case est multiplie de gauche à droite par
$\;\;2^7\;\;|\;\;2^6\;|\;\;2^5\;|\;\;2^4\;|\;2^3\;|\;\;2^2\;|\;2^1\;\;|\;2^0$
c'est à dire
$128\;\;|\;64\;|\ 32\;|\;\; 16\;|\; \;\; 8\;|\; \;\; 4 \;|\; \;\; 2\;|\; \;\; 1$

Je vais aller voir tes algos...
Connais-tu la multiplication arabe  ?
34578*273 = 9439794
https://www.cjoint.com/c/JEfpvPAcqIW

Si j'en crois ce site :
http://therese.eveilleau.pagesperso-ora … egypte.htm
C'est la multiplication égyptienne en plus délayé et compliqué : je l'ai donc retrouvée avec ma décomposition en binaire...
@+

Dernière modification par yoshi (05-05-2020 16:42:12)


Arx Tarpeia Capitoli proxima...

Hors ligne

#11 07-05-2020 13:54:30

Mouss
Membre
Inscription : 23-04-2020
Messages : 105

Re : Algorithmique

Merci, j'ai réussi à faire le lien entre la multiplication égyptienne que vous m'avez envoyé en lien et vos explications, du coup si on utilise cet algo ça réduit les calculs je suppose ?! car si on crée un algo qui multiplie deux nombres juste sur la base d'additions (ex: 3*5 ça revient a 5+5+5) ça nécessiterait plus de calculs ?!

Pour ce qui est de l'as multiplication arabe, jamais entendu parlé. Pas trop compris le principe.

Hors ligne

#12 12-07-2020 11:32:37

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 947

Re : Algorithmique


Arx Tarpeia Capitoli proxima...

Hors ligne

Pied de page des forums