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

Soma total de bits para um algorítimo - IRP, Ex. 8.4.

+1 voto
94 visitas
perguntada Abr 2, 2018 em Ciência da Computação por Pedro Campelo (46 pontos)  
editado Abr 2, 2018 por Pedro Campelo

"3.11) Um algorítimo processa alguns de uma representação binária de 1 até (2^(n) − 1), onde n é o número de bits de cada número. Em particular, o algorítimo processa pelo menos os bits significantes de cada número (da direita para a esquerda), até que ache o número 1. Dado n, determine, usando soma, o número de bits que o algorismo processa. Por exemplo, para n=4, o número total de bits é 26."

8.4) Resolva o problema 3.8 usando uma abordagem recursiva e desenhe o a figura original do problema 3.11.

A questão acima é a questão 8.4 do livro "Introduction to Recursive Programming" de Manuel Rubio Sánches.

Compartilhe

1 Resposta

+1 voto
respondida Abr 2, 2018 por Pedro Campelo (46 pontos)  

Para

n=0 -> somabits=0
n=1 -> soma
bits=1
n=2 -> somabits=4
n=3 -> soma
bits=11
n=4 -> soma_bits=26

Deste modo, podemos achar a equação de soma_ bits(n) em função de soma_bits(n-1). Deste modo:

somabits(0)=0
somabits(1) = (2 * 0) + 1 = 2*somabits(0) + 1
somabits(2) = (2 * 1) + 2 = 2*somabits(1) + 2
somabits(3) = (2 * 4) + 3 = 2*somabits(2) + 3
somabits(4) = (2 * 11) + 4 = 2*somabits(3) + 4

somabits(n) = 2*somabits(n-1) + n

Assim, para achar a soma de bits no Python:

def soma_bits(n):
    if (n==1):
        return 1
    else:
        return (2*soma_bits(n-1)+n)

Alguns exemplos:

soma_bits(3)
Out: 11

soma_bits(7)
Out: 247

Agora para criar a tabela, primeiro definimos uma função que retorna todas as combinações binárias possíveis para um determinando n, eliminando a primeira linha de (0,0,0....n). Assim:

import itertools
import numpy as np

#matriz(2^n - 1 linhas e n colunas) que retorna a permutação de n  

def bin_perm(n): 
    lista=0
    lista=np.array(list(itertools.product([0, 1], repeat=n)))
    lista=np.delete(lista, (0), axis=0)
    return lista

Obtendo o resultado para n=4:

bin_perm(4)
Out: 
array([[0, 0, 0, 1],
       [0, 0, 1, 0],
       [0, 0, 1, 1],
       [0, 1, 0, 0],
       [0, 1, 0, 1],
       [0, 1, 1, 0],
       [0, 1, 1, 1],
       [1, 0, 0, 0],
       [1, 0, 0, 1],
       [1, 0, 1, 0],
       [1, 0, 1, 1],
       [1, 1, 0, 0],
       [1, 1, 0, 1],
       [1, 1, 1, 0],
       [1, 1, 1, 1]])

Em seguida, use o resultado acima para criar a tabela desejado com a ajuda do plotly:

import plotly
import plotly.plotly as py
from plotly.offline import init_notebook_mode
import plotly.figure_factory as ff
plotly.offline.init_notebook_mode(connected=True)


table_data = [["Coluna 1", "Coluna 2","Coluna 3", "Coluna 4"],
              [0, 0, 0, 1],
               [0, 0, 1, 0],
               [0, 0, 1, 1],
               [0, 1, 0, 0],
               [0, 1, 0, 1],
               [0, 1, 1, 0],
               [0, 1, 1, 1],
               [1, 0, 0, 0],
               [1, 0, 0, 1],
               [1, 0, 1, 0],
               [1, 0, 1, 1],
               [1, 1, 0, 0],
               [1, 1, 0, 1],
               [1, 1, 1, 0],
               [1, 1, 1, 1]]

figure = ff.create_table(table_data)
plotly.offline.plot(figure)

E a imagem gerada é:

A imagem será apresentada aqui.

comentou Abr 6, 2018 por danielcajueiro (5,696 pontos)  
Pedro, vc não pode anexar a figura que você gerou?
comentou Abr 7, 2018 por Felipe Carneiro (76 pontos)  
editado Abr 9, 2018 por Felipe Carneiro
Pedro, caso você esteja com dificuldades para anexar uma imagem, basta escolher-la a partir de seu próprio computador clicando no ícone referente a anexo de imagens. Depois clique em upload.
Se não conseguir, acredito que seja possível que faça o upload da imagem no https://imgur.com/ e depois cole o seu link no corpo da resposta.
comentou Jun 26, 2018 por Felipe Carneiro (76 pontos)  
Pedro, parabéns, a implementação ficou muito boa.

Creio que também seja possível implementar esse problema recursivo através de um 'for'.
Segue tentativa de implementação:

import numpy as np

def bin_perm(n):
    lista=0
    lista=np.array(list(itertools.product([0, 1], repeat=n)))
    lista=np.delete(lista, (0), axis=0)
    return lista



def sum_bits(n):
     lista=bin_perm(n)
      aux=[]
     if (n==1):
         return 1
     else:
     for p in range (1,n+1):
         for i in range(0,linhas+1):
             while (lista[i][n-p]==1):
                 return p
         aux.append(p)
         return aux
...