Cómo escribir un programa que calcule ‘b’ elevado a power ‘n’ usando solo suma e iteración

En Perl6 probablemente reemplazaría (localmente) los operadores de multiplicación y exponenciación para poder escribirlo normalmente.

sub infix:<*> ( $a = 1, $b = 1 ) { [+] $a xx $b }
sub infix:<**> ( $a = 1, $b = 1 ){ [*] $a xx $b }

decir 5 ** 6; # 15625

Puedo entender si no confía en mí de inmediato que las subrutinas se están llamando realmente, por lo que aquí hay una versión ligeramente modificada que proporciona algunos resultados de registro a STDERR.

sub infix:<*> ( $a = 1, $b = 1 ) {
say $*ERR: "$a * $b";
[+] $a xx $b;
}
sub infix:<**> ( $a = 1, $b = 1 ){
say $*ERR: "$a ** $b";
[*] $a xx $b;
}

decir 5 ** 6;

5 ** 6
5 * 5
25 * 5
125 * 5
625 * 5
3125 * 5
15625

El = 1 en los parámetros solo establece los valores predeterminados, lo cual es necesario en &infix:<*> para 5 ** 0 y 5 ** 1 porque nuestro &infix:<**> operador / subrutina lo llamará con 0 o 1 argumentos en lugar de los 2 argumentos normales en esos casos. Otras soluciones serían hacerlos múltiples subs, o hacer que los parámetros sean opcionales y verificar la definición de los argumentos.

Si no sabes que [+] $a xx $b está haciendo el $a xx $b produce una lista que consta de $a repetido $b veces. los [+] pone efectivamente el + operador entre cada uno de los elementos.

Entonces escribiendo [+] 3 xx 5 es básicamente lo mismo que escribir 3 + 3 + 3 + 3 + 3 .

Aquí hay una función totalmente recursiva escrita en Octave / Matlab.

función y = silly_power (b, n)% calcular b ^ n para un par de números naturales
si n == 1% nada que hacer
y = b; %este es el resultado
de lo contrario, de lo contrario, multiplique b por b ^ {n-1}
y = silly_times (b, silly_power (b, n-1));
fin

end% end la función principal

función z = silly_times (m, n)% encuentra m * n para un par de números naturales
% Agregue el número y a sí mismo x veces con x <= y.
x = min (m, n); % haciendo x menor significa menos llamadas recursivas
y = max (m, n);
si x == 1% entonces nada que hacer
z = y; %este es el resultado
sino% de lo contrario
z = y + veces_silly (y, x-1); % agregue y al producto de y y x-1.
fin

end% end esta subfunción

Vamos a desglosarlo:
2 ^ 4 = 16
2 ^ 4 = 2 * 2 * 2 * 2

descomponerlo aún más:
2 * 2 = 2 + 2
4 * 2 = 4 + 4
8 * 2 = 8 + 8

Entonces, seudocódigo

// en eso
resultado = 1
incremento = 1

// calcular b ^ n
iterar sobre i, (n) veces:
iterar sobre j, (b-1) veces:
resultado = resultado + incremento
fin
incremento = resultado
fin

resultado devuelto

Prueba:

n = 3
b = 3

resultado = 1
incremento = 1
i = 0
j = 0: resultado = 2
j = 1: resultado = 3

incremento = 3
i = 1
j = 0: resultado = 6
j = 1: resultado = 9

incremento = 9
i = 2
j = 0: resultado = 18
j = 1: resultado = 27

volver 27

Esta es la implementación más simple que se me ocurre.

EDITAR: Acabo de notar que básicamente he repetido las respuestas de otras personas.

Para hacer las cosas un poco más interesantes, permitamos solo incrementos para que solo pueda agregar 1. Sí, podemos subir al poder agregando un montón de 1 e iterando.

Supongamos que estamos tratando solo con los números naturales aquí.

Aquí está el pseudocódigo.

// Primero, defina una función que agregue 1 a un número y devuelva el resultado.
función incr (a) {
devolver a + 1
}

// Luego definimos la función add.
// Esto toma 2 números a y b y luego incrementa ab veces por
// llamando a la función incr () que definimos anteriormente.
función add (a, b) {
suma = a
para i = 1 a b {
sum = incr (suma)
}

suma de retorno
}

// A continuación definimos la función mul (). Multiplicamos ayb sumando
// a sí mismo b veces. Hacemos uso de la función add () aquí.
función mul (a, b) {
producto = 0
para i = 1 a b {
producto = agregar (producto, a)
}

producto devuelto
}

// Finalmente la función pow (). Aquí elevamos a al poder de b por
// multiplicando a por sí mismo b veces. Usaremos la función mul ()
// que hemos definido anteriormente.
función pow (a, b) {
pwr = 1
para i = 1 a b {
potencia = mul (pwr, a)
}

poder de retorno
}

Hecho.

Si las llamadas a funciones cuentan como trampa, aquí está todo en una función y bucles 'for' anidados

(Pseudocódigo)

potencia de función (a, b) {
pwr = 1
para i = 1 a b {

producto = 0
para j = 1 a un {

suma = producto
para k = 1 a pwr {
sum ++
}
producto = suma

}
pwr = producto
}

volver pwr
}

¡Lo único que hacemos es incrementar (en la línea 10) e iterar!

Aquí está la primera versión en Java.

public static int incr (int a) {
return ++ a;
}

public static int add (int a, int b) {

int sum = a;
para (int i = 1; i <= b; i ++) {
sum = incr (suma);
}

suma de retorno;
}

public static int mul (int a, int b) {

int producto = 0;
para (int i = 1; i <= b; i ++) {
producto = agregar (producto, a);
}

producto devuelto;
}

public static int pow (int a, int b) {

int pwr = 1;
para (int i = 1; i <= b; i ++) {
pwr = mul (pwr, a);
}

return pwr;
}

public static void main (String [] args) {

// Prueba
System.out.println (pow (5, 6));

}

Y aquí está la segunda versión también en Java.

public static int pow (int a, int b) {

int pwr = 1;
para (int i = 1; i <= b; i ++) {

int producto = 0;
para (int j = 1; j <= a; j ++) {

int sum = producto;
para (int k = 1; k <= pwr; k ++) {
sum ++;

}
producto = suma;

}
pwr = producto;
}

return pwr;
}

public static void main (String [] args) {

// Prueba
System.out.println (pow (12, 3));

}

Mira, solo incrementa y repite y puedes subir a poderes.

Feliz codificación

En Python:

def RepeatAdd (a, b):
total = a
iterador = 1
mientras iterador total + = a
iterador + = 1
retorno total

def RepeatMultiply (b, n):
total = b
iterador = 1
mientras iterador total = RepeatAdd (total, b)
iterador + = 1
retorno total

Esto debería funcionar para todos los valores enteros positivos de byn. La función RepeatAdd proporciona una multiplicación genérica de los dos términos, iterando sobre el segundo. La función RepeatMultiply proporciona b ^ n llamando repetidamente a RepeatAdd en el total acumulado.

Editar: si desea que esto sea aplicable para pasar a la potencia 0, simplemente agregue una marca al comienzo de RepeatMultiply:
si n == 0:
volver 1

Se puede usar una variación del método de cuadratura repetida para obtener la exponenciación sin usar ninguna operación de multiplicación. Para eso necesitamos un cálculo de la representación binaria de n. Suponiendo que la representación binaria de n tiene k dígitos en orden inverso, el código psuedo del algoritmo es el siguiente

1. empezar,
2. establecer base: = b y ans: = 0
3. Para cada i de 0 a k-1

1. para cada j de 0 a base

1. base: = base + base

1. ans: = ans + base

Este método es un poco más rápido que la suma repetida. Por ejemplo, para calcular [matemáticas] 3 ^ 4 = 81 [/ matemáticas] necesitamos realizar 27 sumas repetidas. Donde como en este algoritmo no se requieren adiciones 12.

b ^ n = bbb …
xy = x + x + ..

// So for n > 0, you can use this.
int result = 1;
for (int i = 1; i <= n; i++) {
int aux = result;
for (int j = 1; j < b; j++) {
result += aux;
}
}


Bueno, la función de potencia es multiplicación repetida, y la multiplicación es suma repetida.

Por lo tanto, necesita un bucle para calcular la multiplicación y tomar el resultado de eso en un segundo bucle para calcular la potencia.

La solución directa, verdaderamente iterativa.

#! / usr / bin / env perl
sub mult {
my ($ n, $ t) = @_;
mi $ a = 0;
por mis $ i (1 .. $ t) {
$ a + = $ n;
}
devolver $ a;
}

sub pow {
my ($ n, $ p) = @_;
mi $ a = $ n;
por mis $ i (2 .. $ p) {
$ a = mult ($ a, $ n);
}
devolver $ a;
}

print pow (5, 7), “\ n”;

Hay soluciones más elegantes, pero tomarían más tiempo explicarlo. La solución anterior se traduce fácilmente a cualquier idioma.

Supongo que este es un ejercicio de aprendizaje dadas las restricciones bastante inusuales y luego la relajación usando solo números naturales en el problema. Asi que:

Al leer el texto que le dio su tutor, o las notas de diapositivas de la conferencia a las que debería haber asistido o asistió, y luego intentar y tratar una y otra vez hasta que funcione es la mejor respuesta que puedo dar a su pregunta. La forma de aprender a programar es programar y si no dedica el tiempo para asimilar estos conceptos desde el principio, cuando tenga problemas reales que resolver más adelante, fracasará mucho.

¿Qué tal una respuesta a una pregunta que no hizo?

Realmente depende de lo que se supone que debes aprender. Si el punto es que comprenda cómo funcionan los compiladores, o tal vez cómo o cómo funcionan las compuertas lógicas y por qué b a la potencia n podría procesarse como una serie de adiciones, le sugiero que adapte su respuesta al resultado del aprendizaje. que pensar en una forma “inteligente” de evitarlo en código.

En lugar de ser específico del idioma, esto suena como una pregunta en la que la respuesta debe ser pseudocódigo (sin ofender a las otras respuestas basadas en código perfectamente válidas) a menos que se le haya pedido que lo codifique.

Consejo de estudiante a estudiante: como atajo, afirmaría que no he incluido 0 en el conjunto de números naturales (una suposición justa ya que no hay un acuerdo consistente de que debería estar allí), ya que toma todo un concepto problema fuera de su solución.

Luego, desde el concepto que se supone que debes demostrar, entiendes que una solución debería ser bastante simple de escribir en pseudocódigo. Las otras respuestas ya han explicado bastante exhaustivamente las matemáticas involucradas, así que no me molestaré en repetir eso.

(Si por un giro increíblemente improbable del destino, no eres un estudiante y esta no es una pregunta de tarea, entonces mi respuesta es no molestarte con la estúpida restricción, mentira, diles que tomó 4 semanas debido a la restricción , escríbalo en cualquier idioma que se compile en código de máquina como b ^ n en dos minutos, luego deles el ejecutable compilado y disfrute de sus vacaciones)

respuesta = b
Para: x, 1, n-1
veces = 0
Para y, 1, b
tiempos = tiempos + respuesta
Fin
respuesta = veces
Fin

El verdadero problema es hacerlo solo con incrementos y bucles.

Python es probablemente la forma más limpia de hacerlo.

# compute b to nth power, b**n; multiply b to itself n times
def pow(b, n):
if n == 0:
return 1
result = reduce(lambda x, y: sum(x for i in xrange(y)), (b for i in xrange(abs(n))))
if n < 0:
return 1./result
return result


No se aplica la recursividad. Solo se realizan iteraciones (usando generadores) y sumas (las sumas). Tenga en cuenta que uso la división solo para manejar el caso de los poderes negativos.

La respuesta es realmente simple y todas las respuestas que figuran a continuación son correctas, no he visto una implementación en C, por lo que le voy a dar el código C para que haga lo mismo

#include

int funnyadd (int n, int i) {
int sum = n; // pista de salida.
int temp = n; // seguimiento del número mismo
mientras que (i! = 1) {
int newtemp = n;
while (newtemp! = 1) {// seguimiento del número de adiciones
suma + = temp;
newtemp–;
}
yo-;
temp = suma;
}
suma de retorno;
}

int main (nulo) {
int a = funnyadd (5, 3);
printf (“% d \ n”, a);
devuelve 0;
}

Este método requeriría dos números n e i, donde la función es n ^ i, cómo funciona para un ejemplo, digamos que 2 ^ 3 es:

Salida:
8

Funciona para todos los enteros con los que lo he probado, la complejidad en el tiempo es O (n ^ 2), lo que no es muy bueno, traté de hacerlo más eficiente, pero la adición me dificulta un poco. Esto fue lo mejor que pude hacer.

La razón por la que estamos estableciendo el caso base como 1 aquí es porque el número se eleva a la potencia de 1. Entonces 2 = 2 ^ 1, por lo que su caso base detendría uno por encima de cero.

Esto funcionaría para cualquier número de la misma manera.

¡Buena suerte!

En rubí:

potencia de def (b, n)
resultado = 1
n.times do
result = Array.new (b, result) .reduce (: +). to_i
fin
resultado
fin

O una solución alternativa, sin Array y reducir:

def mult (a, b)
resultado = 0
b.times {resultado + = a}
resultado
fin

potencia de def (b, n)
resultado = 1
n.times {resultado = mult (resultado, b)}
resultado
fin

Que se puede combinar como:

potencia de def (b, n)
resultado = 1
n.times do
subtotal = 0
b.times {subtotal + = resultado}
resultado = subtotal
fin
resultado
fin

Debería ser un delito penal, pero funciona …

def stupidpow(b, n):
if n == 0:
return 1
s = str(b)
for _ in xrange(n-1):
s = str(eval(str(s) + (b-1)*("+%s" % s)))
return eval(s)


Siento que deberías intentar hacer tu propia tarea sin enviar un SOS a Quora.

Habiendo dicho eso, piensa en las matemáticas.

La multiplicación no es más que aplicar la suma de forma iterativa.

La exponenciación a potencias enteras no es más que aplicar multiplicación iterativamente.

Te dejo a ti conectar los puntos.

La razón por la cual su profesor de ciencias de la computación le pide que haga esto no es para probar qué tan bueno usa google o quora. Están tratando de hacerte pensar en términos de algoritmos.

Por lo tanto, no debe privarse de una experiencia de aprendizaje al buscar ayuda en Internet.