-2

Preciso fazer um pseudocódigo que tem numero1 e numero2 (tem que ser numeros naturais menores que 50), preciso elevar o numero1 ao numero2, apenas usando a operação de multiplicação, e mostrar o resultado. Como faço?

1

3 Respostas 3

2

Você deseja fazer a exponenciação de dois números naturais? Por sorte, eu já tratei de um problema recentemente que envolvia calcular a exponencial de dois números reais. Para isso, precisei da definição de exponenciação, que é dada usando expoente natural não nulo e, só depois da definição, é extrapolado para todos os outros números. Vale a pena conferir a resposta dada, é engrandecedora e trata de diversos assuntos matemáticos.

Na outra resposta, defini exponenciação assim:

A exponenciação natural é igual direta ao ponto (desconsidere o 0 como natural agora). O expoente indica quantas vezes você deve multiplicar a base no seguinte algoritmo [para a forma b^n]:

  1. se n == 1, retorne b
  2. caso contrário, retorne b * b^(n-1)

Isso pode ser transformado em pseudocódigo assim (usando Python como base):

def pow(b, n):
  if n == 1:
    return b
  else:
    return b*pow(b, n-1)

Em um dialeto mais pythônico:

def pow(b, n):
  return b if n == 1 else b*pow(b, n-1)

Então com uma simples recursão resolveríamos o problema, certo? Na verdade, ainda é necessário aparar algumas arestas. A primeira é o caso do 0. Na reposta citada no começo desta aqui eu explico como se chega na convenção de que qualquer número diferente de 0 elevado a 0 é 1.

Uma das outras arestas é que poderíamos ter um algoritmo que roda em um tempo bem menor, mais especificamente em o(log n) multiplicações. Esse algoritmo se faz valer da estratégia de divisão e conquista usando uma espécie de meoização. A ideia é a seguinte:

Para calcular b^2n, se eu já tiver calculado b^n, basta fazer b^n * b^n

Note como a quantidade de operações agora diminuiu bruscamente. Antes, ao se chegar na conclusão do valor de b^n, você ainda precisaria fazer mais n multiplicações até chegar em b^2n. Agora em apenas uma operação se obtém b^2n. O pseudocódigo fica assim (já tratando de casos de expoente ímpar):

def pow(b, n):
  if n == 0:
    return 1
  b_to_half_n = pow(b, n//2)
  b_to_double_half_n = b_to_half_n * b_to_half_n
  if n % 2 == 1:
    b_to_double_half_n *= b
   return b_to_double_half_n

Outro ponto seria que... talvez recursão fosse considerado uma trapaça? Bem, então precisaríamos recorrer a laços. Felizmente recursão de cauda (como a primeira versão do algoritmo que faz o(n) multiplicações) é fácil transformar em laço. Podemos usar o seguinte meta-algoritmo:

  1. pega o caso base e o guarde na variável retorno
  2. coloca como condição do while a condição do caso base negada
  3. acumule a parte não recursiva na variável retorno de acordo com a fórmula recursiva, então faça com que os parâmetros sejam atualizados antes de começar a outra iteração
  4. retorne a variável retorno

Aplicando esse meta-algoritmo, ficamos com isso (já pegando o caso básico de expoente 0):

def pow(b, n):
  retorno = 1
  while n != 0:
    retorno *= b
    n -= 1
  return retorno

Bem, fica ineficiente comparado a outra versão mas com certeza não é trapaça. Então, ainda tem mais uma aresta?

Sim, tem. E essa aresta é das grandes. Devo até dizer que foi pegadinha de quem passou a atividade. Se você pegar o caso extremo das entradas (b == 49 e n == 49, visto que na descrição das entradas os números são menores que 50, portanto excluindo igualdade), você necessita de 49 * log2(49) ~= 276 bits para representar a magnitude desse número! Levando em consideração que um dos bits não é usado para valor (o chamado de bit do sinal), são necessários 277 bits! Só o caso de 2^49 implica usar números de pelo menos 51 bits para conseguir representar esse número. Esses números excedem os 32 bits típicos para se armazenar os inteiros em Portugol (fonte)

Então, o que isso quer dizer? Basicamente quer dizer que você deverá implementar seu próprio número usando listas ou vetores, uma implementação chamada de BigInteger. Para esse número, de toda a sorte você deveria inicialmente implementar a soma antes de mesmo ter a multiplicação disponível para ser usada. E perguntar "como se implementa um BigInteger do zero?" é um tanto quanto amplo demais para o formato do site.

0

Creio que seja isso que esteja procurando: inserir a descrição da imagem aqui

Segue abaixo Código usado:

algoritmo "semnome"
// Função : Exponenciação por Multiplicação
// Autor :  Paulo Vieira
// Data : 20/03/2018
// Seção de Declarações 
var
   Potencia, Base, Resultado, Contador: INTEIRO

inicio
// Seção de Comandos 
   Repita
       Limpatela
       Escreval("----------------------------")
       Escreva("Informe o número base:")
       Leia(Base)
   Ate Base < 51

   Repita
       Limpatela
       Escreval("----------------------------")
       Escreva("Informe a potência desejada:")
       Leia(Potencia)
   Ate Potencia < 51

   Limpatela
   Escreval("-----------")
   Escreva("A Base é")
   Escreval(Base)
   Escreval("-----------")
   Escreva("A Expoente é")
   Escreval(Potencia)
   Escreval("-----------")

   Resultado <- 0

   Para Contador de 1 ate Potencia Faca
        Se Resultado <> 0 entao
           Resultado <- Resultado * Base
        Senao
           Resultado <- Base * Base
        FimSe
   FimPara

   Escreval("-------------------------------")
   Escreva("O Resultado da operação é")
   Escreval(Resultado)
   Escreval("-------------------------------")
fimalgoritmo
-2

Não sei se isso te ajudaria, mas a função ficaria mais ou menos assim, utilizando a função de potência.

Fazendo com multiplicação, você teria que multiplicar o valor da sua base pela quantidade de vezes da sua potencia usando um for:

//algoritmo "Potencia"
var
   numero1,numero2:INTEIRO
   potencia:INTEIRO

inicio
// Seção de Comandos
   Escreva("informe um numero para a base de uma potencia")
           Leia(base)
           Para aux de 1 ate 50 passo 1 FACA
           potencia<-numero1^numero2
           escreval("a potencia de " ,numero1, " elevado " ,numero2," e ",potencia)
           fimpara
1
  • Creio que você não entendeu a pergunta. A operação permitida é multiplicação, você usou exponenciação. O 50 também não tem relação com a quantidade de passos do programa (portanto não deveria estar diretamente no for), mas sim limites máximos para os números de entrada. 20/03/2018 às 3:25

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .