Skip to main content
replaced http://pt.stackoverflow.com/ with https://pt.stackoverflow.com/
Fonte Link

A resposta do Lucas Virgiliresposta do Lucas Virgili explica bem o raciocínio por trás da pergunta (que certamente é mesmo sobre representação binária), mas gostaria de dar uma resposta um pouco mais geral:

A resposta do Lucas Virgili explica bem o raciocínio por trás da pergunta (que certamente é mesmo sobre representação binária), mas gostaria de dar uma resposta um pouco mais geral:

A resposta do Lucas Virgili explica bem o raciocínio por trás da pergunta (que certamente é mesmo sobre representação binária), mas gostaria de dar uma resposta um pouco mais geral:

Não existe nota de R$25...
Fonte Link
mgibsonbr
  • 82,6mil
  • 22
  • 186
  • 334
1c,1c,1c,1c, 5c, 10c,10c, 25c, 50c, R$1, R$2,R$2, R$5, R$10,R$10, R$25R$20, R$50, R$100...

R$44 = R$25R$20 + R$10 + R$5R$10 + R$2 + R$2
1c,1c,1c,1c, 5c, 10c,10c, 25c, 50c, R$1, R$2,R$2, R$5, R$10,R$10, R$25, R$50, R$100...

R$44 = R$25 + R$10 + R$5 + R$2 + R$2
1c,1c,1c,1c, 5c, 10c,10c, 25c, 50c, R$1, R$2,R$2, R$5, R$10,R$10, R$20, R$50, R$100...

R$44 = R$20 + R$10 + R$10 + R$2 + R$2
Fonte Link
mgibsonbr
  • 82,6mil
  • 22
  • 186
  • 334

A resposta do Lucas Virgili explica bem o raciocínio por trás da pergunta (que certamente é mesmo sobre representação binária), mas gostaria de dar uma resposta um pouco mais geral:

Quando se pega um número qualquer, no abstrato, e se representa esse número em uma base, se está justamente decompondo-o em uma série de números menores. Por exemplo:

44 = 10*4 + 1*4                            (base 10: 44)
   = 16*2 + 1*12                           (base 16: 2C)
   = 32*1 + 16*0 + 8*1 + 4*1 + 2*0 + 1*0   (base 2: 101100)

E assim por diante. No caso dos números em binário, há apenas duas possibilidades: ou o componente está presente ou não está:

1, 2, 4, 8, 16, 32,...

No caso dos números em decimal, por exemplo, cada componente pode ocorrer de 0 a 9 vezes:

1,1,1,1,1,1,1,1,1, 10,10,10,10,10,10,10,10,10, 100,100,100,100,100,100,100,100,100, 1000...

E assim por diante. Para se "montar" o número 44, pega-se 4 unidades (i.e. dentre os 9 valores 1 disponíveis pega-se 4) e 4 dezenas (dentre os 9 valores 10disponíveis pega-se 4). Nenhuma centena, milhar, etc.

Esse raciocínio vale mesmo para bases "loucas", como por exemplo: "representar uma quantia em Reais usando o menor número possível de notas/moedas":

1c,1c,1c,1c, 5c, 10c,10c, 25c, 50c, R$1, R$2,R$2, R$5, R$10,R$10, R$25, R$50, R$100...

R$44 = R$25 + R$10 + R$5 + R$2 + R$2

Método reverso

A forma mais eficiente de se resolver esse problema (representar um número dado um conjunto de componentes) é se começar pelo "maior deles" (ou, se a sequência for infinita, o maior dentre eles que for menor ou igual ao número) e percorrer a lista até o início - subtraindo-se os valores encontrados até o número chegar a zero:

entrada = 44
lista = [1,2,4,8,16,32,64,128]
maior = x in lista if x <= entrada
for y from maior to 0:
    if y <= entrada:
        incluir y na saída
        entrada -= y

Exceto pelo caso binário (onde o teste por bits é mais simples e eficiente - já que o computador te "ajuda" na tarefa com operadores binários próprios pra isso), essa seria a melhor forma de fazer, para uma entrada arbitrária [ordenada em ordem crescente, é claro].

Método direto

Lembra do primário, quando você aprendeu a fazer somas usando o QVL? O mesmo princípio pode ser utilizado, mas usando-se uma base arbitrária em vez do 10:

  • Enquanto o valor a ser atingido for maior que zero:
    • Pegue o menor valor da lista (unidade), e acrescente-o à saída - decrementando a entrada
    • Se o menor valor da lista não estiver disponível (i.e. todas as unidades foram usadas), retire N valores da saída e troque-os por um valor de grandeza maior (dezena) - de modo que N unidades + 1 unidade seja igual a 1 dezena.
    • Repita recursivamente para grandezas maiores (dezena/centena, centena/milhar, etc).

Citei esse método por curiosidade apenas, pois desnecessário dizer ele é por demais ineficiente (você estaria "contando" de 1 a 44 - complexidade O(n)), deixo a implementação em código como exercício para o leitor... :P