Práctica 4 - Divide y Vencerás

Análisis y Diseño de Algoritmos
PRACTICA 4 – Divide y vencerás
Nombre de la profesora: Albortante Morato

Cecilia
Nombre del alumno: Melo Jimenez Jesus Uriel
Grupo: 3CM2
Introducción
Con ayuda del editor de texto y compilador Visual Code Studio se resolverla las problemáticas
planteada para la práctica 3.
Los headers a utilizar en la práctica son los siguientes:

stdio.h: Significa "encabezado de entrada - salida estándar", es el archivo de encabezado de la
biblioteca estándar de C que contiene definiciones de macro, constantes y declaraciones de funciones
y tipos utilizados para las diversas operaciones de entrada/salida. De este header utilizaremos
funciones como printf(Imprime texto y valores de variables, esto escribiendo su respectiva macara de
formato),scanf(Realiza la lectura de la variable con ayuda del operador de dirección de memoria).
stdlib.h: Es el archivo de cabecera de la biblioteca estándar de propósito general del lenguaje de
programación C. Contiene los prototipos de funciones de C para gestión de memoria dinámica, control
de procesos y otras. De esta función utilizaremos la función de srand para generar números
aleatorios.
Las problemáticas planteadas son las siguientes:
Implementar en el lenguaje de programación de su preferencia solo 1 de los siguientes algoritmos:
1. Multiplicación de enteros largos en decimal o en binario, aplicando el truco de Gauss.
2. Multiplicación de matrices de forma recursiva.
3. Multiplicación de matrices con el método Strassen.
Desarrollo
El programa comienza incluyendo las bibliotecas necesarias: stdio.h, stdlib.h y funciones.h (cabecera
creada por mí en donde están todas las funciones que utilizare).
Se incluyen las bibliotecas estándar <stdio.h>, <stdlib.h> y el archivo de encabezado

"divideYvenceras.h". Las dos primeras bibliotecas son estándar en C y se utilizan para entrada/salida
y asignación de memoria dinámica, respectivamente.
Se declara una variable de puntero numeros y se inicializa en NULL. Este puntero se utilizará para
almacenar los dos números ingresados por el usuario.
Se declara una variable op que se utilizará para almacenar la opción seleccionada por el usuario en el
menú.
Se inicia un bucle do-while que continuará ejecutándose hasta que el usuario seleccione la opción 2
(Salir).
Dentro del bucle, se muestra un menú con dos opciones: ingresar números y multiplicar, o salir del
programa. El usuario debe elegir una de estas opciones ingresando un número.
Se utiliza un switch para manejar las dos opciones posibles.
Si el usuario elige la opción 1 (Ingresar números y multiplicar), el programa verifica si ya se han
ingresado números anteriormente (comprobando si numeros no es NULL). Si es así, libera la memoria
asignada previamente con free(numeros).
Luego, el programa reserva memoria para dos números enteros largos (long long) usando malloc(2 *
sizeof(long long)). Esto proporciona espacio en la memoria para almacenar los dos números que el
usuario ingresará.
Se utiliza un bucle for para solicitar al usuario que ingrese dos números, uno a la vez, utilizando scanf.
Los números ingresados se almacenan en el arreglo apuntado por numeros.
Luego, se llama a una función llamada multiplicacion_larga con los dos números ingresados como
argumentos. El resultado de la multiplicación se almacena en la variable result y se muestra en la
pantalla.
Si el usuario elige la opción 2 (Salir), el programa muestra un mensaje de despedida y luego verifica si
numeros no es NULL. Si no es NULL, libera la memoria asignada para almacenar los números.
Si el usuario ingresa una opción que no sea 1 o 2, el programa muestra un mensaje de "Opción no
válida" y el bucle continúa ejecutándose.
El bucle do-while se repite hasta que el usuario seleccione la opción 2, en cuyo caso el programa sale
del bucle y finaliza..
Dentro del archivo divideYvenceras.h se encuentra la siguiente función:
“multiplicacion_larga”:
La función toma dos argumentos de tipo long long: a y b, los cuales son los números que se
multiplicarán.
La función comienza con una comprobación para ver si ambos números son lo suficientemente
pequeños (menores que 10). Si lo son, se realiza una multiplicación directa y se devuelve el resultado.
Esto actúa como un caso base para detener la recursión cuando los números son pequeños.
Si los números no son pequeños, se realiza una multiplicación larga eficiente. Para ello, se divide el
proceso en varias etapas.
Se calcula el número de dígitos en los números a y b utilizando bucles while. Esto se hace para
determinar la cantidad de dígitos en los números y, por lo tanto, la longitud de la multiplicación.
Se determina el número n, que es el máximo de los números de dígitos en a y b. Esto asegura que
ambos números tengan la misma longitud.
Luego, se divide los números a y b en dos mitades, a1 y a0 para a, y b1 y b0 para b. Esto se hace
calculando un factor p, que se usa para dividir los números.
Se realizan tres multiplicaciones recursivas:
ac es el producto de a1 y b1.
bd es el producto de a0 y b0.
ad_bc se calcula restando ac y bd de la multiplicación de (a1 + a0) y (b1 + b0).
Finalmente, se calcula el producto final combinando estos resultados y teniendo en cuenta la posición
de los dígitos (p) para obtener el resultado correcto.
El resultado de la multiplicación se devuelve como un valor long long.
Archivo “Funciones.h”
Código principal
Resultados
Menú de opciones
Menú de opciones con opción no valida
Opción 1
Conclusión
El programa funciona correctamente con números bastante grandes, pero deja de funcionar y se cierra
cuando los números introducidos superan el tamaño en bytes del tipo de dato long long, aun con esto,
la practica se realizo satisfactoriamente

Práctica 4 - Divide y Vencerás

Cargado por

Copyright:

Formatos disponibles

Práctica 4 - Divide y Vencerás

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Práctica 4 - Divide y Vencerás

Cargado por

Copyright:

Formatos disponibles

Análisis y Diseño de Algoritmos

PRACTICA 4 – Divide y vencerás

Nombre de la profesora: Albortante Morato

Los headers a utilizar en la práctica son los siguientes:

Se incluyen las bibliotecas estándar <stdio.h>, <stdlib.h> y el archivo de encabezado

Menú de opciones con opción no valida

También podría gustarte