jueves, febrero 23, 2006

Torres de Hanoi

Otro día comentare más cuestiones sobre el autor, pero hoy explicaré la leyenda tal y como la describen habitualmente:

Cuando Dios creó el mundo, dispuso 3 torres de diamante. En una de la torres colocó 64 discos de oro con diferentes diámetros. Los discos se encontraban de mayor a menor, situados los de mayor diámetro cerca de la base.

Desde entonces, los monjes de un monasterio cercano mueven los discos uno a uno, con el propósito de que los 64 discos terminen en la tercera torre.

Las reglas para mover los discos son las siguientes:
  1. No se puede mover más de un disco cada vez.
  2. No se puede colocar un disco mayor sobre otro menor.

El siguiente programa es un simulador del juego:







program hanoi;
uses crt;
const
maxDiscos = 64;
type
Tdiscos = array[1..maxDiscos] of integer;
Ttorre = record
numDiscos : integer;
discos : Tdiscos;
end;
var
torre1, torre2, torre3 : Ttorre;
num : integer;
altura: integer;
fin: boolean;
rta: string[2];
i: integer;
numMovimientos: integer = 0;

procedure dibujarEscenario(altura: integer; torre1, torre2, torre3: Ttorre);
var i, j, z: integer;
begin
clrscr;

{Empezamos dibujando las 3 torres sin ning£n disco}
for z:=1 to 3 do
begin
for i:=6 to 13 do
begin
gotoxy(2+z*20, i);
writeln('±');
end;
end;

{Dibujamos los discos de las 3 torres}

{Torre1}
for z:=1 to torre1.numDiscos do
for i:=-torre1.discos[z] to torre1.discos[z] do
begin
gotoxy(22+i,10-z);
writeln('=');
end;

{Torre2}
for z:=1 to torre2.numDiscos do
for i:=-torre2.discos[z] to torre2.discos[z] do
begin
gotoxy(42+i,10-z);
writeln('=');
end;

{Torre3}
for z:=1 to torre3.numDiscos do
for i:=-torre3.discos[z] to torre3.discos[z] do
begin
gotoxy(62+i,10-z);
writeln('=');
end;
end;

procedure moverDisco(var torreOrigen: Ttorre; var torreDestino: Ttorre);
begin
if torreOrigen.numDiscos <> 0 then
if (torreDestino.discos[torreDestino.numDiscos]>
torreOrigen.discos[torreOrigen.numDiscos])
or (torreDestino.numDiscos = 0) then
begin
torreDestino.numDiscos:=torreDestino.numDiscos+1;
torreDestino.discos[torreDestino.numDiscos]:=
torreOrigen.discos[torreOrigen.numDiscos];
torreOrigen.numDiscos:=torreOrigen.numDiscos-1
end
else
begin
gotoxy(1,24);
textcolor(RED);
writeln('MOVIMIENTO NO PERMITIDO');
readln();
textcolor(BLUE);
end
else
begin
gotoxy(1,24);
textcolor(RED);
writeln('LA TORRE SELECCIONADA NO TIENE DISCOS');
readln();
textcolor(BLUE);
end
end;

begin

textcolor(BLUE);
textbackground(YELLOW);
clrscr;

writeln('Torres de Hanoi');
repeat
write('N£mero de discos (entre 1 y 9): ');
readln(num);
until (num>0) and (num<10);
altura:= num;
torre1.numDiscos := num;
for i:=1 to num do
torre1.discos[i]:=num+1-i;
torre2.numDiscos := 0;
torre3.numDiscos := 0;
fin:=false;
repeat
dibujarEscenario(altura, torre1, torre2, torre3);

if torre3.numDiscos = num then
begin
gotoxy(1,24);
textcolor(RED);
writeln('­HAS GANADO! N£mero de movimientos realizados: ',
numMovimientos);
writeln('N£mero m¡nimo de movimientos posible: ',
2*num-1);
readln();
fin:=true;
end
else
begin
gotoxy(1,15);
writeln('Selecciona un movimiento:');
writeln('12-De la torre 1 a la torre 2');
writeln('13-De la torre 1 a la torre 3');
writeln('21-De la torre 2 a la torre 1');
writeln('23-De la torre 2 a la torre 3');
writeln('31-De la torre 3 a la torre 1');
writeln('32-De la torre 3 a la torre 2');
writeln('0-Salir');
readln(rta);
if rta = '12' then moverDisco(torre1, torre2);
if rta = '13' then moverDisco(torre1, torre3);
if rta = '21' then moverDisco(torre2, torre1);
if rta = '23' then moverDisco(torre2, torre3);
if rta = '31' then moverDisco(torre3, torre1);
if rta = '32' then moverDisco(torre3, torre2);
if rta = '0' then fin:=true;
numMovimientos:=numMovimientos+1;
end;
until fin;
end.

lunes, febrero 13, 2006

Fibonacci y la razón aurea

La serie que hemos calculado, denominada serie de Fibonacci, cumple algunas propiedades
curiosas. La más llamativa de todas es la conexión con la razón aurea.

Esta razón se menciona en el libro VI de Los Elementos de Euclides. La podemos intuir cuando
intentamos dividir un segmento en 2 partes que guarden cierto equilibrio, pero sin que el corte
sea por el medio del segmento.


_______________I_________________________


¿Qué tiene de especial este corte? ¿Cual es la proporción que esconde? ¿Qué tiene que ver
con la serie de Fibonacci?

Símplemente el trozo largo respecto al trozo corto guarda la misma proporción que el segmento
entero respecto al trozo largo.


<------ 1 ----------> <---------- X -------------------->
_______________I_________________________

<-------------------- X+1 ------------------------------>


Algebraicamente:

(X+1) / X = X / 1
Por lo tanto:
(X+1) = X^2

X^2 - X -1 = 0
(X cuadrado - X -1 igual a 0)

Resolviendo esta ecuación de segundo grado obtenemos:

X = (1+SQRT(5))/2
(X es igual a (1 + raiz de 5) entre 2)

O sea que X = 1,6180339887498948482045868343656...

Hagamos el programa que además de la serie de Fibonacci, nos muestre la razón entre 2
elementos consecutivos de la serie:


program Fibonacci;
uses crt;
var numActual, numAnterior, numComodin, limite:longint;
begin
clrscr;
writeln('Serie de Fibonacci');
write('Introduce el l¡mite: ');
readln(limite);
writeln;
writeln;
numActual:=1;
numAnterior:=0;
repeat
write(numActual);
write(' -> ');
if numAnterior <> 0 then
writeln(numActual/numAnterior)
else writeln('X');
numComodin:=numActual;
numActual:=numAnterior+numActual;
numAnterior:=numComodin;
until numAnterior > limite;
readln
end.
 
Sorprendente, ¿verdad?

miércoles, febrero 08, 2006

Lenguajes recursivos

Los lenguajes recursivos son aquellos en los que sus funciones y/o procedimientos pueden llamarse a sí mismos.

Las técnicas que posibilitan soluciones recursivas son muy diferentes a las iterativas o repetitivas.

La recursividad dota de mayor potencia al lenguaje, ya que aunque todas las soluciones recursivas se pueden implementar de forma no recursiva, la recursividad ofrece las siguientes ventajas:
  • Las soluciones recursivas son más fáciles de plantear (hablamos de problemas medianamente complejos como los que plantearé en los próximos días).
  • En problemas no triviales, la solución tiene menos líneas de código.

Como ejemplo, este programa sirve para calcular el valor de un elemento de la serie de Fibonacci. Por supuesto, se hace uso de la recursividad:



program fibonacci_recursivo;
uses crt;
var numero:longint;
function calculaFibonacci(num:longint):longint;
begin
if (num=1) or (num=2) then calculaFibonacci:=1
else calculaFibonacci:=calculaFibonacci(num-1) + calculaFibonacci(num-2);
end;

begin
clrscr;
writeln('Fibonacci recursivo');
write('Introduce un n£mero: ');
readln(numero);
writeln(calculaFibonacci(numero));
readln;
end.

viernes, febrero 03, 2006

Fibonacci

Fibonacci (Leonardo de Pisa) nació en Pisa y vivió de 1170 a 1250.
Mercader y estudioso de las matemáticas fue uno de los que introdujeron los principios de la aritmética y el cálculo arábigo entre los mercaderes Europeos.

Escribió muchos libros sobre matemáticas, aunque teniendo en cuenta que no existía la imprenta, pocos han llegado hasta nuestros días.

En su libro Liber Abaci, entre múltiples problemas, plantea el de la reproducción de la pareja de conejos, que da lugar a la famosa serie de Fibonacci.

Fuente: http://redescolar.ilce.edu.mx/redescolar/act_permanentes/mate/nombres/mate4j.htm

1) Supongamos que tenemos una pareja de conejos (macho y hembra) de un mes de edad que aún no pueden reproducirse, pero que podrán hacerlo cuando cumplan dos meses de edad.

2) Supongamos también que cada mes, a partir del segundo, nace una nueva pareja de conejos (macho y hembra).

3) Si cada pareja de conejos se reproduce de la misma forma que la pareja inicial, ¿cuántas parejas habrá al principio de cada mes?

Primer mes: 1 pareja (el macho y la hembra).
Segundo mes: 1 pareja (el macho y la hembra).
Tercer mes: La pareja inicial + una nueva pareja. En total 2 parejas.
Cuarto mes: La pareja inicial + la pareja nueva del tercer mes + una nueva pareja. En total 3 parejas.
Quinto mes: Aquí el tema se complica, y ya me veo obligado a remitiros a http://redescolar.ilce.edu.mx/redescolar/act_permanentes/mate/nombres/mate4j.htm
para que lo veáis gráficamente.

El caso es que la serie resultante es 1, 1, 2, 3, 5, 8, 13, 21, …

O sea, que se puede calcular el número de parejas sumando los 2 términos anteriores.

Este tema de la serie me sirve de excusa para el primer programa. Un programita que calcule la serie hasta un límite que introduzca el usuario.

Para este tema, y siempre con la intención de hacerlo lo más fácil posible, he descargado el compilador de Turbo Pascal 5.5 de la web del programador de Pascal (http://www.devq.net/pascal)

El programa que calcula la serie hasta el límite de un tipo longint de TurboPascal es el siguiente:


program Fibonacci;
uses crt;
var numActual, numAnterior, numComodin, limite:longint;
begin
clrscr;
writeln('Serie de Fibonacci');
write('Introduce el límite: ');
readln(limite);
writeln;writeln;
numActual:=1;
numAnterior:=0;
repeat
writeln(numActual);
numComodin:=numActual;
numActual:=numAnterior+numActual;
numAnterior:=numComodin;
until numAnterior > limite;
readln
end.




Por otra parte, hace algún tiempo me descargué el BloodShed Dev-Pascal v1.9.2

que por debajo lleva Free Pascal Compiler 1.06.

Así que he decidido hacer una segunda comprobación.

El resultado es el siguiente:

La compilación no da ningún problema, pero en ejecución las tildes no aparecen correctamente. Me imagino que tendrá solución aunque no merece la pena esforzarse si con el antiguo compilador ha ido bien.

Resulta más curioso el tamaño del ejecutable obtenido:
El ejecutable generado con Turbo Pascal 5.5 es de 5 K-s.
El ejecutable generado con Free Pascal compiler 1.06 (con las opciones por defecto) ocupa 22 K-s.

Y es que el que tuvo retuvo.

jueves, febrero 02, 2006

Inicio

Esta es mi primera anotación en el Blog.
En principio quiero dedicarla a la programación en lenguajes de tercera generación algunos de los cuales se consideran anticuados hoy en día.
Mi opinión personal es que un programa debe resolver problemas y no crearlos. Por ello utilizaré el lenguaje apropiado para cada caso.
No tengo demasiado tiempo libre por lo que si consigo realizar un programita semanal que alguien considere útil estaré más que satisfecho.
Saludos.