283
edições
Algoritmo de Euclides estendido (editar)
Revisão das 13h25min de 4 de setembro de 2013
, 4 de setembro de 2013Inseri um exemplo do algoritmo em Javascript
m (Bot: A migrar 10 interwikis, agora providenciados por Wikidata em d:Q1362750) |
(Inseri um exemplo do algoritmo em Javascript) |
||
|
'''MDC(120,23)''' = <math>120*(-9) + 47*23</math>
== O algoritmo ==
Uma implementação do algoritmo em [[JavaScript]]:
Voici un example en '''Javascript:'''
<syntaxhighlight lang="javascript">
/*********************************************
* Recebe dois inteiros não negativos a e b
* e devolve um vetor cuja primeira posição
* é o mdc(a,b), a segunda posição é o valor u
* e a terceira o valor v tais que
* a*u + b*v = mdc(a,b)
**********************************************/
function euclides (a, b){
var r = a;
var r1 = b;
var u = 1;
var v = 0;
var u1 = 0;
var v1 = 1;
var rs, us, vs, q;
while (r1 != 0){
q = parseInt (r / r1);
rs = r;
us = u;
vs = v;
r = r1;
u = u1;
v = v1;
r1 = rs - q *r1;
u1 = us - q*u;
v1 = vs - q*v1;
}
return [r, u, v]; // tais que a*u + b*v = r et r = pgcd (a, b)
}
</syntaxhighlight>
== Referências ==
| |||