8

Estou usando javascript para minha lógica:

Tenho uma sequencia de números: 1, 2, 4, 8, 16, 32 e assim vai. Dado um numero, cuja precisa ser a soma de números da sequencia, por exemplo: 44 (do qual o valor é a soma do 4+8+32). Como eu sei que o numero 44 é a soma do 4, 8 e 32?

Andei pesquisando, e pensei usar radiciação. Alguém tem alguma sugestão de como descobrir o numero?

2
  • Um algoritmo do gênero poderia retornar o valor 4+8+16+16? Commented 11/07/2014 às 17:08
  • nao. eles nao podem se repetir
    – fsi
    Commented 11/07/2014 às 17:10

3 Respostas 3

13

Lembre-se que um numero no PC e representado em binario, ou seja, base 2. O que isso quer dizer e que o numero ja e uma soma de potencias de 2 quando esta no computador.

Um exemplo:

44 = 1 x 2^5 + 1 x 2^3 + 1 x 2^2
   = 32 + 8 + 4

Logo, indo da direita para a esquerda, 44 em binario e 101100. Assim, para saber qual e a decomposicao de qualquer numero em potencias de 2 nos precisamos ver quais sao os bits ligados na sua representacao em base 2.

Em javascript nos podemos fazer isso usando o seguinte algoritmo:

Passo 1) Vemos se o bit mais a direita do numero e um 1
Passo 1.1) Se for, marcamos a potencia correta de 2 como presente
Passo 2) Nos dividimos o numero por 2, o que vai fazer com que o bit mais a
         direita do numero seja descartado.
Passo 3) Se o numero for 0, pare.

Logo, algo assim:

n = 44;
power = 0;
var fatores = []
while (n != 0) {
    if ((n & 1) != 0) { 
        fatores[fatores.length] = (1 << power);
    }
    ++power;
    n >>>= 1;
}
6

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$20, R$50, R$100...

R$44 = R$20 + R$10 + R$10 + 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

3
  • Argh, editaram o título da pergunta enquanto escrevia minha resposta, agora ela não se aplica mais à pergunta... Favor levar isso em consideração antes de dar downvote :P
    – mgibsonbr
    Commented 11/07/2014 às 17:55
  • Ainda se aplica, e o conteúdo é bom. +1 =)
    – OnoSendai
    Commented 11/07/2014 às 18:00
  • 2
    Também acho que ainda se aplica, mas se conseguir pensar em um título melhor vá em frente e edite também :)
    – bfavaretto
    Commented 11/07/2014 às 18:13
4

Tenho uma sequencia de numeros: 1, 2, 4, 8, 16, 32 e assim vai

Por 'assim vai', estou assumindo que sua sequência representa potências de 2:

20 = 1
21 = 2
22 = 4
23 = 8
24 = 16
25 = 32

Posso inferir, então, que os próximos números são:

26 = 64
27 = 128
28 = 256
[...]

Dispositivos digitais fazem uso de uma estrutura chamada Bit para armazenar dados. Um bit sozinho pode apenas expressar um estado binário (0/1, verdadeiro/falso, sim/não), mas um grupo deles pode expressar um valor numérico se interpretado como presença ou não de um valor na sua sequência de potências de 2:

Posição            87654321
Mapa de bits       01011011
Valores decimais   |||||||\_ 1
                   ||||||\__ 2
                   |||||\___ (desligado)
                   ||||\____ 8
                   |||\_____ 16
                   ||\______ (desligado)
                   |\_______ 64
                   \________ (desligado)
                ----------------
Total                        91

Qualquer número em base decimal pode ser interpretado dessa forma. Assim, para descobrir que mapa de bits compõe um determinado número decimal, você pode utilizar a seguinte função JavaScript:

parseInt(numero, 10).toString(2);

Se você utilizar 44 na posição do parâmetro numero, seu retorno será o seguinte:

101100

Que indica, exatamente, os bits relativos aos valores 32, 8 e 4.

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 .