PDF de programación - Apuntes de Programación

Roberto Bonvallet

Apuntes de Programaci´on

Editorial USM

Este material fue desarrollado en 2010 durante el proyecto de renovaci´on de la asignatura Progra-
maci´on de Computadores del Departamento de Inform´atica de la Universidad T´ecnica Federico Santa
Mar´ıa, bajo la coordinaci´on de Jos´e Miguel Herrera.

Originalmente en formato web, el apunte ha sido utilizado desde 2011 como referencia oficial de
la asignatura, que es cursada por todos los estudiantes de primer a ˜no de carreras de Ingenier´ıa de
la universidad.

El contenido original del apunte est´a disponible libremente en la p´agina web de la asignatura:
http://progra.usm.cl/apunte/.

Copyright: ©2013 Roberto Bonvallet.

Primera impresi´on: enero de 2013.

ISBN: 978-956-7051-67-0.

Impresi´on: CIPOD Ltda. Impresi´on por demanda. Fono (2) 2366555.

Parte I

Materia

1

Cap´ıtulo 1

Introducci´on a la programaci´on

Se suele decir que una persona no entiende algo de verdad hasta que puede
explic´arselo a otro. En realidad, no lo entiende de verdad hasta que puede
explic´arselo a un computador. — Donald Knuth.

Si tuvieramos que resumir el prop´osito de la programaci´on en una frase,

´esta deber´ıa ser:

que el computador haga el trabajo por nosotros.

Los computadores son buenos para hacer tareas rutinarias. Idealmente,
cualquier problema tedioso y repetitivo deber´ıa ser resuelto por un computador,
y los seres humanos s´olo deber´ıamos encargarnos de los problemas realmente
interesantes: los que requieren creatividad, pensamiento cr´ıtico y subjetividad.
La programaci´on es el proceso de transformar un m´etodo para resolver

problemas en uno que pueda ser entendido por el computador.

1.1 Algoritmos

La inform´atica se trata de computadores tanto como la astronom´ıa se trata
de telescopios. — Edsger Dijkstra.

Al dise ˜nar un programa, el desaf´ıo principal es crear y describir un proce-
dimiento que est´e completamente bien definido, que no tenga ambig ¨uedades,
y que efectivamente resuelva el problema.

As´ı es como la programaci´on no es tanto sobre computadores, sino so-
bre resolver problemas de manera estructurada. El objeto de estudio de la
programaci´on no son los programas, sino los algoritmos.

Un algoritmo es un procedimiento bien definido para resolver un problema.
Todo el mundo conoce y utiliza algoritmos a diario, incluso sin darse cuenta:

Una receta de cocina es un algoritmo; si bien podr´ıamos cuestionar que algunos
pasos son ambiguos (¿cu´anto es ((una pizca de sal))? ¿qu´e significa ((agregar a

3

4

CAP´ITULO 1. INTRODUCCI ´ON A LA PROGRAMACI ´ON

gusto))?), en general las instrucciones est´an lo suficientemente bien definidas
para que uno las pueda seguir sin problemas.
La entrada de una receta son los ingredientes y algunos datos como: ¿para
cu´antas personas se cocinar´a? El proceso es la serie de pasos para manipular
los ingredientes. La salida es el plato terminado.
En principio, si una receta est´a suficientemente bien explicada, podr´ıa permitir
preparar un plato a alguien que no sepa nada de cocina.

El m´etodo para multiplicar n ´umeros a mano que aprendimos en el colegio es
un algoritmo. Dado cualquier par de n ´umeros enteros, si seguimos paso a paso
el procedimiento siempre obtendremos el producto.
La entrada del algoritmo de multiplicaci´on son los dos factores. El proceso es
la secuencia de pasos en que los d´ıgitos van siendo multiplicados las reservas
van siendo sumadas, y los productos intermedios son finalmente sumados. La
salida del algoritmo es el producto obtenido.

Un algoritmo debe poder ser usado mec´anicamente, sin necesidad de usar

inteligencia, intuici´on ni habilidad.

A lo largo de esta asignatura, haremos un recorrido por los conceptos ele-
mentales de la programaci´on, con ´enfasis en el aspecto pr´actico de la disciplina.
Al final del semestre, usted tendr´a la capacidad de identificar problemas
que pueden ser resueltos por el computador, y de dise ˜nar y escribir programas
sencillos. Adem´as, entender´a qu´e es lo que ocurre dentro del computador
cuando usted usa programas.

Los computadores son in´utiles: s´olo pueden darte respuestas. — Pablo
Picasso.

Cap´ıtulo 2

Algoritmos

Un algoritmo es una secuencia de pasos para resolver un problema. Los
pasos deben estar muy bien definidos, y tienen que describir sin ambig ¨uedades
c´omo llegar desde el inicio hasta el final.

2.1 Componentes de un algoritmo

Conceptualmente, un algoritmo tiene tres componentes:

1. la entrada: son los datos sobre los que el algoritmo opera;

2. el proceso: son los pasos que hay que seguir, utilizando la entrada;

3. la salida: es el resultado que entrega el algoritmo.

El proceso es una secuencia de sentencias, que debe ser realizada en orden.
El proceso tambi´en puede tener ciclos (grupos de sentencias que son ejecutadas
varias veces) y condicionales (grupos de sentencias que s´olo son ejecutadas
bajo ciertas condiciones).

2.2 C´omo describir un algoritmo

Consideremos un ejemplo sencillo: un algoritmo para resolver ecuaciones

cuadr´aticas.
Una ecuaci´on cuadr´atica es una ecuaci´on de la forma ax2 + bx + c = 0,
donde a, b y c son datos dados, con a (cid:54)= 0, y x es la inc´ognita cuyo valor que se
desea determinar.
Por ejemplo, 2x2 − 5x + 2 = 0 es una ecuaci´on cuadr´atica con a = 2, b = −5
y c = 2. Sus soluciones son x1 = 1/2 y x2 = 2, como se puede comprobar
f´acilmente al reemplazar estos valores en la ecuaci´on. El problema es c´omo
obtener estos valores en primer lugar.

El problema computacional de resolver una ecuaci´on cuadr´atica puede ser

planteado as´ı:

5

6

CAP´ITULO 2. ALGORITMOS

Dados a, b y c, encontrar los valores reales de x que satisfacen
ax2 + bx + c = 0.

La entrada del algoritmo, pues, son los valores a, b y c, y la salida son las
ra´ıces reales x (que pueden ser cero, una o dos) de la ecuaci´on. En un programa
computacional, los valores de a, b y c deber´ıan ser ingresados usando el teclado,
y las soluciones x deber´ıan ser mostradas a continuaci´on en la pantalla.

Al estudiar ´algebra aprendemos un algoritmo para resolver este problema.
Es lo suficientemente detallado para que pueda usarlo cualquier persona,
(incluso sin saber qu´e es una ecuaci´on cuadr´atica) o para que lo pueda hacer
un computador. A continuaci´on veremos algunas maneras de describir el
procedimiento.

Lenguaje natural

Durante el proceso mental de dise ˜nar un algoritmo, es com ´un pensar y
describir los pasos en la misma manera en que hablamos a diario. Por ejemplo:

Teniendo los valores de a, b y c, calcular el discriminante ∆ =
b2 − 4ac. Si es discriminante es negativo, entonces la ecuaci´on no
tiene soluciones reales. Si es discriminante es igual a cero, entonces
la ecuaci´on tiene una ´unica soluci´on real, que es x = −b/2a. Si el
reales, que son x1 = (−b − √
discriminante es positivo, entonces la ecuaci´on tiene dos soluciones

∆)/2a y x2 = (−b +

√

∆)/2a.

Esta manera de expresar un algoritmo no es ideal, ya que el lenguaje natural

es:

impreciso: puede tener ambig ¨uedades;

no universal: personas distintas describir´an el proceso de maneras distintas; y

no estructurado: la descripci´on no est´a expresada en funci´on de componentes
simples.

A ´un as´ı, es posible identificar los pasos del algoritmo. Por ejemplo, hay
que evaluar la expresi´on b2 − 4ac, y ponerle el nombre ∆ a su resultado. Esto
se llama asignaci´on, y es un tipo de instrucci´on que aparece en casi todos los
algoritmos. Despu´es de eso, el algoritmo puede usar el nombre ∆ para referirse
al valor calculado.

Diagrama de flujo

Un diagrama de flujo es una representaci´on gr´afica de un algoritmo. Los
pasos son representados por varios tipos de bloques, y el flujo de ejecuci´on
es indicado por flechas que conectan los bloques, tal como se muestra en la
figura 2.1.

2.2. C ´OMO DESCRIBIR UN ALGORITMO

7

inicio

Leer a, b y c

∆ = b2 − 4ac

s´ı

¿∆ < 0?

no
¿∆ = 0?

no
√
x1 = (−b +
x2 = (−b − √

∆)/2a
∆)/2a

s´ı

x1 = −b/2a

Escribir “La ´unica
soluci´on es”, x1

Escribir “No

hay soluciones”

Escribir “La primera soluci´on es”, x1
Escribir “La segunda soluci´on es”, x2

fin

Figura 2.1: Diagrama de flujo del algoritmo para resolver la ecuaci´on cuadr´atica
ax2 + bx + c = 0.

8

CAP´ITULO 2. ALGORITMOS

leer a
leer b
leer c
discriminante = b2 − 4ac

si discriminante < 0:

escribir “La ecuaci´on no tiene soluciones reales”

o si no, si discriminante = 0:

x = −b/2a
escribir “La soluci´on ´unica es”, x

o si no:

x1 = (−b − √
√
x2 = (−b +
escribir “La primera soluci´on real es:”, x1
escribir “La segunda soluci´on real es:”, x2

discriminante)/2a
discriminante)/2a

Figura 2.2: Pseudoc´odigo del algoritmo para resolver la ecuaci´on cuadr´atica
ax2 + bx + c = 0.

El inicio y el final del algoritmo son representados con bloques circulares. El
algoritmo siempre debe ser capaz llegar desde uno hasta el otro, sin importar
por qu´e camino lo hace. Un algoritmo no puede ((quedarse pegado)) en la
mitad.

La entrada y la salida de datos son representadas con romboides,
Los diamantes representan condiciones en las que el algoritmo sigue uno de
dos caminos que est´an etiquetados con s´ı o no, dependiendo de si la condici´on
es verdadera o falsa.

Tambi´en puede haber ciclos, representados por flechas que regresan a

bloques anteriores. En este ejemplo, no hay ciclos.

Otras sentencias van dentro de rect´angulos. En este ejemplo, las sentencias

son asignaciones, representadas en la forma nombre = valor.

Los diagramas de flujo no son usados en la pr´actica para programar, pero

son ´utiles para ilustrar c´omo funcionan algoritmos sencillos.

Pseudoc´odigo

El pseudoc´odigo es una descripci´on estructurada de un algoritmo basada
en ciertas convenciones notacionales. Si bien es muy parecido al c´odigo que
finalmente se escribir´a en el computador, el pseudoc´odigo est´a pensado para
ser le´ıdo por humanos.

2.2. C ´OMO DESCRIBIR UN ALGORITMO

9

Una manera de escribir el algoritmo para la ecuaci´on cuadr´atica en pseu-

doc´odigo es la que se muestra en la figura 2.2.