Máximo divisor comum

De GNU Octave
Ir para: navegação, pesquisa

O Octave já tem uma função que nos calcula o máximo divisor comum, designada gcd. No entanto, vamos escrever uma nova função baseada no Algortimo de Euclides.

Veja na animação disponível na Wikipédia que o algoritmo consiste em subtrair ao maior o menor, e assim sucessivamente, até que ambos sejam iguais.

Primeira versão

a = 252
b = 105
while (a!=b)
	if (a>b)
		a=a-b
	else
		b=b-a
	endif
endwhile
disp(a)

Execução

>>> euclides
a =  252
b =  105
a =  147
a =  42
b =  63
b =  21
a =  21
 21
>>>

Programa completo:

a = input('a?');
b = input('b?');
while (a!=b)
	if (a>b)
		a=a-b;
	else
		b=b-a;
	endif
endwhile
disp(a)

Como é pedida uma função, vamos ter que usar a sintaxe própria das funções. Vamos dar-lhe o nome mdc, que não está a ser utilizado. A função tem que ser guardada num arquivo mdc.m.

function s = mdc(a, b)
% mdc(a,b) 
%	Calcula o máximo divisor comum de dois números
% 	O cálculo é efetuado segundo o algoritmo de Euclides
while (a!=b)
	if (a>b)
		a=a-b;
	else
		b=b-a;
	endif
endwhile
s = a;

Ao invocar a função, passam-se os argumentos.

>>> mdc(24,36)
ans =  12
>>> mdc(18, mdc(24,36))
ans =  6
>>>