INSTITUTO POLITÉCNICO NACIONAL
ESCUELA SUPERIOR DE INGENIERÍA MECÁNICA Y
ELÉCTRICA
UNIDAD CULHUACAN
Unidad de Aprendizaje:
Análisis de Algoritmos
Profesor:
Beatriz Dolores Guardián Soto
Práctica 2:
Factorial y Serie de Fibonacci
Integrantes:
Montoya Flores Daniel
Mora Martínez Yeredith Giovanna
Naveda Leyva Martín
Villanueva Carranza Aline
GRUPO: 5CM23
Objetivos:
Resolver los siguientes problemas:
Factorial
Serie Fibonacci
Con algoritmos
1. Recursión
2. Programación Estructurada (Utilizar funciones)
3. Iterativo (Utilizando ciclos, while, do while, for)
Introducción
Se pretende aplicar la MDAAC en cada uno de los algoritmos propuestos, para el
desarrollo de los mismos, utilizaremos la herramienta en software llamada PSeInt,
la cual nos permite desarrollar pseudocódigos, y además probarlos con una interfaz
amigable.
Desarrollo
Definición del problema 1: Resolver el problema de encontrar el factorial de un
número.
El primer algoritmo que se presentara será el iterativo, hecho por Aline.
Análisis del problema:
El factorial de un numero entero positivo “n” se define como el producto de todos los
números enteros positivos menores o iguales que n.
En otras palabras para poder sacar el factorial de un número n (n!) lo que debemos
hacer es multiplicar n por los números antecesores a este hasta llegar a 1.
Ejemplos:
8x7x6x5x4x3x2x1
8!=803220 =
1 -> se observa que 1 es el termino de
8!=8*7! = 8x7x6x5x4x3x2x1
parada (se usara como una condición)
7!=7*6! = 7x6x5x4x3x2x1
6!=6*5! = 6x5x4x3x2x1
5!=5*4! = 5x4x3x2x1
4!=4*3! = 4x3x2x1
3!=3*2! = 3x2x1
2!=2*1! = 2x1
1!=1 = 1x1
0!=1
Construcción del algoritmo:
Primero se construye el algoritmo general, que es la respuesta inmediata a la
solución del problema.
ALGORITMO GENERAL
Inicio
Leer n;
para i<-n; hasta 1; (i<-i-1) hacer
fact<- i*i-1;
fin para
escribir “fac”;
fin
PRUEBA DE ESCRITORIO
# n i fac
1 3 3 6
2 2
1 0
El resultado nos da erróneo, así que se empiezan a hacer algunos ajustes en el
algoritmo.
DEPURACION DE ALGORITMO
Inicio
Leer n;
si n=1 o n=0 entonces
escribir “factorial es 1”;
si no
para i<-n; hasta 1; (i<-i-1) hacer
n*<- i-1;
fin para
fin si
escribir “n”;
fin
PRUEBA DE ESCRITORIO
# n i
1 3 3
2 2
0
En la primera depuración se observó que aún había errores
Proceso factorial
Definir n,i,fac Como Entero;
Escribir "Ingrese el numero para sacar el factorial: ";
Leer n;
Si n=1 o n=0 Entonces
Escribir "El factorial de ", n, " es: 1";
SiNo
fac<-n;
Para i<-n hasta 2 Con Paso -1 Hacer
fac <- fac * (i-1);
FinPara
Escribir "El factorial de ",n," es: ",fac;
FinSi
FinProceso
PRUEBA DE ESCRITORIO
# n i
1 3 3
2
1
6
Codificación
#include <stdio.h>
#include <stdlib.h>
int main ()
{
int n,factorial, i;
puts("Ingrese un numero: ");
scanf("%i", &n); //& nos da (apunta) la direccion de memoria
if (n==1 |n==0 )
{
printf ("\n El factorial de %i es: 1",n);
}
else
{
factorial=n;
for(i=n;i>1;i--)
{
factorial=factorial*(i-1);/*factorial*=(i-1) */
}
printf("El factorial de %i es: %i\n",n,factorial);
}
return 0;
}
El segundo algoritmo es el Estructurado (utilizando funciones), elaborado por
Yeredith.
Análisis del problema:
1. Se pide un dato, supóngase se quiere obtener el factorial de 3
2. El factorial de un número es la multiplicación de 1 hasta n excepto cuando es
un número negativo o 0.
3. Factorial de 3 es 1x2x3 = 6
4. Si se quiere obtener el factorial de 0 será uno ya que la ecuación dice que
n!/n= (n-1)! Es decir que 1!/1=(1-1) por lo tan1=0.
5. El factorial de un número negativo es 0.
Construcción del algoritmo:
Funcion ped_dat
escribir "ingese un numero: "
leer num
FinFuncion
Funcion cicl_fact
Para i<-1 Hasta num Hacer
fact<-fact*i
i<-i+1
Fin Para
FinFuncion
Funcion cond_fact
Si num<0 Entonces
fact<-0
SiNo
Si num<-0 Entonces
fact<-1
SiNo
cicl_fact
Fin Si
Fin Si
FinFuncion
Algoritmo factorial
ped_dat
cond_fact
Escribir "el factorial", num
escribir "es", fact
FinAlgoritmo
Prueba de Escritorio.
Sea num=5
Si num es diferente de 0 y mayor a 0
Desde 1 hasta 5
1!=1
2!=1x2
3!=1x2x3
4!=1x2x3x4
5!=1x2x3x4x5
5!=720
Codificación
#include "iostream"
#include "conio.h"
using namespace std;
int i, fact=1, num;
void ped_dat(){
cout<<"ingrese un numero: ";
cin>>num;
}
void cicl_fact(){
for (i=1; i<=num; i++)
fact=fact*i;
}
void cond_fact(){
if (num<0){
fact=0;
}else{
if (num==0)
{
fact=1;
}else{
cicl_fact();
}
}
}
main(){
ped_dat(); cond_fact();
cout<<"El factorial de "<<num<<" es: "<<fact;
}
El tercer algoritmo es el Recursivo elaborado por Martin
Análisis del problema
FACTORIAL DE UN NÚMERO
El factorial de un entero no negativo n, se escribe n! (y se pronuncia “n factorial”),
se define
n! = n* (n - 1) * (n - 2) *…* (n-x)
en donde n-x será igual a 0, para describir esta situación utilizaremos como ejemplo
5! que es el producto de 5*4*3*2*1, el cual es igual a 120.
Antes que nada, procedemos a preguntar al usuario el número del cual desea
obtener el factorial, ese valor nos permitirá saber cuántas veces se mandara a
llamar la función a sí misma, la función consiste en realizar la formula anterior y el
resultado final será obtenido de la siguiente manera:
Funcion res <- fac ( n )
Si n=0 Entonces
res=1;
Sino
res=n*fac(n-1);
Fin Si
Fin Funcion
La parte donde se ve reflejada la fórmula es:
res=n*fac(n-1);
pero para poder obtener el resultado(res) final es necesario hacer una condición
que nos permitirá saber cuándo tenemos que dejar de realizar la función, ejemplo:
n=5
La evaluación de 5! se lleva a cabo como muestra la figura. La figura (a) muestra la
manera en que proceden las llamadas recursivas hasta que 1! se evalúa como 1, lo
cual termina la recursividad. La figura (b) muestra los valores devueltos por cada
llamada recursiva a su llamada original, hasta que se calcula y se devuelve el valor
final.
(a) (b)
Construcción del Algoritmo
Funcion res <- fac ( n )
Definir res Como Entero;
Si n=0 Entonces
res <- 1;
Sino
res <- n*fac(n-1);
FinSi
FinFuncion
Algoritmo factorial
Definir n Como Entero;
Escribir "";
Escribir " FACTORIAL";
Escribir "";
Escribir "Introduce el numero: ";
Leer n;
Escribir "El factorial del numero " ,n, " es: ", fac(n);
Escribir "";
Escribir "";
FinAlgoritmo
Prueba de Escritorio.
FACTORIAL DE UN NUMERO
EJEMPLO: n=5
n=1
2*1!=2
2! = 2 (2 -
Realizamos la operación 1)!
n=2
3*2!=6
3! = 3 (3 -
Realizamos la operación 1)!
n=3
4*3!=24
4! = 4 (4 -
Realizamos la operación 1)!
n=4
5*4!=120
5! = 5 (5 -
Realizamos la operación 1)!
Codificación
#include<iostream>
using namespace std;
int factorial(int);
int main(){
int n;
cout<<endl<<" FACTORIAL"<<endl<<endl<<endl;
cout<<"Introduce el numero: ";
cin>>n;
cout<<endl;
cout<<"El factorial del numero "<<n<<" es: "<<factorial(n)<<endl<<endl<<endl;
}
int factorial(int n){
int fac;
if(n==0)
return 1;
else
return n*factorial(n-1);
}
Definición del problema 2: Resolver el problema de encontrar el factorial de un
número.
El primer algoritmo es el Iterativo (Utilizando ciclos), hecho por Martin.
Análisis del problema:
SERIE DE FIBONACCI
La serie se presenta en la naturaleza y, en particular, describe la forma de una
espiral, la serie de Fibonacci:
0, 1, 1, 2, 3, 5, 8, 13, 21,…
Comienza con 0 y 1, y tiene la propiedad de que cada número subsiguiente es la
suma de los dos números anteriores de la serie.
Antes que nada, procedemos a solicitar al usuario que introduzca el número del cual
quiere calcular el valor Fibonacci, este valor nos permitirá empezar con los cálculos
y en el caso del siguiente código nos permitirá determinar cuántas veces se ejecuta
el siclo para poder obtener el resultado de la serie.
Mientras n>0 Hacer
res<-n1+n2;
n1<-n2;
n2<-res;
Escribir Sin Saltar res," ";
n<-n-1;
Fin Mientras
Antes de empezar los cálculos determinamos n1=-1 y n2=1 ya que esto nos ayudara
a determinar correctamente la serie y una vez dentro del siclo iremos
decrementando el valor de n hasta que n sea igual a 0 con el fin de salir y concluir
las operaciones adecuadamente, ejemplo:
n=5
Construcción del algoritmo:
Algoritmo fibo
Definir n,res,n1,n2 como entero;
n1<--1;
n2<-1;
Escribir " FIBONACCI";
Escribir "";
Escribir "Cuantos numeros de la serie quieres ver: ";
Leer n;
Escribir "";
Mientras n>0 Hacer
res<-n1+n2;
n1<-n2;
n2<-res;
Si n>1 Entonces
Escribir Sin Saltar res,"-";
Sino
si n<=1 Entonces
Escribir Sin Saltar res,"";
FinSi
FinSi
n<-n-1;
FinMientras
Escribir "";
Escribir "";
FinAlgoritmo
Prueba de Escritorio.
SERIE DE FIBONACCI
EJEMPLO: n=5
n1= -1 n2=1
valores iniciales de n1 y
n2
n=5
res = -1+1; n1=1; n2=0;
res="0" n=5-1
n=4
res = 1+0; n1=0; n2=1;
res="0-1" n=4-1
n=3
res = 0+1; n1=1; n2=1;
res="0-1-1" n=3-1
n=2
res = 1+1; n1=1; n2=2;
res="0-1-1-2" n=2-1
n=1
res = 1+2; n1=2; n2=3;
res="0-1-1-2-3" n=1-1
Codificación
#include <iostream>
#include <conio.h>
using namespace std;
int main()
{
int n,res,n1=-1,n2=1;
cout<<endl<<" FIBONACCI"<<endl<<endl<<endl;
cout << "Cuantos numeros de la serie quieres ver: ";
cin >> n;
cout <<endl<<endl;
do{
res=n1+n2;
n1=n2;
n2=res;
if(n>1)
cout <<res<<" - ";
else if(n<=1)
cout <<res<<" ";
n--;
}while(n>0);
cout <<endl<<endl;
return 0;
}
El segundo algoritmo es el Recursivo, hecho por Daniel.
Análisis del problema:
El cálculo de la sucesión de Leonardo de Pisa, conocido como Fibonacci:
0, 1, 1, 2, 3, 5, 8, 13, 21,…., etcétera.
El Fibonacci de un número se obtiene la suma de los dos números Fibonacci
anteriores. Por definición:
Fibonacci (0) = 0 Paso básico
Fibonacci (1) = 0 Paso básico
Fibonacci (2) = Fibonacci (1) + Fibonacci (0)
= 1 + 0 =1
Fibonacci (3) = Fibonacci (3) + Fibonacci (2)
= 2 + 1 =3
Fibonacci (n) = Fibonacci (n-1) + Fibonacci (n-2) Paso Recursivo
La fórmula siguiente representa la definición de la serie de Fibonacci.
n=0
n Si
n=1
Fibonacci(n)
Fibonacci (n-1) +
Si n > 1
Fibonacci(n-2)
Construcción del algoritmo:
funcion numFibo <- FibonacciRec(n)
si n = 0 o n = 1 entonces
numFibo <- n;
SiNo
numFibo <- FibonacciRec(n-1) + FibonacciRec(n-2);
FinSi
FinFuncion
Proceso Fibonacci
Definir n,numFibo Como Entero;
leer n;
numFibo <- FibonacciRec(n);
Escribir numFibo;
FinProceso
Prueba de Escritorio.
La siguiente imagen nos muestra el siguiente del algoritmo recursivo del factorial de
un numero N.
Codificación
#include<stdio.h>
int Fibonacci(int);
void generarSerie();
void Mostrar(int n);
int main()
{
generarSerie();
return 0;
}
int Fibonacci(int n)
{
if(n == 0 | n == 1 )
{
return n;
}
else
{
return (Fibonacci(n-1) + Fibonacci(n-2));
}
}
void generarSerie()
{
int n,i;
printf("\nHasta que termino de la serie desea ver? ");
scanf("%d",&n);
i=0;
while(i<n)
{
Mostrar(Fibonacci(i));
i++;
}
}
void Mostrar(int n)
{
printf("\n%3d",n);
}
El tercer algoritmo es el Estructurado (Utilizando Funciones), hecho por Daniel.
Análisis del problema:
Considerando el análisis anterior (algoritmo recursivo).
0, 1, 1, 2, 3, 5, 8, 13, 21,…., etcétera.
El Fibonacci de un número se obtiene la suma de los dos números Fibonacci
anteriores. Por definición:
Fibonacci (0) = 0
Fibonacci (1) = 0
Fibonacci (2) = Fibonacci (1) + Fibonacci (0)
= 1 + 0 =1
Fibonacci (3) = Fibonacci (3) + Fibonacci (2)
= 2 + 1 =3
Fibonacci (n) = Fibonacci (n-1) + Fibonacci (n-2)
Construcción del algoritmo:
funcion CapturaDatos(n por referencia)
leer n;
FinFuncion
funcion Fibonacci(n)
Definir fiba,fibo,i,fibb como entero;
si n = 0 o n = 1 Entonces
fibo <- n;
SiNo
fiba <- 0;
fibb <- 1;
i <- 2;
mientras i <= n hacer
fibo <- fibb +fiba;
fiba <- fibb;
fibb <- fibo;
i <- i + 1;
FinMientras
mostrar(fibo);
FinSi
FinFuncion
Funcion mostrar(n)
Escribir n;
FinFuncion
Proceso NumeroFibonacci
Definir n como entero;
CapturaDatos(n);
Fibonacci(n);
FinProceso
Prueba de Escritorio.
La prueba se realiza al módulo o función que genera la serie de Fibonacci(n).
n Fibo Fiba Fibb I
6 0 1 2
1 1 1 3
2 1 2 4
3 2 3 5
5 3 5 6
8 5 8 7
Codificación
#include<stdio.h>
int CapturaDatos();
int FunFibonacci(int);
void generarSerie();
void Mostrar(int n);
int main()
{
int numero;
generarSerie();
return 0;
}
int CapturaDatos()
{
int num;
printf("\nTeclee el numero que desea ver de la serie de fibonacci: ");
scanf("%d",&num);
return num;
}
int FunFibonacci(int n)
{
int i,fibo,fiba,fibb;
if( n == 0 | n == 1)
{
fibo = n;
}
else
{
fiba = 0;
fibb = 1;
i = 2;
while(i <= n)
{
fibo = fibb + fiba;
fiba = fibb;
fibb = fibo;
i++;
}
}
return fibo;
}
void generarSerie()
{
int n,i;
printf("\nHasta que termino de la serie desea ver?");
scanf("%d",&n);
i=0;
while(i<n)
{
Mostrar(FunFibonacci(i));
i++;
}
}
void Mostrar(int n)
{
printf("\n%3d",n);
}
Conclusiones
El objetivo de esta práctica se cumplió, ya que cada uno de los integrantes,
comprendió y aplico la Metodología del diseño y análisis de los algoritmos
computacionales, aunque debemos aclarar que solo ocupamos la parte del diseño,
con forme avance el curso, se aplicara el análisis de los algoritmos, donde se
evalúa el espacio y el tiempo.
Por otro lado se entendió, como hacer una prueba de escritorio y como esta
influye en las correcciones o redefiniciones del algoritmo final (pseudocódigo), así
mismo cada uno analizo el problema de forma distinta.
Para cumplir de forma completa algunos integrantes realizaron más de un
algoritmo para obtener una mejor compresión.
Bibliografía
Aguilar, L. J. (2008). Fundamentos de programación. Algoritmos, Estructura de
datos y objetos. MC Graw Hill.
Soto, B. D. (2018). Apuntes de clase.
