0

Olá, estou estou escrevendo algoritmos para numeros grandes. Implementei as operações de soma, divisão e subtração porém para o divide não tenho nenhuma ideia apenas um algoritmo para usar com base binária. Não é uma opção transformar o número para binário, quero utilizar a base 10.

Os numeros que quero dividir estão representados da seguinte maneira:

2346

|2|->|3|->|4|->|6|

É uma lista circular.

Como posso fazer?

Vou deixar o algoritmo em binario recursivo para a divisão:

funcao divide(x,y)
entrada: dois numeros inteiros de n bits x e y, onde y >= 1
saida: o quociente e o resto de x dividido por y

se x = 0 : retorn (q,r) = (0,0)
(q,r) = divide(floor(x/2),y)
q = 2*q, r = 2*r
se x é impar: r = r + 1
se r>=y: r = r - y, q = q + 1
retorna (q,r)

1 Resposta 1

0

Não entendi por que uma lista circular, mas vá lá. Como você passou pseudocódigo na pergunta, vou responder com pseudocódigo também; se depois tiver dificuldade em converter o pseudocódigo em C, posta as estruturas para que eu possa tentar fazer as correspondências.

O algoritmo é essencialmente o algoritmo que todos nós aprendemos lá no 4º ano com a Tia Loló:

função divide(x, y)
entrada: dois números inteiros e posiitivos, sendo y > 0
saída: o quociente e o resto de x dividido por y

01: se x = 0: retorne (0, 0)
02: seja ny = número de dígitos de y
03: seja x' = ny dígitos mais significativos de x
04: início do loop:
05:     seja dq = 0
06:     enquanto x' >= y, faça x' = x' - y e incremente dq
07:     concatene dq no final de q
08:     se ainda houver dígitos de x que não foram incluídos em x',
09:         concatene o próximo dígito mais significativo de x no final de x'
10:         senão saia do loop (vá para a linha 12)
11: fim do loop (vá para a linha 04)
12: retorne (q, x')

Note que o algoritmo funciona igualmente bem para listas não-circulares de dígitos, ou para vetores de dígitos BCD a quatro bits por dígito decimal.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .