Tipos de algoritmos. Tipos de algoritmos: lineal, ramificado, cíclico Tipos básicos de ejemplos de algoritmos

Los algoritmos pueden ser simples o complejos, pero todos tienen características comunes. En base a estas características se acostumbra distinguir tres tipos de algoritmos, con los que nos familiarizaremos.

En los algoritmos, los comandos se escriben uno tras otro en un orden determinado. No necesariamente se realizan en una secuencia escrita. Puede haber referencias internas a diferentes comandos.

En general, ejecutar comandos según un algoritmo recuerda un poco a los juegos de mesa, en los que los participantes se turnan para lanzar dados y caminar por el campo. Además, en los márgenes puede haber comentarios con el estilo: “Retroceder 2 celdas” o “Avanzar 5 celdas” (Fig. 1).

Arroz. 1. Juego de mesa ()

Un modelo más complejo para ejecutar el algoritmo es el conocido juego "Monopoly" o "Manager" (Fig. 2).

Arroz. 2. Juego "Monopolio" ()

La diferencia significativa entre este juego y simplemente ejecutar un algoritmo es que el objetivo final de los participantes no es completar el camino, sino acumular dinero a través de determinadas acciones.

Dependiendo del orden de ejecución del comando, se pueden distinguir tres tipos de algoritmos:

Algoritmos lineales;

Algoritmos de ramificación;

Algoritmos con repeticiones.

"Monopolio"

Monopoly es uno de los juegos de mesa más populares. Sus reglas son bastante simples y comprensibles para cualquiera que lo haya jugado al menos una vez (Fig. 4).

Arroz. 4. Juego "Monopolio" ()

Al principio, los jugadores tienen la misma cantidad de dinero en efectivo. Tirando los dados y moviendo sus fichas por el campo de juego en bucle, adquieren terrenos inmobiliarios de diferentes colores. Una vez en el sitio adquirido por el enemigo, el jugador está obligado a pagarle el alquiler establecido. Habiendo comprado todas las parcelas del mismo grupo de colores, el participante puede construir en ellas casas y hoteles, lo que aumenta el tamaño del alquiler. El objetivo de todo lo que sucede es banal: arruinar a todos los rivales.

Según fuentes oficiales, la empresa Parker Brothers, que produce Monopoly desde 1935 hasta el día de hoy, el legendario juego de mesa nació de la siguiente manera. En 1934, un ingeniero desempleado, Charles Darrow (Fig. 5), invitó a la oficina mencionada a publicar un juego que había inventado sobre el comercio de bienes raíces.

Arroz. 5. Charles Darrow ()

Habiendo descubierto 52 errores de diseño en el juego de mesa, los hermanos Parker rechazaron al inventor. Con puro espíritu empresarial estadounidense, fue a la imprenta, encargó 5 mil copias del juego y las vendió con bastante rapidez. Al darse cuenta de que las ganancias se les escapaban de las narices, Parker Brothers adquirió apresuradamente los derechos de Monopoly y, al año siguiente, se convirtió en el juego de mesa más vendido en los Estados Unidos y Darrow se convirtió en la encarnación viva del sueño americano.

Pero al mismo tiempo también hay juegos anteriores que recuerdan notablemente al Monopoly. ¿Resulta que Darrow fue simplemente el primero en intervenir y recibir una patente para el pasatiempo "popular"? Si y no. Las investigaciones de los últimos años han arrojado luz sobre el misterio de los orígenes del Monopoly.

En la segunda mitad del siglo pasado, el economista político Henry George vivió y trabajó en Estados Unidos. Propuso sustituir todos los impuestos por un único impuesto: el de la tierra. Imbuido de sus ideas, en enero de 1904 Magee recibió una patente para una computadora de escritorio. juego el El Juego del Propietario, que tiene reglas y apariencia Me recuerda al Monopoly de hoy. Se cree que el "Juego del propietario" tenía dos versiones de las reglas: después de jugar un juego bajo las leyes fiscales actuales, los jugadores cambiaban al modelo propuesto por George y supuestamente estaban convencidos de sus ventajas necesarias. Por tanto, el juego no era un entretenimiento, sino una herramienta de lucha ideológica.

No llegó a producirse en masa, pero The Landlord's Game se fue extendiendo poco a poco por Norteamérica en copias artesanales. Durante la Gran Depresión se produjo un gran interés por el juego de mesa: miles de desempleados estaban felices de imaginarse a sí mismos como bolsas de dinero, al menos en la mesa de juego. La aparición de un hombre emprendedor como Charles Darrow fue cuestión de meses, y apareció, llevándose la gloria del único inventor del Monopoly durante muchas décadas.

Por supuesto, hubo quienes consideraron necesario arrebatar una pieza a los titulares de los derechos de autor. Los monopolios sin licencia han inundado China. Y en nuestro país se han producido y se siguen produciendo hileras ordenadas de clones: “Broker”, “Cooperativa”, “Manager” (Fig. 6)...

Arroz. 6. Juego "Administrador" ()

A la luz del reciente replanteamiento del papel de Darrow en la creación de Monopoly y la expiración de los derechos de autor, dichas empresas no serán demandadas. Incluso si asumimos que no existió Elizabeth Magie en el mundo, las reglas del Monopoly hace tiempo que pasaron al dominio público. Sin embargo, Hasbro aún se reserva parte de la patente: el diseño de los chips, el diseño gráfico, la secuencia de celdas en el campo de juego.

Un algoritmo en el que los comandos se ejecutan en el orden en que fueron escritos, es decir, secuencialmente uno tras otro, se llama lineal.

Arroz. 3. Bombilla ()

Por ejemplo, el siguiente algoritmo para reemplazar una bombilla fundida es lineal (Fig.3):

1. apague el interruptor de la luz;

2. desenroscar la bombilla fundida;

3. enrosque una bombilla nueva;

4. Encienda el interruptor para comprobar que la luz está encendida.

Usando un diagrama de bloques, este algoritmo se puede representar de la siguiente manera:

(diagrama de bloques (Fig. 7.) ver al final del resumen)

Son extremadamente raras las situaciones en las que se conoce de antemano la secuencia de las acciones necesarias. En la vida, a menudo hay que tomar decisiones en función de la situación actual. Si llueve, cogemos un paraguas y nos ponemos un chubasquero; si hace calor, use ropa ligera. También existen condiciones de selección más complejas. En algunos casos, el destino futuro de una persona depende de la decisión elegida.

La lógica de decisión se puede describir de la siguiente manera:

SI<условие>, ESO<действия 1>,

DE LO CONTRARIO<действия 2>

SI tienes dinero, ENTONCES compra pan, DE LO CONTRARIO no lo compres.

SI estás en el centro hoy, ENTONCES llámame, DE LO CONTRARIO no me llames.

SI has aprendido tus lecciones, ENTONCES sal a caminar, DE LO CONTRARIO estudia tus lecciones.

En algunos casos<действия 2>puede estar ausente. Esto puede deberse tanto a su obviedad (como, por ejemplo, en el primer ejemplo: está claro que si no tienes dinero, simplemente no puedes comprar pan) como a la falta de necesidad.

SI<условие>, ESO<действия 1>

SI te llamas hongo de leche, ENTONCES métete atrás.

SI quieres estar sano, ENTONCES endurecete.

Una forma de organización de acciones en la que, dependiendo del cumplimiento o incumplimiento de alguna condición, se realiza una u otra secuencia de acciones, se denomina derivación.

Representemos en forma de diagrama de flujo la secuencia de acciones de un alumno de sexto grado que ha olvidado las llaves del apartamento, que imagina así: “Si mamá está en casa, vendré y me sentaré a hacer mi tarea. Si mi madre no está en casa, me voy a jugar al fútbol con mis amigos hasta que venga mi madre. Si no hay amigos afuera, me subiré a los columpios hasta que venga mi madre”.

(diagrama de bloques (Fig. 8.) ver al final del resumen)

Necesario y condiciones suficientes

Ya hemos comentado contigo que existen condiciones necesarias y suficientes.

Un ejemplo de condición necesaria sería:

Para convertirse en médico, es necesario obtener una educación médica.

La condición de tener formación médica es necesaria para ejercer como médico, pero no es suficiente. De hecho, no todos los graduados de las facultades de medicina se convierten en médicos.

Un ejemplo de condición suficiente sería:

Para hacerlo más fresco, simplemente enciende el aire acondicionado.

Esta condición es suficiente: si enciende el aire acondicionado, en realidad se enfriará. Sin embargo, esta condición no es necesaria, pues para lograr este objetivo puedes encender el ventilador, abrir la ventana, etc.

Por supuesto, existen condiciones necesarias y suficientes al mismo tiempo (tales condiciones se llaman equivalente). Por ejemplo:

Para que llegue el verano es necesario y suficiente que termine la primavera.

De hecho, si la primavera termina, llega el verano, y si la primavera no termina, el verano no puede llegar. Es decir, las condiciones para finales de primavera y principios de verano son equivalentes.

Los conceptos de condiciones necesarias, suficientes y equivalentes son muy importantes en una rama de las matemáticas como la lógica matemática. Además, se encuentran muy a menudo en la demostración de diversos teoremas.

En la práctica, suele haber problemas en los que es necesario repetir una o más acciones varias veces hasta que se cumpla alguna condición preestablecida.

Por ejemplo, si necesitamos clasificar una caja de manzanas para separar las podridas de las maduras, entonces debemos repetir los siguientes pasos:

1. Toma una manzana.

2. Mira si está podrido.

3. Si está podrido, tíralo; si no, ponlo en otra caja.

Este conjunto de acciones debes realizarlas hasta que se acaben las manzanas de la caja.

Se llama una forma de organizar acciones en la que se repite la misma secuencia de acciones hasta que se cumpla alguna condición preestablecida. ciclo (repetición).

Una situación en la que un bucle nunca termina se llama bucle.

Deberían desarrollarse algoritmos que no permitan este tipo de situaciones.

Considere el algoritmo para un despertador en un teléfono, que debería sonar a las 8:00 de la mañana y luego sonar cada 10 minutos hasta que se apague.

En este caso, su diagrama de bloques se ve así: (consulte el diagrama de bloques (Fig. 9) al final del resumen)

En esta lección, analizamos tres tipos de algoritmos: algoritmos lineales, algoritmos de ramificación y algoritmos de repetición.

En la próxima lección discutiremos la escritura de algoritmos en la práctica.

Tamiz de Eratóstenes

Recordemos la definición de número natural primo.

Un número natural se llama primo si sólo tiene dos divisores: uno y el número mismo. Los números restantes se llaman compuesto. Además, el número 1 no es primo ni compuesto.

Ejemplos de números primos: 2, 3, 5, 7.

Ejemplos de números compuestos: 4, 6, 8.

En el siglo III a.C., el matemático griego Eratóstenes propuso el siguiente algoritmo para encontrar todos los números primos menores que un número determinado. PAG:

1. escribe todos los números naturales del 1 al norte;

2. tachar 1;

3. subrayar el menor de los números no marcados;

4. tache todos los números que sean múltiplos del número subrayado en el paso anterior;

5. Si hay números sin marcar en la lista, vaya al paso 3; de lo contrario, todos los números subrayados son primos.

Este es un algoritmo cíclico. Cuando se ejecuta, se repiten los pasos 3-5 hasta que haya números sin marcar en la lista original.

Consideremos el resultado de este algoritmo. escribamos todo números primos del 1 al 25.

Anotemos los números del 1 al 25.

Tachemos el 1. Ahora subrayemos los dos. Tacha todos los números pares.

Como no todos los números están marcados, subrayamos el 3. Ahora tachamos todos los números que son divisibles por 3.

Como no todos los números están marcados, subrayamos el 5. Ahora tachamos el número 25.

Como no todos los números están marcados, enfatizamos el 7.

No se puede tachar nada, pero no todos los números están marcados, por eso subrayamos el 11.

No se puede tachar nada, pero no todos los números están marcados, por eso subrayamos el 13. Nuevamente, no se puede tachar nada: subrayamos el 17, luego el 19 y el 23.

Ahora todos los números están marcados.

Obtenemos números primos: 2, 3, 5, 7, 11, 13, 17, 19, 23.

Arroz. 7.Diagrama de flujo para cambiar una bombilla.

Arroz. 8. Diagrama de flujo de acciones para un alumno de sexto grado.

Arroz. 9. Diagrama de bloques del despertador.

Bibliografía

1. Bosova L.L. Informática y TIC: Libro de texto para 6º de primaria. - M.: BINOM. Laboratorio de Conocimiento, 2012.

2. Bosova L.L. Ciencias de la Computación: Cuaderno de trabajo para 6to grado. - M.: BINOM. Laboratorio de Conocimiento, 2010.

3. Bosova L.L., Bosova A.Yu. Lecciones de informática en los grados 5-6: Manual metodológico. - M.: BINOM. Laboratorio de Conocimiento, 2010.

1. Portal de Internet “Nuestra Red” ()

2. Portal de Internet “Hipermercado del Conocimiento” ()

3. Portal de Internet “kaz.docdat.com” ()

Tarea

1. §3.4 (Bosova L.L. Informática y TIC: Libro de texto para sexto grado).

2. Página 81 tareas 2, 6 (Bosova L.L. Informática y TIC: Libro de texto para sexto grado).

3. Página 82 tarea 9, 11, 13, 14 (Bosova L.L. Informática y TIC: Libro de texto para sexto grado).

4. * Página 83 tarea 15 (Bosova L.L. Informática y TIC: Libro de texto para sexto grado).

Anotación: El algoritmo es un concepto básico para quienes quieren iniciarse en la programación en cualquier lenguaje de programación. Cualquier tarea se puede formalizar algorítmicamente. Para entender por dónde empezar, veamos los principales tipos de algoritmos. El propósito de esta conferencia es presentar a los estudiantes el concepto de algoritmo; muestran que algo tan abstracto como un algoritmo nos rodea en la vida cotidiana.

Ejemplo de pseudocódigo:

alg Encontrar el cociente de dos números que comienzan con la salida ("establecer el dividendo y el divisor") entrada (dividendo, divisor) si divisor ≠ 0 entonces cociente = dividendo / divisor salida (cociente) de lo contrario salida ("sin solución") con alg Encontrar la cociente de dos numeros

Este ejemplo utiliza tres variables: dividendo, divisor y cociente. El dividendo y el divisor los especifica el artista con números arbitrarios. El cociente sólo se cuenta si el divisor no es cero.

La implementación gráfica del algoritmo es un diagrama de bloques. Un diagrama de bloques consta de bloques de cierta forma conectados por flechas. La respuesta la recibe una persona que ejecuta los comandos según el diagrama de flujo. Los diagramas de bloques se analizarán con más detalle en la Clase 2.

La implementación del software del algoritmo es programa de computadora, escrito en cualquier lenguaje de programación algorítmico, por ejemplo: C++, Pascal, Basic, etc. Un programa consta de comandos en un lenguaje de programación específico. Tenga en cuenta que el mismo diagrama de bloques se puede implementar en idiomas diferentes programación. En este caso, la respuesta la recibe una computadora, no una persona. Para obtener más información sobre cómo escribir programas en el lenguaje de programación C++, consulte la Clase 3.

Hay tres tipos principales de algoritmos:

1. algoritmo lineal,
2. algoritmo de ramificación
3. algoritmo cíclico.

Algoritmo lineal es un algoritmo en el que las acciones se realizan una vez y estrictamente de forma secuencial.

El ejemplo más simple de implementación de un algoritmo lineal es el camino a casa desde la universidad.

Una forma verbal de escribir este algoritmo:

1. salir de la universidad en la parada de autobús;
2. espere el autobús correcto;
3. tomar el autobús correcto;
4. pagar el viaje;
5. bajarse en la parada requerida;
6. llegar a casa.

Es obvio que este ejemplo se refiere al algoritmo lineal, porque todas las acciones se suceden una tras otra, sin condiciones ni repeticiones.

Hay tres tipos de algoritmos: lineal, ramificado y cíclico.

Tipo lineal de algoritmos.

Los algoritmos en los que las instrucciones se ejecutan una tras otra, independientemente de las condiciones, se denominan algoritmos de tipo lineal.

Por ejemplo, un algoritmo de cálculo que utiliza las fórmulas más simples que no tienen restricciones en los valores de las variables incluidas en ellas.

Ejemplo

Formulación del problema : Calcula el área de un círculo si se conoce el radio.

Dado : R es el radio del círculo.

Encuentra: S – área del círculo.

Solución: S=3.14R2

Forma verbal de escribir el algoritmo.

Elijamos el idioma ruso para escribir el algoritmo de esta forma y escribamos una secuencia de comandos, cuya ejecución en un valor de radio determinado nos permitirá encontrar el área:

Lea el valor R.

Multiplica el valor R por 3,14.

Multiplica el resultado de la segunda acción por el valor de R.

Registre el resultado como el valor S.

En el lenguaje de los diagramas de flujo - arroz. 8

Tipo de ramificación de algoritmos.

La resolución de problemas no siempre se puede presentar en forma de algoritmo lineal.

Los algoritmos en los que es necesario organizar la elección de una secuencia de acciones en función de algunas condiciones se denominan algoritmos de tipo ramificación.

En el método gráfico, la ramificación se organiza mediante un elemento lógico (diamante) que tiene una entrada y dos salidas. El propósito del elemento lógico es verificar una condición determinada. Dependiendo del cumplimiento (verdad) o incumplimiento (falsedad) de la condición que se esté verificando, se puede salir a la rama “Sí” o “No”, respectivamente.

Ejemplo

Formulación del problema : calcular
.

Dado: x – el valor del argumento.

Encontrar: y – valor de la función.

Solución:

y= x, si x  0

- x si x<0

Diagrama de bloques - ver fig. 9.

presentación verbal

En pseudocódigo :

Leer valor x

Si x>0, entonces

Fin de sucursal

Anota el valor

Destacar construcción condicional completa e incompleta .

Tipo cíclico de algoritmos.

Al desarrollar algoritmos para resolver una gama bastante amplia de problemas, a menudo surge la necesidad de repetir los mismos comandos una y otra vez.

Un algoritmo compilado utilizando múltiples repeticiones de las mismas acciones (ciclos) se llama algoritmos de tipo cíclico.

Sin embargo, "repetidamente" no significa "indefinidamente". La organización de bucles que nunca conduce a una parada en la ejecución del algoritmo (el llamado bucle) es una violación del requisito de su eficacia.

Al desarrollar un algoritmo de estructura cíclica, se distinguen los siguientes conceptos:

parámetro de bucle – un valor cuyo cambio está asociado con la ejecución repetida del ciclo;

valor inicial y final del parámetro ciclo ;

paso del ciclo – este es el valor por el cual el parámetro del bucle cambia con cada repetición.

El algoritmo cíclico consta de preparación del ciclo, cuerpo del ciclo, condiciones para continuar el ciclo .

EN preparación del ciclo incluye acciones relacionadas con la configuración de valores iniciales para un parámetro de ciclo (valores iniciales y finales, paso de parámetro).

EN cuerpo de bucle incluye: acciones repetidas para calcular las cantidades requeridas; preparar el siguiente valor del parámetro del bucle, preparar otros valores necesarios para la ejecución repetida de acciones en el cuerpo del bucle.

EN condición de continuación Se determina la necesidad de realizar más acciones repetitivas. Si el parámetro del bucle excede el valor final, se debe terminar el bucle.

Consideremos una representación gráfica del bloque cíclico del algoritmo (ver Fig. 10).

Los ciclos pueden ser con condición previa(cuando la condición se verifica antes del inicio del cuerpo del bucle) y con poscondición(cuando se verifica la condición después del primer paso por el cuerpo del bucle).

Bucle con poscondición