O mdc (m´aximo divisor comum) de dois n´umeros inteiros a e b (onde a ≥ b ≥ 0)
O mdc (m´aximo divisor comum) de dois n´umeros inteiros a e b (onde a ≥ b ≥ 0) pode ser calculado pelo seguinte algoritmo recursivo: fun¸c˜ao mdc(a, b) se b = 0 ent˜ao retorne a sen˜ao retorne mdc( b, a mod b ) (No algoritmo acima, “a mod b” ´e o resto da divis˜ao de a por b.) Descreva uma vers˜ao iterativa do algoritmo acima. Calcule a complexidade de pior caso do seu algoritmo (n´umero m´aximo de itera¸c˜oes realizadas) em fun¸c˜ao de a e b (use a nota¸c˜ao O).
💡 1 Resposta
Ed 
Aqui está uma versão iterativa do algoritmo para calcular o MDC (Máximo Divisor Comum) de dois números inteiros a e b, onde a ≥ b ≥ 0: ``` função mdc(a, b): enquanto b ≠ 0: resto = a % b a = b b = resto retorne a ``` A complexidade de pior caso desse algoritmo é O(log b), onde b é o menor dos dois números. Isso ocorre porque a cada iteração, o valor de b é reduzido pela metade aproximadamente. Portanto, o número máximo de iterações é proporcional ao logaritmo de b na base 2.
Faça como milhares de estudantes: teste grátis o Passei Direto
Esse e outros conteúdos desbloqueados
16 milhões de materiais de várias disciplinas
Impressão de materiais
Agora você pode testar o
Passei Direto grátis
✏️ Responder
Para escrever sua resposta aqui, entre ou crie uma conta.
Compartilhar