PDF de programación - Algoritmos a fondo: con implementaciones en C y Java

Algoritmos a fondo

Con implementaciones en C y Java

Ing. Pablo Augusto Sznajdleder

Sznajdleder, Pablo
Algoritmos a fondo : con implementaciones en C y Java . - 1a ed. -
Buenos Aires : Alfaomega Grupo Editor Argentino, 2012
576 p. ; 24x21 cm.

ISBN 978-987-1609-37-6

1. Informática. I. Título
CDD 005.3

Queda prohibida la reproducción total o parcial de esta obra, su tratamiento informático y/o la transmisión por cualquier otra forma o medio
sin autorización escrita de Alfaomega Grupo Editor Argentino S.A.
Edición: Damián Fernández
Revisión de estilo: Vanesa García y Juan Micán
Diagramación: Diego Ay
Revisión de armado: Vanesa García

Internet: http://www.alfaomega.com.mx
Todos los derechos reservados © 2012, por Alfaomega Grupo Editor Argentino S.A.
Paraguay 1307, PB, ofi cina 11
ISBN 978-987-1609-37-6
Queda hecho el depósito que prevé la ley 11.723
NOTA IMPORTANTE: La información contenida en esta obra tiene un fi n exclusivamente didáctico y, por lo tanto, no está previsto su
aprovechamiento a nivel profesional o industrial. Las indicaciones técnicas y programas incluidos han sido elaborados con gran cuidado
por el autor y reproducidos bajo estrictas normas de control. Alfaomega Grupo Editor Argentino S.A. no será jurídicamente responsable
por: errores u omisiones; daños y perjuicios que se pudieran atribuir al uso de la información comprendida en este libro, ni por la utilización
indebida que pudiera dársele.
Los nombres comerciales que aparecen en este libro son marcas registradas de sus propietarios y se mencionan únicamente con fi nes
didácticos, por lo que Alfaomega Grupo Editor Argentino S.A. no asume ninguna responsabilidad por el uso que se dé a esta información,
ya que no infringe ningún derecho de registro de marca. Los datos de los ejemplos y pantallas son fi cticios, a no ser que se especifi que lo
contrario.
Los hipervínculos a los que se hace referencia no necesariamente son administrados por la editorial, por lo que no somos responsables de
sus contenidos o de su disponibilidad en línea.

Empresas del grupo:
Argentina: Alfaomega Grupo Editor Argentino, S.A.
Paraguay 1307 P.B. “11”, Buenos Aires, Argentina, C.P. 1057
Tel.: (54-11) 4811-7183 / 0887 - E-mail: [email protected]
México: Alfaomega Grupo Editor, S.A. de C.V.
Pitágoras 1139, Col. Del Valle, México, D.F., México, C.P. 03100
Tel.: (52-55) 5575-5022 - Fax: (52-55) 5575-2420 / 2490. Sin costo: 01-800-020-4396
E-mail: [email protected]
Colombia: Alfaomega Colombiana S.A.
Carrera 15 No. 64 A 29, Bogotá, Colombia
PBX (57-1) 2100122 - Fax: (57-1) 6068648 - E-mail: [email protected]
Chile: Alfaomega Grupo Editor, S.A.
Doctor La Sierra 1437 - Providencia, Santiago, Chile
Tel.: (56-2) 235-4248 - Fax: (56-2) 235-5786 - E-mail: [email protected]

Superman, por Octaviano Sznajdleder

A los amores de mi vida: mi esposa Analía y mi hijo Octaviano.
Ellos son el motor que impulsa todo lo que hago.

A la memoria de Naum, quien pasó a vivir en nuestros corazones.
Siempre me preguntaba: —¿Cómo va ese libro, Pablo?

V

A mi mamá Nélida, que no solo pone su casa a mi disposición sino que,
además, siempre me prepara el té.

Agradecimientos

A mi editor y amigo Damián Fernández, que no para de ofrecerme
inmejorables oportunidades.

A Graciela Sosisky y Domingo Mandrafi na quienes, hace ya varios
años, me dieron la oportunidad de incorporarme a la cátedra de
Algoritmos.

A Adriana Adamoli por su colaboración y por el aporte de muchos
de los ejercicios que se encuentran en la Web.

A Juan Grande quien, GTalk mediante, siempre estuvo presente
para darme una mano.

A Marcelo Grillo, Gustavo Baez y a todos los promotores de Alfaomega
por la amabilidad, la cordialidad y la excelente estadía que me han
hecho pasar durante mi viaje a México.

A los maestros Alberto Templos Carbajal, Sergio Fuenlabrada y Edna
Miranda por sus valiosísimos aportes.

Algorítmos a fondo - Ing. Pablo A. Sznajdleder

VII

Mensaje del Editor

Los conocimientos son esenciales en el desempeño profesional. Sin ellos es imposible
lograr las habilidades para competir laboralmente. La universidad o las instituciones de
formación para el trabajo ofrecen la oportunidad de adquirir conocimientos que serán
aprovechados más adelante en benefi cio propio y de la sociedad. El avance de la ciencia
y de la técnica hace necesario actualizar continuamente esos conocimientos. Cuando
se toma la decisión de embarcarse en una vida profesional, se adquiere un compromiso
de por vida: mantenerse al día en los conocimientos del área u ofi cio que se ha decidido
desempeñar.
Alfaomega tiene por misión ofrecerles a estudiantes y profesionales conocimientos ac-
tualizados dentro de lineamientos pedagógicos que faciliten su utilización y permitan de-
sarrollar las competencias requeridas por una profesión determinada. Alfaomega espera
ser su compañera profesional en este viaje de por vida por el mundo del conocimiento.
Alfaomega hace uso de los medios impresos tradicionales en combinación con las tec-
nologías de la información y las comunicaciones (IT) para facilitar el aprendizaje. Libros
como este tienen su complemento en una página Web, en donde el alumno y su profesor
encontrarán materiales adicionales, información actualizada, pruebas (test) de autoeva-
luación, diapositivas y vínculos con otros sitios Web relacionados.
Esta obra contiene numerosos gráfi cos, cuadros y otros recursos para despertar el inte-
rés del estudiante, y facilitarle la comprensión y apropiación del conocimiento.
Cada capítulo se desarrolla con argumentos presentados en forma sencilla y estructu-
rada claramente hacia los objetivos y metas propuestas. Cada capítulo concluye con
diversas actividades pedagógicas para asegurar la asimilación del conocimiento y su
extensión y actualización futuras.
Los libros de Alfaomega están diseñados para ser utilizados dentro de los procesos de
enseñanza-aprendizaje, y pueden ser usados como textos guía en diversos cursos o
como apoyo para reforzar el desarrollo profesional.
Alfaomega espera contribuir así a la formación y el desarrollo de profesionales exitosos
para benefi cio de la sociedad.

Algorítmos a fondo - Ing. Pablo A. Sznajdleder

VIII

Pablo Augusto Sznajdleder
Es Ingeniero en Sistemas de Información, egresado de la Universidad Tecnológica Na-
cional (UTN-FRBA) en 1999.
Actualmente, es profesor en la cátedra de “Algoritmos y Estructura de Datos” en la UTN-
FRBA, pasando también por la Universidad Nacional de San Martín (UNSAM) y el Institu-
to de Tecnología ORT Argentina.
Trabajó como instructor Java para Sun Mycrosystems, Oracle e Informix/IBM entre otras
empresas líderes.
Desde 1995 trabaja en sistemas, principalmente, en el desarrollo de aplicaciones empre-
sariales distribuidas: primero en C/C++ y luego, en Java/JEE.
En 1996 comenzó a trabajar con Instructor Java para Sun Microsystems y, desde el 2000,
se desempeña como consultor en la búsqueda y selección de RRHH capacitados en
dicha tecnología, poniendo especial atención en la identifi cación de jóvenes estudiantes
sin experiencia laboral previa, pero con gran potencial profesional.
Tiene las certifi caciones internacionales Sun Certifi ed Java Programmer (SCJP, 1997) y
Sun Certifi ed Java Developer (SCJD, 1998) y, además, está certifi cado como Instructor
Ofi cial Java por Sun Microsystems (1997).
En el 2008 publicó HolaMundo.pascal, Algoritmos y estructura de datos cuyo contenido
cubre por completo los temas que abarca la asignatura de igual nombre en UTN-FRBA.
En el 2009 participó como revisor técnico en el libro Análisis y diseño de algoritmos (Ló-
pez, Jeder, Vega). En el 2010 publicó su libro sobre desarrollo de aplicaciones Java: Java
a fondo, Estudio del lenguaje y desarrollo de aplicaciones.

Revisor técnico: Alberto Templos Carbajal
Es Ingeniero en computación de la Facultad de Ingeniería de la UNAM y ejerce, desde 1983,
como Profesor de dicha facultad en las Divisiones de Ingeniería Eléctrica en distintas asig-
naturas de la carrera de Ingeniería en Computación y Educación Continua. Desde 1986, es
Profesor a tiempo completo y ha ocupado los siguientes cargos: Coordinador de las carre-
ras de Ingeniero en Computación y, de manera temporal, de Ingeniero Eléctrico Electrónico
e Ingeniero en Telecomunicaciones, Jefe del Departamento de Ingeniería en Computación,
Secretario Académico de las Divisiones de Ingeniería Eléctrica y Estudios de Postgrado y
Coordinador de Postgrado en la Secretaría de Postgrado e Investigación de la Facultad de
Ingeniería. También ha sido cofundador de dos empresas de computación y asesor en esa
misma área de diversas compañías.
Actualmente, es miembro de diferentes comités, evaluador de planes de estudio del área
de computación para diferentes organismos nacionales y es responsable de un proyecto de
investigación e innovación tecnológica sobre el Diseño de algoritmos para robots. Su produc-
tividad, principalmente, está orientada a la docencia.

Algorítmos a fondo - Ing. Pablo A. Sznajdleder

Contenido

Modulo 1
Programación estructurada

1.

1.2.1
1.2.2

Introducción a los algoritmos y a la
programación de computadoras .......................................... 1
1.1 Introducción ................................................................................. 2
1.2 Concepto de algoritmo ............................................................... 2
Defi nición de algoritmo y problema ............................... 2
Análisis del enunciado de un problema ......................... 3
Análisis del problema ........................................ 3
1.2.2.1
1.2.2.2 Datos de entrada .............................................. 3
1.2.2.3 Datos de salida ................................................. 4
1.2.3 Memoria y operaciones aritméticas y lógicas ................ 4
1.2.4
Teorema de la programa