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

Question

"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.

Answer 1

Para

n=0 -> somabits=0
n=1 -> somabits=1
n=2 -> somabits=4
n=3 -> somabits=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 é:

Comments

Pedro, vc não pode anexar a figura que você gerou?

---

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.

---

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