PDF de programación - Ejercicios de programación en Forth

EJERCICIOS DE

PROGRAMACI ÓN EN FORTH

F. J. Gil Chica

diciembre, 2009

Capítulo 1

Enunciados

1.1. Consideraciones previas

Esta es una colección de ejercicios de programación en Forth. Abarcan
desde manipulación básica de la pila hasta cálculo numérico y creo que son
ilustrativos del lenguaje y de la forma en que se programa con él.

Respecto a lo primero, hemos omitido algunos temas más avanzados de
los que podrían componerse ejercicios que involucrasen el uso de immediate,
postpone, catch y throw, por ejemplo.

Respecto a lo segundo, observará el lector en primer lugar que hemos
compuesto todos los ejercicios sin intervención de variables: todos los cálculos
se basan en la pila. En general, esto es más elegante y ajustado a la filosofía del
lenguaje, aunque reconocemos que algunos de los ejercicios hubiesen quedado
más claros y limpios introduciendo variables locales. Pero no se olvide lo
que son: ejercicios. También observará el lector que en general las palabras
son muy pequeñas. Si reunimos el vocabulario contenido en este texto y lo
compilamos (usamos Gforth) veremos que la media es inferior a 100 bytes
por palabra. No obstante, hay algunas pocas de estructura muy lineal que
son inusualmente largas para el lenguaje, aunque muy breves comparadas
con el tamaño medio de las funciones en cualquier otro lenguaje. En estos
pocos casos, es obvia la forma en que pueden factorizarse.

1.2. Manipulación de la Pila

Salvo indicación contraria, se suponen operaciones con números enteros.

1. Escribir una palabra que produzca el efecto en la pila (a b -- a+1

b-1 a+b).

1

2. Escribir una palabra que produzca el efecto en la pila (a b -- a*a

a*b).

3. Dados tres números en la pila, (a, b, c), calcular d = b2

− 4ac.

4. Escribir una palabra que tome dos números (a, b) de la pila y deje como

resultado (a − b) y (a + b).

5. Escribir una palabra que tome tres números (a, b, c) de la pila y deje

como resultado a2 + b2 + c2.

6. Escribir una palabra que tome un número n de la pila y deje como

resultado n2

− 5n + 6.

7. Escribir una palabra que tome una dirección de la pila y deje la misma
dirección incrementada en una celda y el valor contenido en la dirección
original.

8. Escribir una palabra que tome dos direcciones de la pila y deje am-
bas direcciones incrementadas en una unidad y los contenidos de las
direcciones originales ( d1 d2 -- d1+1 d2+1 v1 v2).

9. Escribir una palabra que tome dos direcciones de la pila e intercambie

sus contenidos.

10. Escribir una palabra que produzca el efecto en la pila (a b>0 -- a*b)
sin usar la multiplicación. Una multiplicación no es más que una suma
repetida.

11. Escribir una palabra que produzca el efecto en la pila (a b -- a/b
a %b) es decir, que tome dividendo y divisor y deje cociente y resto, sin
usar la división. Una división no es más que una resta repetida.

12. Implementar las palabras rot y -rot.

13. Implementar la palabra 2swap cuyo efecto sobre la pila es (a b c d

-- c d a b).

14. Implementar la palabra tuck, cuyo diagrama de pila es (a b -- b a

b).

15. Implementar 2drop, que elimina los dos elementos superiores de la pila.
Implementar la palabra 2dup, cuyo diagrama de pila es (a b -- a b
a b). Escribir la palabra 2over cuyo efecto sobre la pila es ( a b c d
-- a b c d a b.

2

16. Implementar la palabra 3dup, cuyo efecto sobre la pila es ( a b c --

a b c a b c).

17. Escribir una palabra que elimine todo elemento de la pila sólo en el

caso de que la pila contenga algún elemento que eliminar.

18. Escribir una palabra llamada pick (totalmente desaconsejable su uso)
que trate a la pila como un vector, copiando el elemento n que se indique
en la cima de la pila. n numera los elementos de la pila desde el más
reciente, 0, al más profundo, y no se cuenta a sí mismo (ej. si la pila
contiene 1, 2 y 3, 1 2 3 2 pick tiene como resultado 1 2 3 1)

1.3. Memoria

1. Escribir una palabra que recupera el valor contenido en una dirección
de memoria, dejando en la pila la dirección original incrementada en
una unidad (o en una celda), y el valor recuperado.

2. Escribir una palabra que intercambia los valores contenidos en dos di-

recciones de memoria.

3. Escribir una palabra que copia en la pila el último elemento apilado en

la pila de retorno.

4. Escribir una palabra que toma de la pila una dirección origen y una
dirección destino, copia el valor contenido en la dirección origen en la
dirección destino y devuelve en la pila las direcciones originales incre-
mentadas en una unidad.

5. Escribir una palabra que toma de la pila dos direcciones, una origen y
otra destino, y un número n, copiando n bytes a partir de la dirección
origen en las n posiciones correlativas a partir de la dirección de destino.

6. Escribir una palabra que tome de la pila dos direcciones y devuelva:
ambas direcciones incrementadas en una unidad y los valores contenidos
en las direcciones originales.

7. Escribir una palabra que desplaza una porción de memoria el número

de posiciones que se indique hacia ((arriba)). Idem hacia ((abajo)).

8. Un bloque de memoria se especifica mediante un dirección base y un
tamaño en bytes. Escribir dos palabras que esperen en la pila la espe-
cificación de un bloque y un entero que represente cuántos bytes ese

3

bloque ha de ser desplazado, y efectúe el desplazamiento. El despla-
zamiento puede hacerse ((hacia arriba)) o ((hacia abajo)), de ahí las dos
palabras.

1.4. Números enteros

1. Escribir una palabra que tome dos números de la pila y deje el máximo
común divisor de ambos. Si a y b son estos números y suponemos
que a > b, úsese la propiedad de que mod(a, b) = mod(b, r), donde r
es el resto de la división entera a/b. Por aplicación repetida de esta
propiedad, puede demostrarse que el valor buscado es el del primer
argumento cuando el segundo se hace nulo.

2. Dos números se llaman primos si el máximo común divisor a ambos es
1. Escribir una palabra que tome dos números y deje verdadero o falso
según sean primos o no.

3. Escribir una palabra que busque el mínimo divisor (distinto de 1) de

un número dado en la pila.

4. Basándose en el ejercicio anterior, escribir una palabra que deje un flag
en la pila indicando si el número depositado en ella es o no primo: (n
-- flag).

5. Imprimir todos los números primos entre dos dados.

6. Escribir una palabra que produzca la descomposición en factores primos

de un número dado.

7. Dado un número n y una base b, encontrar la potencia p tal que bp <

n <= bp+1.

8. Dada una función entera de argumento entero f (n), encontrar la su-

matoria

N

Xi=0

f (i)

(1.1)

Se esperan en la pila N y la dirección de f .

9. Dados dos enteros en la pila representando un racional (numerador, de-
nominador), encontrar el máximo común divisor de ambos y dividirlos
por él. El resultado es la fracción canónica del número original (ej. 9/27
se reduce a 1/3).

4

10. Escribir palabras qrot, -qrot, qtuck y qnip aptas para manipular
números racionales (cada número racional ocupa dos celdas de la pila).

11. Un número racional se representa mediante dos enteros depositados en
la pila: el numerador y el denominador. Escribir palabras para la suma,
resta, multiplicación y división de racionales.

12. Dados dos números en la pila, n y k, calcular el coeficiente binomial

Cn,k =

n!

k!(n − k)!

(1.2)

13. Un algoritmo sencillo para generar números aleatorios parte de una

semilla n0 y calcula según

nj+1 = (anj + c) %m

(1.3)

En concreto, cuando a = 899, c = 0 y m = 32768 se generan números
en el intervalo [0, 32767]. Escribir un generador de números aleatorios.

14. Dado un número p encontrar el mayor n <= √p.
15. Dado un número p y una raíz aproximada n <= √p encontrar la re-
presentación racional de una mejor aproximación de acuerdo con la
fórmula:

nk+1 =

1

2 nk +

p

nk

(1.4)

16. Dado un número entero, escribir una palabra que imprima su represen-

tación en binario.

17. Dado un entero, escribir una palabra que imprima su representación en

hexadecimal.

18. Dado un entero n, escribir una palabra que consulte el valor del bit p,

dejando un 0 o 1 en la pila según que dicho bit esté a 0 o 1.

19. Dado un entero n y un número p, escribir palabras para activar y

desactivar el bit p de n.

20. Un número complejo, con partes reales e imaginaria enteras, se repre-
senta en la pila mediante dos enteros: parte real y parte imaginaria.
Escribir palabras para sumar, restar, multiplicar y obtener una poten-
cia de un complejo.

5

21. Dados dos complejos a + bj y c + dj, se define su razón como

a + bj
c + dj

=

ac + bd
c2 + d2 +

bc − ad
c2 + d2 j

(1.5)

Implementar una palabra que efectúa la división. Puesto que las par-
tes reales e imaginaria ya no son enteros, sino racionales, la palabra
dejará en la pila primero los numeradores, real e imaginario, y luego el
denominador, común.

1.5. Vectores

Consideramos por simplicidad vectores de números enteros. La versión
para números reales es obvia. Nos apoyaremos en el tipo vector. Al escribir

10 vector X

Se espera que sea creado en el diccionario un vector de 10 elementos. Un
vector de 10 (n) elementos ocupa 11 (n+1) celdas en el diccionario, pues
la primera de ellas contiene el tamaño del vector. En tiempo de ejecución,
la palabra X creada anteriormente se espera que deje en la pila la dirección
del primer elemento y el número de elementos. Para los diagramas de pila,
usaremos las letras i para un índice, v para un valor, d para una dirección y
N para el número de elementos del vector.

1. Escribir una palabra, vector que cree en el diccionario un vector con
el número de elementos depositado en la pila y la estructura explicada.

2. Escribir una palabra v! que espere en la pila un valor, la posición donde
quiere guardarse, el tamaño del vector y su dirección. (ej. 4 10 X v!
almacena el valor 4 en la posición 10 del vector X; las