PDF de programación - Problemas y Algoritmos de Olimpiada de Informática

Problemas y Algoritmos

de Olimpiada de Informática

4

3

2

7

8

9

6

5

1

9 7 7 7 9 6 6

Por Luis E. Vargas Azcona

Algunas imagenes por Roberto López

2

Acuerdo de Licencia

Esta obra está bajo una licencia Atribución-No comercial-Licenciamiento Recíproco
2.5 México de Creative Commons.
Eres libre de:

copiar, distribuir y comunicar públicamente la obra

hacer obras derivadas

Bajo las condiciones siguientes:

Atribución. Debes reconocer la autoría de la obra en los términos especica-
dos por el propio autor o licenciante.

No comercial. No puedes utilizar esta obra para nes comerciales.

Licenciamiento Recíproco. Si alteras, transformas o creas una obra a partir
de esta obra, solo podrás distribuir la obra resultante bajo una licencia igual
a ésta.

Al reutilizar o distribuir la obra, tiene que dejar bien claro los términos de la
licencia de esta obra.

Alguna de estas condiciones puede no aplicarse si se obtiene el permiso del
titular de los derechos de autor.

Nada en esta licencia menoscaba o restringe los derechos morales del autor.

Los derechos derivados de usos legítimos u otras limitaciones reconocidas por ley no
se ven afectados por lo anterior.
Esto es solamente un resumen fácilmente legible del texto legal de la licencia. Para
ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-
sa/2.5/mx/ o envie una carta a Creative Commons, 171 Second Street, Suite 300,
San Francisco, California 94105, USA.

3

4

Prefacio

El propósito general de este libro, es el de introducir al lector en la resolución de
problemas de programación así como en el diseño de algoritmos.
Si bien se presentan algoritmos, el objetivo no es saturar el conocimiento del lector
con una gran cantidad de algoritmos sino mostar sus fundamentos, mostrar también
maneras inteligentes de usarlos para resolver problemas, y sobre todo, lograr que el
lector sea capaz de diseñar sus propios algoritmos.
Muchos libros de algoritmos se limitan a explicar algoritmos sin detenerse en su fun-
damento matemático y sin decir las aplicaciones que tiene en solución de problemas.
Algunos otros si explican el fundamento de los algoritmos, pero resultan inadecuados
para estudiantes con poco conocimiento matemático ya que suelen dar por hecho
que el lector ya sabe teoría de conjuntos y matemáticas discretas.
Este libro está dirigido a estudiantes con gusto de programar y resolver problemas
pero que todavía no adquieren las bases matemáticas necesarias para poder leer
libros de algoritmos con suciente fundamento matemático; por lo que se pretende,
no solamente explicar los algoritmos, sino también darle al lector las herramientas
necesarias para entender, analizar y diseñar.
Por ello, una gran cantidad de páginas se dedican a establecer las bases matemáticas
que sirven como soporte para la resolución de problemas de programación.
Los temas tratados en este libro son indispensables para comprender el gran campo
de estudio de la solución de problemas mediante el uso de las computadoras, consti-
tuyen los fundamentos de una cantidad interminable de conocimientos y técnicas que
estan en constante desarrollo por la investigación en las ciencias de la computación.
En el libro se muestran implementaciones en C++ que no usan memoria dinámica
ni estructuras, esto es por los siguientes motivos:

A veces al tener el pseudocódigo de un algoritmo, no resulta claro cómo im-
plementarlo sin escribir demasiado. Por ello es preferible mostrar algunas im-
plementaciones de ejemplo para que el lector conozca al menos una implemen-
tación corta de cada algoritmo.

Muchos elementos del lenguaje C++ son muy conocidos e incluso estan pre-
sentes en otros lenguajes, con una syntaxis casi idéntica a la de C++, por ello,

5

6

si se utilizan pocos elementos del lenguaje, es posible que un lector que no esté
familiarizado con este lenguaje pueda igualmente entender los códigos.

No está por demás decir que este libro fue escrito pensando en participantes
de un concurso llamado olimpiada de informática, en ese concurso los parti-
cipantes tienen tiempo limitado para implementar y depurar sus programas y
las implementaciones son mas fáciles de depurar con memoria estática.

Al Estudiante

Puede parecer extraño encontrar un libro de algoritmos con estas características,
ya que dedica muchas páginas a los fundamentos matemáticos y omite varias cosas
que varios libros de algoritmos orientados a licenciatura no dejarían pasar por alto,
como lo son quicksort, shellsort, listas circulares, listas doblemente ligadas y tablas
de dispersión entre otras cosas.
El motivo de esto es simple: este libro no pretende ser una referencia ni mucho menos
un repaso de los temas de licenciatura; pretende aportar las herramientas básicas
para aplicar la programación en la resolución de problemas.
Por esto mismo puede llegar a ser un recurso valioso ya que permite abordar la
programación desde un punto de vista mas creativo y menos repetitivo, y al mismo
tiempo el enfoque a resolver nuevos problemas es la base de la inovación.
Este libro esta hecho para leerse casi como si fuera una novela, un capítulo tras otro,
y si se decide saltarse uno o mas capítulos se corre el riesgo de que mas adelante no
se pueda seguir bien. La diferencia con una novela es la gran cantidad de problemas
de ejemplo, los cuales conviene intentar resolver antes de leer la solución.

Al Instructor

La teoría necesaria para leer este libro de principio a n es muy poca, incluso un
alumno de preparatoría la debería de saber. Sin embargo, muchos problemas que
se mencionan, por si dicultad, estan lejos de ser adecuados para cualquier alumno
de preparatoria e incluso pueden darle dicultades a graduados de la universidad;
pero resultan bastante adecuados para aquellos que buscan algo mas interesante que
problemas de rutina o para quienes se preparan para concursos de programación.
El libro está escrito de la manera en la que me gustaría presentar los temas si fuera
yo el instructor.
Es decir, procura motivar todos los conceptos antes de abordarlos formalmente,
intenta nunca dejar huecos, en la teoría; y sobre todo, buscar aplicaciones creativas
a cada tema que se aborda evitando decir muy rápido la solución y dando tiempo
para especular.

7

Para resolver un problema, es necesario plantearse un diálogo consigo mismo de
preguntas y respuestas. Dicho diálogo también se debe de presentar entre alumno e
instructor y en muchas partes del libro se intenta plasmar el diálogo abordando los
razonamientos que podrían llevar al lector a resolver cada uno de los ejemplos.

Al Olímpico

Este libro lo escribí pensando principalmente en los olímpicos, por lo que todo lo que
se menciona aquí tiene aplicación directa o indirecta con la olimpiada de informática.
La olimpiada esta centrada en resolver problemas mediante la programación y el
diseño de algoritmos; para ello se requieren bases matemáticas sólidas y un conoci-
miento profundo(aunque no necesariamente amplio) de los algoritmos.
Es por eso que este libro dedica muchas páginas a dejar claras las bases matemáticas
y a explorar las propiedades de algoritmos y no solo en introducirlos.
Los ejemplos se deben de intentar resolver por cuenta propia para aprender de
los propios errores e ir desarrollando poco a poco un método propio para resolver
problemas. Si de pronto no logras resolver un ejemplo, puedes empezar a leer la
solución para darte una idea y continuar por cuenta propia.

8

Índice general

I Recursión

13

1. Inducción Matemática

17
1.1. Ejemplos de Inducción . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.2. Errores Comunes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.3. Denición de Inducción . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.4. Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.4.1. Sumas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.4.2. Tablero de Ajedrez . . . . . . . . . . . . . . . . . . . . . . . . 27
1.4.3. Chocolate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

1.5. Sugerencias

2. Denición y Características de la Recursión

31
2.1. Factorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.2.
Imprimir Números en Binario . . . . . . . . . . . . . . . . . . . . . . 34
2.3. Los Conejos de Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . . 35

39
3. Recursión con Memoria o Memorización
3.1. Mejorando el Rendimiento de Fibonacci
. . . . . . . . . . . . . . . . 39
3.2. Error Común en la Memorización . . . . . . . . . . . . . . . . . . . . 41
3.3. Triangulo de Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.4. Teorema del Binomio . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4. Divide y Vencerás

45
4.1. Máximo en un Arreglo . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.2. Búsqueda Binaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.3. Torres de Hanoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5. Búsqueda Exhaustiva

53
5.1. Cadenas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.2. Conjuntos y Subconjuntos . . . . . . . . . . . . . . . . . . . . . . . . 57
5.3. Permutaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

9

10

II Análisis de Complejidad

ÍNDICE GENERAL

65

6. Técnicas Básicas de Conteo

69
6.1. Reglas Básicas de Conteo . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.2. Conjuntos, Subconjuntos, Multiconjuntos . . . . . . . . . . . . . . . . 73
6.3. Permutaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.4. Combinaciones
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6.5. Separadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

7. Funciones

83
7.1. Las Funciones como Reglas . . . . . . . . . . . . . . . . . . . .