Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
Discussion fermé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 948
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 948
Re : Algorithmique
Je regrette mais sans une valeur de départ de z, c'est impossible...
Voilà traduit en Python, ton algorithme :
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 948
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 948
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 948
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 948
Re : Algorithmique
Arx Tarpeia Capitoli proxima...
Hors ligne
Pages : 1
Discussion fermée