Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Crie um algoritmo que apresenta a soma dos bits menos significantes de todos os números de \((1,n^2-1)\) contando do primeiro começando do final do número em binário.

0 votos
30 visitas
perguntada Nov 3 em Ciência da Computação por Fábio Springer (11 pontos)  
editado Nov 3 por Fábio Springer

Crie um algoritmo que apresenta a soma dos bits menos significantes de todos os números de \((1,n^2-1)\) contando do primeiro começando do final do número em binário. Isso é, sabendo que a representação binária dos três primeiros números é:
0001, 0010 e 0011 e n = 2 algoritmo deve retomar 5. Caso n= 4 esperamos como resposta 26. A figura representa o objetivo do algoritmo.
A imagem será apresentada aqui.

Exercício retirado do livro introduction to recursive programing de Manuel Rubio-Sanchez. Cap 3, ex 3.8

Compartilhe

1 Resposta

0 votos
respondida Nov 3 por Fábio Springer (11 pontos)  
editado Nov 8 por Fábio Springer

Para resolver a exercício sugiro uma aproximação direta em três passos:
1) Criar uma função que converte o número pedido para o formato binário
2) Criar uma função que dado n cria uma lista com ops números em binário e gravados com string.
3) Criar uma recursão que soma 1 cada vez que não encontra o número 1 como elemento final de um elemento da lista. Em seguida avança para o proximo componente e casso esse componente seja igual a 1 encera a recursão.

Perceba que um fato particular de responder esse exercício em python é que a função range não inclui o último valor, range(1, \(n^2\) ) equivale a 1 até \(n^2-1\) na linguagem python.

O algoritmo em python a seguir contempla essas passo:

# Retorna os "least significant bits" binários de um dado numero
def binary(num):
    return int(bin(num).split('0b')[1])

# Cria a lista com a representação binária
def creat_list(n):
    bin_list = []
    for i in range(1, (n**2)):
        bin_list.append(str(binary(i)))
    return bin_list

# O numero de interaçõers é o valor pedido
def cont(n):
    interactions = 1
    total_interactions = 0
    for element in creat_list(n):
        for number in element [ : :-1]:
            if number == "1":
                total_interactions += 1
                break
            else:
                interactions += 1
    return total_interactions

Depois basta rodar o código:

if __name__ == "__main__":

cont(2)
cont(4)

E de fato obtemos o resultado esperado.

comentou Nov 6 por bonfim_tiago (6 pontos)  
Em primeiro lugar, gostaria de te parabenizar pelos códigos gerados! Os códigos são extremamente intuitivos, modularizados e concisos.
   Tendo isso em vista, os comentários que eu vou fazer aqui devem ser encarados como oportunidades de aprimoramento somente, não sendo nada grave.
    Bom, eu senti falta de alguns comentários pelo código. Ainda que o código seja extremamente intuitivo, eu acredito que documentar, por exemplo, a declaração de funções pode ser uma prática muito importante na manutenção futura desse programa. Uma breve descrição da funcionalidade da função e dos parâmetros de entrada e saída bastaria. A título de exemplificação, cito aqui a função "def creat_list(n):" onde o parâmetro "n" poderia ter a sua interpretação muito facilitada pela adição de alguns poucos comentários.
   Por fim, uma prática que eu venho adotando no Python há algum tempo consiste em apresentar o tipo esperado do dado quando da declaração dos parâmetros de entrada de uma função. Por exemplo, poderia ser a declaração de uma variável do tipo int como "a: int" ao invés de somente "a". Isso pode não fazer nenhuma diferença para o Python, mas confere um nível muito interessante de legibilidade aos códigos. Por isso, a recomendação.

   No mais, parabéns e um grande abraço!
...