jueves, 14 de enero de 2016

Algoritmos - 2 de 5



5.3 Algoritmos iterativos

Un componente básico de los algoritmos es la iteración. Esta palabra implica repetición, ya que iterar significa ejecutar repetidamente algunos pasos elementales de un algoritmo acercándose, paso a paso, a la solución. Para realizar un programa de ordenador es muy conveniente localizar los pasos que se repiten y anidarlos dentro de un sistema iterativo.
En el ejemplo anterior en el que se determinaba si el número 5 era o no primo, se ha seguido un método que funciona para el caso concreto del número 5. Si se quisiera desarrollar un programa más genérico (por ejemplo, un programa que determinara si un número N es o no primo) haría falta identificar la parte repetitiva del algoritmo y anidarla dentro de un proceso iteración en el algoritmo. 


Ejemplo 6. Determinar iterativamente si un número N es o no primo

Vamos a rehacer el algoritmo para calcular si el número 5 es primo de manera que sea un algoritmo válido para un número genérico N. En el diagrama de flujo del ejemplo para el número 5 se observan tres repeticiones:
Se divide el número N entre un número natural.
Se observa si la división es entera.
Se incremento del número natural que va a dividir al número N.
En el caso que estamos tratando hemos localizado tres pasos que se repiten, los cuales se realizan desde el número 2 hasta el número 4 en el ejemplo concreto del número 5. De lo que se trata es de anidar estos tres pasos dentro de un bucle que se ejecute mientras que se cumpla una cierta condición; siendo la condición que el número natural que divide a N sea inferior a N. Vamos a llamar al número que divide i, al resultado de la división D y al número a chequear N. El diagrama de flujo resultante es el siguiente:


En el diagrama de flujo hay tres instrucciones que se repiten iterativamente (la tres que se han descrito anteriormente) y aparece una condición de chequeo para saber si debe detenerse el algoritmo o no (si i ha llegado a obtener el valor de N). La manera elegida para programar el bucle ha sido la de anidarlo dentro de un bucle WHILE con la condición de chequeo en TRUE (while 1). Este bucle resultaría ser un bucle infinito (ya que la condición de chequeo siempre se cumple) si no fuera porque dentro del bucle se han anidado dos bifurcaciones IF que contienen una ruptura del bucle (BREAK). Esta ruptura se produce cuando la condición de alguna de las dos bifurcaciones se cumple, las cuales son:

1ª Si se encuentra una división exacta (N no es primo).
2ª Si resulta que el divisor a probar (i) ha llegado a ser igual a N (N es primo).



Ejemplo 7. Mejora del algoritmo para calcular si un número N es primo 

A continuación se van a presentar dos mejoras del anterior proceso iterativo desde el punto de vista de la computación. Como ya sabemos, para determinar si, por ejemplo, el número 231 es primo, hay que dividirlo entre todos los números naturales entre el 2 y el 230. Pero también es cierto que todos aquellos números naturales superiores al √231 no dividen de forma entera al 231, por lo que la condición de chequeo puede modificarse por comprobar que la variable i no rebase el valor de √231 . Con esto se consigue que, en el caso del número 231, en lugar de repetir el proceso iterativo 229 veces (desde i=2 hasta i=230), se repita solo 14 veces (desde i=2 hasta i=15), ya que por encima del 15 es seguro que no existe ningún número que divida al 231 de manera entera, con lo que se reduce la carga computacional del algoritmo.



Otra mejora sobre el algoritmo anterior consiste en evitar que en cada paso del bucle iterativo se calcule la raíz cuadrada de N, ya que calcular la raíz cuadrada de un número es muy costoso para un ordenador. Para ello basta con calcular una vez la raíz de N, almacenarla en una variable (llamémosle K) y utilizar esta variable en la condición de chequeo, como puede verse en el diagrama de flujo siguiente.


Si se prueba a cronometrar los dos últimos programas presentados (PrimoII y PrimoIII) puede observarse que PrimoIII es mucho más rápido que PrimoII. ¿Cómo cronometrar un programa? Generalmente se utiliza el propio reloj del ordenador para medir el tiempo. Además, cuando son programas cuyo tiempo de ejecución es muy corto, se le suele pedir al ordenador que los ejecute varias veces (por ejemplo 1000) y se establece una media del tiempo que ha tardado, ya que medir lo que tarda el programa una sola vez es muy impreciso.


Ejemplo 8. Obtención del factorial de un número N iterativamente

Un ejemplo claro de un proceso iterativo es el cálculo del factorial de un número N. La regla del factorial de un número expresada matemáticamente es:


De forma que para calcular el factorial del número 5 se siguen los siguientes pasos:
Se multiplica a 2 por 3 y se almacena el resultado.
Se multiplica el resultado anterior por 4 y se almacena de nuevo.
Se multiplica el resultado anterior por 5 y se almacena de nuevo.
Este último resultado es el factorial de 5. Si observamos el proceso se ve necesario utilizar una variable que varíe su valor de uno en uno desde el 2 hasta el 5 (llamémosle a esta variable i) Asimismo se necesita otra variable para almacenar el resultado de la multiplicación (llamémosle a esta variable Resultado).

Los pasos que se repiten son 3:
Multiplicación de Resultado por la variable i.
Almacenamiento de la operación anterior.
Incremento de la variable i en una unidad.

En realidad los pasos 1º y 2º se pueden hacer en una sola operación "informática" (multiplicar Resultado por i) y asignar el resultado de la multiplicación a Resultado).

Por último faltaría la condición de chequeo para continuar o para detener los tres pasos durante el proceso iterativo. La condición de chequeo en este caso es comprobar que la variable i no supera el valor del número del que se calcula el factorial N.



Ejemplo 9. Descomposición factorial de un número N.

Obtener la descomposición factorial de un número natural N consiste en determinar todos aquellos números naturales de menor valor que multiplicados entre si dan como resultado el número N. Para ello hay que probar a dividir el número N entre todos los números naturales que hay entre 2 y N . A continuación se describen los pasos que se repetirán en el proceso iterativo:

Siendo I el número con el que se prueba a dividir N en un momento dado, hay que chequear que el valor de I no supere el valor de √N :

Si lo supera, se termina el proceso iterativo.
Si no lo supera, se comprueba si N es divisible de manera entera entre I:
Si N no es divisible entre I hay que pasar al siguiente número (el I+1).
Si N es divisible entre I hay que:
Almacenar a I como factor del número N
Actualizar el valor de N como N=N/I
Los factores se van a guardar en un vector que llamaremos factores. Para guardar ordenadamente los factores nos valdremos de una variable auxiliar que llamaremos f.
Inicialmente esta variable f valdrá 1 y, cada vez que aparezca un nuevo factor de N, se incrementará en una unidad el valor de f. De esta manera, sirviéndonos de la variable auxiliar f, podremos guardar el primer factor en la primera celda del vector factores, el segundo factor en la segunda celda y así sucesivamente.



Espero haber ayudado en algo. Hasta la próxima oportunidad!










  

No hay comentarios:

Publicar un comentario

       

Etiquetas

Academy (23) Accediendo a datos con ADO .NET (31) Acceso a la red (30) Algoritmo (34) Algoritmos en JAVA (2) Ampliación de clases (2) APRENDA A PROGRAMAR COMO SI ESTUVIERA EN PRIMERO - Autores : IKER AGUINAGA (3) APRENDA A PROGRAMAR COMO SI ESTUVIERA EN PRIMERO - Autores : IKER AGUINAGA (10) Aprendiendo a desarrollar en Windows 8 (5) Aprendiendo UML en 24 Horas (Autor : Joseph Schmuller ) (30) Arquitectura (29) Arquitectura del Computador (3) Arquitectura del Computador - Historia de la informática (1) Asignación de direcciones IP (23) Aspectos fundamentales de bases de datos (5) Auditoría de la dirección (2) Auditoría de Sistemas (3) Auditoría Informática - Un enfoque práctico - Mario G . Piattini y Emilio del Peso (7) Avanzado (23) Base de Datos (67) Básico (23) Bios (29) Business Productivity Online Suite - BPOS (3) Capa de Red (22) Capa de Transporte (16) Capítulo 1 - Documentos HTML5 (6) Capítulo 10. API Web Storage (2) Capítulo 11. API IndexedDB (4) Capítulo 12. API File (1) Capítulo 2. Estilos CSS y modelos de caja (7) Capítulo 3. Propiedades CSS3 (4) Capítulo 4. Javascript (6) Capítulo 5. Video y audio (6) Capítulo 6. Formularios y API Forms (8) Capítulo 7. API Canvas (5) Capítulo 8. API Drag and Drop (2) Capítulo 9. API Geolocation (2) CCNA1 v5.0 (211) CCNA1 v6.0 (23) CCNA2 v5.0 (26) CCNA3 v5.0 (25) CCNA4 v5.0 (23) CD-ROM (3) Chapter 1 How does Xamarin.Forms fit in? (7) Chapter 2 Anatomy of an app (5) Cisco (313) Cloud Computing (3) CNNA v5.0 Routing & Switching (232) CNNA v6.0 Routing & Switching (2) Codigo (2) Computadora (32) Configuración (29) Configuración de un sistema operativo de red (21) Control (29) Creación de tipos de datos y tablas (3) Creación y Administración de bases de datos (3) Creando la Interface de la Aplicación Windows (50) Creating Mobile Apps with Xamarin.Forms (13) Cuenta (29) Curso (32) Curso Aprendiendo a Programar (25) Datos (3) Desarrollando en Windows 8 - AVANZADO (2) Desarrollando en Windows 8 - BÁSICO (3) Desarrollando en Windows 8 - INTERMEDIO (2) Desarrollo (2) Desarrollo .Net (21) Desarrollo avanzado de Windows Store Apps usando C# (1) Desarrollo basado en conceptos de Ingeniería de Software para Visual Studio (2) DESARROLLO DE APLICACIONES WINDOWS CON MICROSOFT .NET (37) DESARROLLO DE APLICACIONES WINDOWS CON MICROSOFT .NET (Autor: Luis Dueñas Huaroto) (29) Desarrollo en Microsoft Visual Studio (44) Desarrollo en Microsoft Visual Studio - AVANZADO (15) Desarrollo en Microsoft Visual Studio - BÁSICO (14) Desarrollo en Microsoft Visual Studio - INTERMEDIO (18) Desarrollo en Windows Phone 8 (13) Diagnostico (4) Diagrama (3) Diagramas de actividades (2) Diagramas de colaboraciones (2) Diagramas de secuencias (2) Digital (2) Diplomado (2) Disco (29) Disco Duro (4) Diseño de aplicaciones de Windows 8 en HTML 5 (7) Dispositivos Electrónicos (11) Doctorado (2) Ejemplos (3) Ejemplos de algoritmos (27) El camino hacia el CSS3 (3) El diseño web flexible (6) El elemento de diseño Canvas (3) El enfoque de los sistemas (3) El flujo de un programa (2) El gran libro de HTML5 - CSS3 y Javascript - Autor: Juan Diego Gauchat (55) El principio de organicidad (7) Electrónica (2) Elementos de un sistema (5) Empresas (2) Entrada y salida (4) Entropía y neguentropía (7) Estrategia (2) Estructura de un programa Java (12) Estructuras de almacenamiento (10) Estructuras de control (6) Estructuras de las tablas en SQL Server (2) Estructuras fundamentales de los datos (2) Ethernet (21) Evolución y Familias de los Microprocesadores (15) Exámen (23) Exploración de la red (23) Extensión de clases (4) Facebook (4) Familia Intel (15) Forefront (8) Función (3) Funciones de una red (12) Funciones de una red informática (1) Fundamentos de C# para absolutos principiantes (17) Fundamentos de programación en Java (50) Generaciones de la computadora (5) Gestión (3) Gestión de riesgos - Auditoría de Sistemas (1) GONZALO MARTÍNEZ (1) Grupos Facebook (1) Harvard (29) Historia de las computadoras (11) HTML5 y CSS3 - Autor: Christophe Aubry (99) HTML5 y CSS3 aplicadal texto (7) HTML5 y CSS3 para los formularios (15) Imágenes (2) Implementación de Windows 7 (11) Información (31) Informática (29) Ingeniería (4) Instalar (29) Inteligencia (2) Inteligencia de Negocios con SQL Server (3) Intermedio (23) Internet (29) Internet Explorer 9 (3) Introducción a ASP.NET 5 (8) Introducción a Java (7) Introducción a jQuery (8) Introducción a la Auditoría de Sistemas (2) Introducción a la teoría general de sistemas (Oscar Johansen Bertoglio) (39) Introducción a Networking (2) Introducción a Window Forms (5) Introducción al acceso a datos con ADO .NET (9) Investigación de Operaciones (12) Java (52) Jump Start de consultas en las bases de datos de Microsoft SQL Server 2012 (8) La definición de un Sistema (6) La evolución del HTML y del CSS (3) La nueva sintaxis HTML5 (12) LA QUINTA DISCIPLINA en la práctica (Autor : Peter Senge) (28) Las animaciones en CSS3 (5) Las transformaciones CSS3 (11) Las transiciones con CSS3 (8) Licenciamiento Microsoft (3) Local Area Network (LAN) - Red de Area Local (2) Lógico (2) Los elementos de la estructura en html5 (9) Los elementos multimedia: audio y vídeo (2) Los estilos de caja en CSS3 (13) Los nuevos selectores de CSS3 (6) Maestría (2) Mantenimiento de Mouse y Teclado (2) Manual de Microsoft SQL Server - Full Transact SQL (68) Manual de soporte técnico para escuelas sobre windows 7 (42) Marco Teorico de Investigación de Operaciones (6) Medios de Almacenamiento (11) Medios de Networking (2) Mejorando la Interface de las Aplicaciones Windows (26) Memoria Tipos y Clases (5) Método (2) Metodología (1) Microsoft (324) Microsoft Lync 2010 (7) Microsoft Silverlight 4.0 (2) Microsoft Virtual Academy (356) Modelo (2) Modelo OSI y TCP-IP (2) Modelos con poco grado de dificultad de Programación Lineal - Investigación de Operaciones (13) Modelos con razonable grado de dificultad de Programación Lineal - Investigación de Operaciones (10) Modelos de desafio de Programación Lineal - Investigación de Operaciones (5) Modelos difíciles de Programación Lineal - Investigación de Operaciones (5) Modelos Fáciles de Programación Lineal - Investigación de Operaciones (13) Modelos lineales con solver (3) Modulo (23) Movimiento (2) Mozilla (29) MS SQL Server (77) MS Virtualization para Profesionales VMware - Gestión (3) MS Virtualization para Profesionales VMware- Plataforma (4) MVA (263) Negocio (2) Nivel Avanzado Desarrollo .Net (6) Nivel Básico Desarrollo .Net (11) Nivel Intermedio Desarrollo .Net (8) Normas técnicas peruanas y su evolución - Auditoría de Sistemas (1) Nube Privada - Avanzado (6) Nube Privada - Básico (6) Nube Privada - Intermedio (6) Office 365 (3) Optimización de Escritorio (10) Optimización de Escritorio - Avanzado (4) Optimización de Escritorio - Básico (3) Optimización de Escritorio - Intermedio (3) ORACLE 10g - ADMINISTRACIÓN Y ANÁLISIS (3) Oracle 10g y el Grid Computing (3) Organización aleatoria y secuencial (1) Partes principales de la Mainboard (12) Perceptron (2) Perfil (2) Periféricos de Entrada / Salida (15) Pesi (2) PHP y MySQL - Manual de aprendizaje para crear un sitio web - Autor : Olivier ROLLET (79) Plan (2) Plataforma (29) PMBOK (24) PMBOK - Guía de los fundamentos para la dirección de proyectos (24) PMBOK - INFLUENCIA DE LA ORGANIZACIÓN Y CICLO DE VIDA DEL PROYECTO (6) PMBOK - Introducción (11) PMBOK - PROCESOS DE LA DIRECCIÓN DE PROYECTOS (5) Prevención - Herramientas e Instrumentos de Medida (9) Principios básicos de enrutamiento y switching (185) Proceso (2) Proceso de auditoría de sistemas informáticos (2) Programación en Android - Auor : Salvador Gómez Oliver (46) Programación paso a paso de C# - Autor : Nacho Cabanes (16) Protocolos y comunicaciones de red (17) Proyecto (2) Qué es un sistema (4) Red de Área Local Inalámbrica (WLAN) (4) Redes (30) Redes inalámbricas - WIRELESS - Conocimiento general (15) Redes neuronales (2) Redes y Comunicaciones (45) Reparación de Fuentes - UPS - Estabilizadores (10) Reparación de Impresoras (9) Reparación de Monitores (16) Router (29) Seguridad en la Nube (3) Seminario (23) Server (24) Sharepoint 2010 - Nivel Básico (6) Sharepoint 2010 - Niveles Avanzados (18) Sharepoint 2010 - Niveles Avanzados - Básico (8) Sharepoint 2010 - Niveles Avanzados - Intermedio (9) Sinergia y recursividad (4) Sistema (33) Sistema de Cableado Estructurado (9) Software (30) SOLUCIÓN GRÁFICA DE MODELOS DE PROGRAMACIÓN LINEALES - INVOPE (8) Soporte a Infraestructura (3) SQL (38) SQL Azure - Introducción (3) Subsistemas de control (4) Tablas (4) Tarjeta Principal del Sistema (10) Tarjetas de Interfaces (7) Tecnología (31) Tecnologías LAN (1) TEORÍA GENERAL DE SISTEMAS (1) Tic (2) Tipo (2) TML5 y CSS3 - Autor: Christophe Aubry (12) Trabajando con el Formulario (7) Un diseño HTML5/CSS3: dConstruct 2011 (3) Un diseño HTML5/CSS3: FlipThru (2) Un diseño HTML5/CSS3: The Cat Template (2) Usando Controles Windows Forms (12) Usando Herramientas de Datos de Visual Studio (6) Ventas (2) Virtualización Hyper - V Nivel Básico (5) Virtualización Hyper - V Nivel Intermedio (5) What’s New in Windows 8.1 Security (4) Window (29) Windows 7 Segunda Fase - AVANZADO (4) Windows 7 Segunda Fase - BÁSICO (6) Windows 7 Segunda Fase - INTERMEDIO (4) Windows 8 - Vista Previa (4) Windows 8.1 To Go (2) Windows Azure (3) Windows Phone 7 (2) Windows Server 2008 R2 (3) Windows Server 2012 - Gestión y Automatización (3) Windows Server 2012 R2 Essentials (7) Windows Server 2012: Almacenamiento (5) Windows Server 2012: Identidad y Acceso (4) Windows Server 2012: Revisión Técnica (7) Xamarin (1)

Páginas vistas en total según Google