Preciso desenvolver um algoritmo em VisuAlg onde eu entro com um número e ele me diz se é potência de 2 ou não. Quais estratégias posso usar?
6 Respostas
Divide sucessivamente o teu x número por 2.
Se o resto for sempre 0 e chegares ao quociente 1 é porque x é uma potência de 2.
Exemplo:
8192/2 = 4096
4096/2 = 2048
2048/2 = 1024
1024/2 = 512
512/2 = 256
256/2 = 128
128/2 = 64
64/2 = 32
32/2 = 16
16/2 = 8
8/2 = 4
4/2 = 2
2/2 = 1
8192 é uma potência de 2.
A forma mais eficiente é verificar se o número-1 termina em 1111...
em binário. Em JavaScript isto é:
function isPowOf2(v){
return v && !(v & (v - 1));
}
var test = [0, 1, 2, 4, 6, 8];
for(var i = 0; i < test.length; ++i){
console.log(test[i] + " - " + isPowOf2(test[i]));
}
Aplicando para 8 pode-se ver o que está acontecendo matematicamente.
v = 8 = b1000 = true
v - 1 = 8 - 1 = 7 = b0111
8 & 7 = b1000 & b0111 = 0
!(8 & 7) = !(0) = true
v && !(8 & 7) = true
Q.E.D
-
-
Eu apreciaria de ver dois exemplos, se você não se importar: 8 e 6, que deveriam retornar verdade e falso respectivamente, em termos das operações de bits realizadas. Não estou conseguindo enxergar a corretude de sua resposta, não consigo simular os bits sem papel ou computador à mão 30/10/2017 às 2:14
-
O pessoal no chat me tirou a dúvida é consegui enxergar. Caso alguém mais esteja com dificuldades: chat.stackexchange.com/transcript/11910/2017/10/30/0-3 30/10/2017 às 2:43
-
@Marconi Só uma correção no código, de acordo com o post no link stackoverflow.com/a/600306/1377664 : se
v
for0
, irá retornar true, mas0
não é potência de2
, logo, deveria serreturn (x != 0) && ((x & (x - 1)) == 0);
@JeffersonQuesado– Meu ovo30/10/2017 às 12:45 -
1@DvD O meu código faz a mesma coisa. Pelo menos, em javascript, uma vez que se v for 0, o resultado é 0, que é um false value. Isso também foi explicado no chat apontado pelo Jefferson. Já agora essa nao foi a minha fonte da resposta e já me esqueci onde a vi, senao até punha o link. 30/10/2017 às 13:02
Para este caso basta aplicar uma única fórmula:
Log Valor / Log 2.
Se o resultado for um número inteiro então o Valor informado tem como base a potência de 2.
EXPLICAÇÃO MATEMÁTICA
Temos que 2 à potência de x é igual a y, onde y é o número que você quer saber se a base é igual a 2, e x é a potência de 2 que resultará em y.
Pelas propriedades da matemática, e em particular a dos logaritmos, a solução abaixo se apresenta.
Atenção: Não arredonde os valores como estão apresentados neste exemplo, senão o resultado não será um valor inteiro!!!
Assim, sem arredondar valores, verifique se o resultado não apresenta casas decimais (número inteiro), e quando não apresentar, saberá que este valor é formado por potência de base 2. Boa sorte!
-
2Complexo, porém, muito interessante, ainda mais por ser um conceito envolvendo logaritmo, que por muitos acharem um calculo "chato", é ignorado. +1– user285951/06/2016 às 2:47
-
3Apesar de ser complexa a explicação, a solução tem como base uma única fórmula para se verificar se o resultado é um número inteiro, ou seja, não se trata nem de um algoritmo, é uma simples aplicação de fórmula. Veja o que a matemática pode fazer por nós...– Leo1/06/2016 às 4:02
-
Devido ao cálculo inerentemente inexato do logaritmo em ponto flutuante (como é o caso da maioria das linguagens de programação e eu creio que seja o caso do VisuAlg), essa solução pode vir a ter alguma falha. Devido à representação numérica, claro, não falha matemática 30/10/2017 às 2:11
Divida o número por dois, até que o resto da divisão seja menor ou igual a 1 (use um loop para isso)
- Se o resto da divisão for igual a 1 o número é potencia de 2
- Se o resto da divisão for menor que 1 o número não é potencia de 2
-
1Pois bem, entendi, até ai, mas agora como vou montar um algoritmo em VisualG que faça isso? pois este ainda é um problema! qual metodo posso utilizar para resolver este problema?– AGenaro1/06/2016 às 18:10
-
Com o algoritmo e uma apostila de VisualG você poderá resolver o seu problema sem dificuldade alguma... E o que temos aqui: www2.joinville.udesc.br/~alp/arquivos/… 2/06/2016 às 14:06
eu criei uma função em c++ que verifica se um número é potência de 2 usando logaritimo de base 2. EXPLICACÃO: calcula-se o logaritmo na base 2 do número dado e tudo que temos que fazer é verificar se o resultado desse cálculo é um número inteiro, para verificar se um numero é interio basta colocar esse numero numa variável inteira X e colocá-lo também numa variável real Y. Se o diferença de X e Y for 0 então o resultado é interio que significa que o número é uma potência de 2, senão então o número não é uma potência de 2.
#include<bits/stdc++.h>
using namespace std;
class Solution{
public:
// Function to check if given number n is a power of two.
bool isPowerofTwo(long long n){
//declaring variables that will help to check if the result of the log is an integer
int i=0;
long double x=0;
//then a put the result of the log in an integer and the same result in a long double variable
i=log2l(n);
x=log2l(n);
//now we subtract the two results
//if the subtraction is 0 then the number is a power of two
if(x-i==0)return true;
//if no, the number is not a power of two
else return false;
// real simple.
}
};
"""
Ejercicio 5.7.6. Potencias de dos.
a) Escribir una función es_potencia_de_dos que reciba como parámetro un número
natural,y devuelva True si el número es una potencia de 2, y False en caso contrario.
b) Escribir una función que, dados dos números naturales pasados como parámetros, devuelva la
suma de todas las potencias de 2 que hay en el rango formado por esos números
(0sinohayningunapotenciade2entrelosdos).Utilizarlafunción es_potencia_de_dos ,
descripta en el punto anterior.
"""
import os
def clear():
""" cls de windows """
os.system('cls' if os.name == 'nt' else 'clear')
def pausar():
""" pausa de windows"""
os.system('pause')
def es_potencia_de_dos(numero):
""" Verifica si es potencia de dos, en primera instancia descartamos el 1 , que
seria 2 a la 0 luego vemos si podemos componer el numero que tenemos
como potencia de dos y de paso devolvemos que potencia de dos es , en caso de
serlo """
if numero == 1:
return True, 0
r = 1
for i in range(1, numero):
r *= 2
if r == numero:
return True, i
else:
continue
return False
def leer_numero():
return input('\nIngrese el numero que desea verificar (* para salir) ')
x = leer_numero()
while x != '*':
potencia, cual = es_potencia_de_dos(int(x))
if potencia:
print('Es potencia, 2 a la ', cual)
else:
print('No es potencia de dos')
x = leer_numero()
clear()
print('Hasta luego..')
os.system('pause')
-
2Olá Lucas, podes traduzir a repsota para português? E já agora explicar qual a ideia de ter ` Ejercicio 5.7.6.` na resposta? Copiaste a resposta de algum lado?– Sergio23/02/2019 às 20:21