PRÁCTICA Nº 2: 1 sesión

PRÁCTICA Nº 3: 1 sesión

(Semana del 27 de marzo al 31 de marzo de 2000)

Simulación de un solitario elemental
0. OBJETIVOS

Reutilización de programas

Diseño e implementación de la estructura de datos Cola.

Uso intensivo de las primitivas de Pilas y Colas

Organizar eficientemente un programa

1. Especificación de Los Tipos de datos relacionados con la baraja

En primer lugar escribiremos una pequeña unidad donde especificaremos el tipo Valor que utilizaremos en pilas y colas. La unidad se llamará U_Tipo y contendrá básicamente las definiciones de tipos y constantes que utilizaremos en las unidades y en el programa principal. Estos tipos y constantes son los siguientes:

UNIT

U_Tipo;

INTERFACE

Const

NumPalos = 4;

CartasPorPalo = 12;

Type

Palo = 1..NumPalos;

Numero = 1..CartasPorPalo;

Carta = Record

PaloCarta: Palo;

NumCarta: Numero;

End;

Valor = Carta;

IMPLEMENTATION

BEGIN

END.
2. ESPECIFICACION DE LA ESTRUCTURA DE DATOS "COLA".

La segunda tarea de esta práctica consiste en escribir dos unidades "UPiCov" y "UPiCop" en las que tendremos la implementación de la estructura de datos Pila que hicimos en la práctica número 2 y en la que adjuntaremos ahora la correspondiente a la estructura de datos "Cola", representada mediante vectores en la unidad "UPiCov" y mediante punteros en la unidad "UPiCop".

La unidad relacionada con Arrays tendrá la siguiente cabecera:

UNIT

UPiCov;

INTERFACE

Uses

U_Tipo;

Const

MAX = NumPalos * CartasPorPalo + 1;

Type

Pila = Record

Info: Array[1..MAX] of Valor;

Cima: 0..MAX

End;

Cola = Record

Info: Array[1..MAX] of Valor;

Ini, Fin: 0..MAX;

End;

Procedure Crear_Pila ( Var sta: Pila );

Function Pila_Vacia ( sta: Pila ): Boolean;

Function Apilar ( Var sta: Pila; x: Valor ): Boolean;

Function Desapilar ( Var sta: Pila ): Boolean;

Function Cima_Pila ( sta: Pila; var x: Valor ): Boolean ;

Procedure Crear_Cola ( Var que: Cola );

Function Cola_Vacia ( que: Cola ): Boolean;

Function Encolar ( Var que: Cola; x: Valor ): Boolean;

Function Desencolar ( Var que: Cola ): Boolean;

Function Primero_Cola ( que: Cola; Var x: Valor ): Boolean;

IMPLEMENTATION

{* Escribir el código de las operaciones anteriores, las de Pilas representadas

mediante vectores ya las tenemos, así que sencillamente las tendremos que adjuntar

aquí. Nos queda por implementar las primitivas correspondientes a las Colas. Hay que

tener en cuenta que vamos a trabajar con una cola circular, por lo que

implementaremos la función Siguiente, tal y como se ha explicado en clase. *}

BEGIN

END.

La unidad relacionada con Punteros tendrá la siguiente cabecera:

UNIT

UPiCop;

INTERFACE

Uses

U_Tipo;

Type

Ptro = ^Nodo;

Nodo = Record

Info: Valor;

Sig : Ptro;

End;

Pila = Record

Cima: Ptro;

End;

Cola = Record

Ini, Fin: Ptro;

End;

Procedure Crear_Pila ( Var sta: Pila );

Function Pila_Vacia ( sta: Pila ): Boolean;

Function Apilar ( Var sta: Pila; x: Valor ): Boolean;

Function Desapilar ( Var sta: Pila ): Boolean;

Function Cima_Pila ( sta: Pila; var x: Valor ): Boolean ;

Procedure Crear_Cola ( Var que: Cola );

Function Cola_Vacia ( que: Cola ): Boolean;

Function Encolar ( Var que: Cola; x: Valor ): Boolean;

Function Desencolar ( Var que: Cola ): Boolean;

Function Primero_Cola ( que: Cola; Var x: Valor ): Boolean;

IMPLEMENTATION

{* Escribir el código de las operaciones anteriores, las de Pilas mediante punteros ya

las tenemos, así que sencillamente las tendremos que adjuntar aquí. Nos queda por

implementar las primitivas correspondientes a las Colas representadas mediante

punteros. *}

BEGIN

END.

3. REALIZACION DE UN PROGRAMA QUE SIMULE UN SOLITARIO ELEMENTAL

Vamos a simular un solitario muy elemental, pero que hará que nos familiaricemos con los subprogramas que hemos implementado en las unidades.

Se trata de simular una baraja española (4 palos, 12 cartas por palo) que tras barajarla la disponemos en una cola. Además, tenemos cuatro pilas, una por cada palo, en las que iremos apilando las cartas en orden ascendente, En cada paso se examina la primera carta de la cola y se desencola; si se puede apilar en alguna de las pilas, la apilamos, en caso contrario la volvemos a encolar. En cada momento estaremos al tanto del número de cartas examinadas y de las que ya llevamos apiladas.

Para facilitar el diseño y la implementación, ofrecemos algunas guías que, por otra parte, será muy conveniente utilizar.

Program Solitario ( Input, Output );

Uses

Crt, U_Tipo, UPiCo(?);

Const

TotalCartas = NumPalos * CartasPorPalo; {* definidos en la unidad *}

Type

Indice = 1..TotalCartas;

{* Especificamos una baraja como un array de Cartas *}

Baraja = Array[Indice] of Carta;

{* Creamos el tipo Mazos, que representa las cuatro pilas de cartas *}

Mazos = array[1..NumPalos] of Pila

Deberemos implementar, primeramente tres subprogramas:

1. Procedure Inicia_Baraja ( Var bar: Baraja );

Que simule el disponer en ‘bar’ la baraja completa y ordenada.

2. Procedure Mezclar_Baraja ( Var bar: Baraja );

Que simule el hecho de mezclar (barajar) las cartas de la baraja. Nos ayudaremos de la función random, que como sabéis sirve para generar números al azar.

Una forma de conseguir barajar las cartas podría ser la siguiente:

Primero elegimos un número al azar entre el 1 y el 48 (el total de cartas), escogemos la carta elegida y la intercambiamos con la primera, después elegimos un número entre el 2 y el 48, la elegida la intercambiamos con la segunda y así sucesivamente hasta tener todas las cartas "mezcladas".

3. Function Encola_Baraja ( Var que: Cola; bar: Baraja ): Boolean;

Que encola la baraja recibida en una cola de cartas. Si ocurre algún error, devolverá FALSE.

El programa principal empezará iniciando y mezclando una baraja y encolándola en una cola de cartas.

A continuación se mostrará la cola de cartas a través de una función que mostrará toda la información contenida en la cola de cartas y el estado de las cuatro pilas que al principio estarán vacías por pantalla.

Function Muestra_Cola_Cartas( Var que: Cola ): Boolean;

Function Muestra_Pilas_Cartas ( maz: Mazos ): Boolean;

Tras ello, se entrará en un bucle que esperará la pulsación de una tecla. Si el usuario pulsa ESC se finaliza el programa, en caso contrario se ha de examinar la primera carta de la cola y si se puede apilar se apilará en la pila adecuada, en caso contario se encola de nuevo en la cola de cartas. Una vez hecho esto se vuelve a mostrar la cola de cartas y las cimas de las cuatro pilas, así como el total de cartas examinadas y el número de cartas que ya se han conseguido apilar. De esta forma, la cola irá menguando de tamaño conforme se van apilando las cartas en los mazos correspondientes

Si se termina el solitario se finaliza el programa.

Una pregunta difícil, sólo para los que les gusta pensar y que no se tendrá en cuenta en la evaluación del programa: ¿Cuántas cartas por termino medio se han de examinar antes de finalizar el solitario?. Dejad que el programa realice sólo el solitario varias veces e intentar encontrar al menos una respuesta empírica.

3. Entrega de programas

Al finalizar la sesión se entregarán las unidades U_Tipo.pas, UPiCov.pas y UPiCop.pas, junto con el programa principal solit.pas

NOTA: Se recuerda a los alumnos que las normas de corrección siguen vigentes y que por lo tanto se tendrán en cuenta a la hora de evaluar la práctica. Uno de los puntos es la presentación correcta de las prácticas siguiendo la Guía de Estilo de Pascal.

Recordar también la necesidad de entregar una hoja con las tareas que se van a realizar en la práctica para poder acceder al laboratorio.

ENTREGA DE PROGRAMAS: Al finalizar la sesión de prácticas correspondiente.