INSTITUTO POLITÉCNICO NACIONAL

ESCUELA SUPERIOR DE MECÁNICA Y

ELÉCTRICA. UNIDAD CULHUACÁN

INGENIERÍA EN COMPUTACIÓN

Profesora: Beatriz Dolores Guardian Soto

Asignatura: Análisis de algoritmos

PRACTICA 2.

Complejidad de algoritmos iterativos y recursivos.

Integrantes:

Méndez Castañeda Daniel Christian

Pérez Sanjuan Francisco Xavier

Tobón Rosas Julián

Equipo: Grupo: 5CM23

Fecha de elaboración: 5 de Marzo de 2023

Semestre Enero - Junio 2023

PRACTICA 2

Definiciones
Algoritmo: Un algoritmo es un conjunto ordenado y finito de pasos precisos y bien
definidos que describen cómo llevar a cabo una tarea o resolver un problema en
particular.
Análisis de algoritmos: El análisis de algoritmos es una rama de la informática y
las matemáticas que se ocupa de la evaluación y comparación de los algoritmos
en términos de su tiempo de ejecución, uso de memoria y otros recursos de
cómputo, este predice el rendimiento de un algoritmo antes de implementarlo en
un programa.
Complejidad algorítmica: Se refiere a la cantidad de recursos (como tiempo y
memoria) que un algoritmo requiere para resolver un problema de entrada de un
tamaño particular. En otras palabras, es la medida de la cantidad de trabajo que
debe realizar un algoritmo para producir una respuesta.
Recursividad: La recursividad es una técnica utilizada en programación y en
matemáticas, que implica la definición de una función en términos de sí misma. En
otras palabras, la recursividad es una técnica de programación en la que una
función se llama a sí misma para resolver un problema.

Metodología del diseño y análisis de los algoritmos

La metodología del diseño y análisis de algoritmos es un conjunto de técnicas y

herramientas utilizadas para diseñar, analizar y evaluar la eficiencia de los
algoritmos. Un algoritmo es un conjunto ordenado de instrucciones que resuelve
un problema o realiza una tarea específica. La metodología del diseño y análisis
de algoritmos implica varias etapas, las cuales algunas de estas son:
Definición del problema: Entender el problema: El primer paso es comprender
claramente el problema a resolver y sus restricciones. Identificar soluciones
potenciales: Una vez que se comprende el problema, se pueden identificar
diferentes soluciones potenciales. Es importante considerar diferentes enfoques y
evaluar sus ventajas y desventajas.
Diseñar el algoritmo: Una vez que se ha identificado la solución más adecuada, se
debe diseñar el algoritmo. Esto implica definir las operaciones que se deben
realizar y el orden en el que deben realizarse. Analizar el algoritmo: Una vez que
se ha diseñado el algoritmo, se debe analizar su eficiencia. Esto implica evaluar el
tiempo y el espacio requeridos para ejecutar el algoritmo.
Codificación del algoritmo: Una vez que se ha diseñado y analizado el algoritmo,
se puede implementar en un lenguaje de programación.
Implementación: Una vez que se ha implementado el algoritmo, es importante
evaluar su rendimiento y compararlo con otros algoritmos existentes.
La metodología del diseño y análisis de algoritmos es una técnica fundamental
para desarrollar algoritmos eficientes y resolver problemas de manera efectiva en
diferentes áreas como la informática, la ingeniería y las ciencias.

Título: Complejidad de algoritmos iterativos y recursivos

Objetivo: Evaluar la eficiencia de algoritmos recursivos e iterativos

Problema propuesto
Dados 2 números enteros positivos (A y B) de al menos 7 dígitos obtener su
producto utilizando los métodos de:
 La russe
 Ingles
 Divide y vencerás

Problema 1

Parte I: Definición del problema y análisis del problema.

Definición del problema

Usando el método de La Russe, obtener el producto de 2 números enteros
positivos (A y B), cada uno con al menos 7 dígitos de longitud.

Análisis del problema

Dados los enteros A y B, se crean 3 listas, en las que la primera lista se agregan
los productos A*2, en la segunda lista la división (B/2) y en la tercera lista la suma
de los enteros positivos de B que correspondan a enteros impares de A.
Para un ejemplo más practico a continuación no tomaremos en cuenta los
números decimales, se obtendrá el producto de un numero A=67 por el de un
numero B=884, para el caso de B las divisiones sucesivas entre 2, terminaran
hasta llegar al numero 1, lo cual a su vez determina el numero de multiplicaciones
por 2 que tendrá A, se descartan valores de A en función de B, que esta contenga
un numero par, y se sumara el valor de A en la columna C, cuando en B tenemos
un impar. Al final se realiza la sumatoria de todos los valores de C, dando como
resultado el producto de nuestros números A y B que es 59,228.
 o Se considerarán en la suma final los valores iniciales, en el caso de que B
sea impar.
o En caso de contemplar los números decimales, para determinar si B es par
o impar, solo se toma en cuenta los números enteros.

A B C
67 884
134 442
268 221 268
536 110
1072 55 1072
2144 27 2144
4288 13 4288
8576 6
17152 3 17152
34304 1 34304
59228

Parte II: Construcción del algoritmo

Algoritmo general
1. Introducir los números enteros positivos A y B.
2. Comprobar que ambos números posean al menos 7 dígitos.
3. En caso de cumplir con el punto 2, crear una tabla con las columnas A, B y
C.
4. Hacer la división con residuo, entre 2 en la columna B, el numero B, hasta
que el resultado sea 1, despreciando el residuo.
5. Dependiendo del número de divisiones que se realizaron en la columna B,
hacer el mismo número de productos por 2, de la columna A.
6. En la columna C, llevar únicamente los datos de A, que se encuentren en la
misma fila que los números impares de la columna B.
7. Realizar la sumatoria de todos los datos filtrados en C.
8. La sumatoria es el resultado del producto de A y B, y se le da al usuario.
Prueba de escritorio
Refinaciones Sucesivas
1. Declarar variables A, B y C
2. Introducir los números enteros positivos A y B mayores a 7 dígitos.
3. Hacer la división con residuo, entre 2 en la columna B, el numero B, hasta
que el resultado sea 1, despreciando el residuo.
4. Dependiendo del número de divisiones que se realizaron en la columna B,
hacer el mismo número de productos por 2, de la columna A.
 5. En la columna C, llevar únicamente los datos de A, que se encuentren en la
misma fila que los números impares de la columna B.
6. Realizar la sumatoria de todos los datos filtrados en C e imprimir resultado.

Pseudocódigo
Inicio del algoritmo
(A, B)
Mientras que (A >= 1) hacer
Si (A mod 2) entonces
multi = multi + B;
Termina si
A = x/2;
B = y*2;
Fin algoritmo

Programación

Problema 2

Parte I: Definición del problema y análisis del problema.

Definición del problema

Dados dos números enteros positivos de 8 dígitos cada uno (A, B) obtener su
producto utilizando el método divide y vencerás.
Análisis del problema
Dados dos números enteros positivos que pueden ser A y B aplicando el método
de divide y vencerás para el producto de A y B se tiene que:
A B c
0981 1234
81 * 34 2754
09 * 34 306
12 * 81 972
12 * 09 108
0981* 1234 1210554
…....
Y asi hasta que se hayan multiplicado
con todas las combinaciones posibles

Parte II: Construcción del algoritmo

Algoritmo general
1. Introducir los números enteros positivos A y B.
2. Comprobar que ambos números posean al menos 8 dígitos.
3. En caso de cumplir con el punto 2, crear una tabla con las columnas A, B y
C.
4. Separamos el problema en subproblemas que se parecen al problema
original, de manera recursiva resuelve los subproblemas y, por último,
combina las soluciones de los subproblemas para resolver el problema
original.
5. Como divide y vencerás resuelve subproblemas de manera recursiva, cada
subproblema debe ser más pequeño que el problema original, y debe haber
un caso base para los subproblemas.
6. Y así hasta a completar todos los resultados de los subproblemas que
salieron de los dígitos declarados.
Prueba de escritorio

Pseudocódigo
Inicio del algoritmo
(A, B)
Mientras que (A<8digitos) hacer
Si (A mod 2) entonces
C=A*B;
Termina si
A = x*y;
B = y*x;
Fin algoritmo

Programación
 Problema 3
Parte I: Definición del problema y análisis del problema.

Definición del problema

Dados dos números enteros positivos de al menos 7 dígitos cada uno obtener su
producto utilizando el método inglés.

Análisis del problema

[Link] definen los dos números que se van a multiplicar.
[Link] traza una matriz dependiendo de la longitud de los números
[Link] multiplican los dígitos por el orden definido escribiendo el resultado parcial en
la casilla correspondiente a la matriz.
[Link] suman los resultados parciales que se encuentran en cada diagonal para
obtener los productos parciales.
[Link] suma los productos parciales para obtener el resultado final.

Parte II: Construcción del algoritmo

Algoritmo general
[Link] los números deseados a multiplicar
[Link] los números a cadenas y obtenemos su longitud.
[Link] una matriz de ceros con dimensiones dependientes a la longitud de los
números anteriormente definidos para contener los productos parciales.
[Link] la matriz con los productos parciales de cada dígito de los dos
números.
[Link] la matriz para mostrar los productos parciales.
[Link] la suma de los productos parciales multiplicando cada elemento de
la matriz por la potencia de 10 y sumándolos.
[Link] el resultado.
Prueba de escritorio

Pseudocódigo

INICIO DEL ALGORITMO

Ingresa los dos números deseados a multiplicar
Divide el primer número en unidades y decenas.
Divide el segundo número en unidades y decenas.
Multiplica cada una de las unidades del primer número por todas las unidades
y decenas del segundo número.
Escribe cada resultado parcial debajo del número correspondiente en la tabla
(matriz) del método inglés.
Suma todos los resultados parciales para obtener el producto final.
FIN DEL ALGORITMO

Programación
(Python)
# Función para calcular el producto usando el método inglés

def metodo_ingles(num1, num2):

# Convertimos los números a cadenas

num1_str = str(num1)

num2_str = str(num2)

# Obtenemos la longitud de las cadenas

num1_len = len(num1_str)

num2_len = len(num2_str)

# Creamos una matriz de ceros con dimensiones dependiendo de la longitud de los números
ingresados

matriz = [[0 for i in range(num2_len)] for j in range(num1_len)]

# Llenamos la matriz con los productos parciales de cada digito

for i in range(num1_len):

for j in range(num2_len):

matriz[i][j] = int(num1_str[i]) * int(num2_str[j])

# Imprimimos la matriz

print("Matriz de productos parciales:")

for i in range(num1_len):

for j in range(num2_len):

print(matriz[i][j], end="\t")
 print()

# Calculamos la suma de los productos parciales

suma = 0

for i in range(num1_len):

for j in range(num2_len):

suma += matriz[i][j] * (10 ** (num1_len + num2_len - 2 - i - j))

# Imprimimos el resultado

print("El producto de", num1, "y", num2, "es:", suma)

# Pedimos al usuario que ingrese los dos números

num1 = int(input("Ingrese el primer número: "))

num2 = int(input("Ingrese el segundo número: "))

# Llamamos a la función

metodo_ingles(num1, num2)
Conclusión
En general, la elección del método a utilizar para el producto de dos números
depende del tamaño de los números involucrados y de la eficiencia requerida en el
cálculo. En el caso de números pequeños, algunos métodos más sencillos pueden
ser suficientes, mientras que, para números grandes, los métodos de divide y
vencerás, inglés o russe pueden ser más apropiados.