 Mie Jun 01, 2005 6:57 pm
|
 |
QUEDIFICILPERL
Perlero Nuevo
|
Registrado: 17 Nov 2004
Mensajes: 22
Ubicación: México
|
|
| Ayuda con programa números primos |
 |
|
He estado intentando sacar un programa que calcule números primos y me preguntaba si alguien del foro lo ha hecho ya (pero con programación simple o básica  )
Lo seguiré intentando y cuando lo saque lo publicaré |
|
|
|
|
Jue Jun 02, 2005 6:48 am
|
|
kidd
Creador de Perl en Español
|
Registrado: 15 Oct 2003
Mensajes: 1389
Ubicación: México
|
|
|
|
|
Jue Jun 02, 2005 2:59 pm
|
|
QUEDIFICILPERL
Perlero Nuevo
|
Registrado: 17 Nov 2004
Mensajes: 22
Ubicación: México
|
|
| Gracias Kidd |
|
|
gracias Kidd ya lo cheque pero creo que necesito estudiar un poco más, saludos
|
|
|
Jue Jun 02, 2005 8:54 pm
|
|
QUEDIFICILPERL
Perlero Nuevo
|
Registrado: 17 Nov 2004
Mensajes: 22
Ubicación: México
|
|
| PROGRAMA QUE CALCULA LOS NUMEROS NO PRIMOS |
|
|
Hola. No me podía ir a dormir si no intentaba por última vez hallar mi propia forma de resolver el problema de los números primos con lo único que se (forma diferente a la que me sugirió kidd), pero en mi búsqueda hallé algo curioso:
Hice un programa que me calcula los números no primos del 1 al 200 del cual el código es el siguiente:
| Código: |
for ($n=2;$n<=200;$n++)
{
for($m=2;$m<$n;$m++)
{
$primo= $n % $m;
if ($primo==0)
{
print "del 2 al 2000 no es primo el $n\n";
last;
}
}
}
|
Pregunta ¿de alguna forma y a partir de este programa puedo hallar los números primos? |
|
|
Jue Jun 02, 2005 9:29 pm
|
|
kidd
Creador de Perl en Español
|
Registrado: 15 Oct 2003
Mensajes: 1389
Ubicación: México
|
|
|
|
|
Vie Jun 03, 2005 11:04 pm
|
|
QUEDIFICILPERL
Perlero Nuevo
|
Registrado: 17 Nov 2004
Mensajes: 22
Ubicación: México
|
|
| Que tal |
|
|
Que tal kidd, ya leí el artículo sobre números primos que me sugeriste, gracias, está buenísimo.
Cuando tengas tiempo me gustaría que me sugirieras algún ejercicio o problemilla que me ayude a mejorar mis conceptos de Perl, no se, de esos ejercicios que te enseñen algo, gracias |
|
|
Sab Jun 04, 2005 9:07 am
|
|
kidd
Creador de Perl en Español
|
Registrado: 15 Oct 2003
Mensajes: 1389
Ubicación: México
|
|
|
|
|
Mie Jun 08, 2005 3:38 am
|
|
macgregor
Perlero Frecuente
|
Registrado: 09 Dic 2004
Mensajes: 117
Ubicación: españa
|
|
| Sucession de Fibonacci |
|
|
Hola a todos.
Respecto a la sucesion de fibonacci.
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229.....
Para calcular la sucesión hay varias posibilidades. La más instructiva desde el punto de vista de la programación creo que es mediante la recursividad.
(Siempre en todo problema la solución más eficiente es aquella que tiene coste constante, solución que expongo más abajo).
El número de fibonacci se calcula como
| Cita: | f(1)=1 caso base
f(2)=1 caso base
f(n)=f(n-1)+f(n-2) caso recursivo |
La verdad es que hace mucho tiempo que no me veo en la necesidad de utilizar la recursividad y para ser sinceros este va a ser mi primera función recursiva en perl  espero que este bien 8D
| Código: |
sub fibo
{
my $n=@_[0];
if ($n==0){return 1;}
else
{
if ($n==1){return 1;}
else
{
return( fibo($n-1)+fibo($n-2) );
{
}
} |
Ahora bastaria (por ejemplo) con crear un bucle que guarde los resultados de cada número en un vector y los muestre por pantalla.
Mediante la recursividad si se pretenden calcular los 100 primeros números y mostrarlos por pantalla veremos que el ordenador tarda un poco en mostrar el resultado.
Si se pretenden mostrar los 101 primeros de la sucesión al trabajar con números cada vez más grandes el tiempo se incrementa de forma exponencial 
También existe la solución a esta sucesión con coste de ejecución constante, por lo tanto más eficiente.
Consiste en crear un vector con tantas posiciones como números queramos calcular (en Perl con crearlo basta XD )
En las dos primeras posiciones ponemos los dos casos base (dos unos).
Y el resto los calculamos modificando la función del caso recursivo.
(¡¡¡cada valor es igual a la suma de sus dos anteriores!!!)
| Código: |
$num= cantidad de números que se quieren calcular de la serie;
@fibo=('1','1');
for (my $i=2;$i=$num;$i++)
{
$fibo[$i]=$fibo[$i-1]+$fibo[$i-2];
}
$"=',';
print @fibo; |
De hecho con esta función se pueden calcular muchísimos números de la sucesión de fibonacci, mientras que con la versión recursiva además de tardar más es muy probable que suceda un error de desbordamiento interno de pila
Espero que esto sirva para activar las neuronas y le sea útil a alguien.
(KIDD creo que si pones esto un poco mejor explicado y algún ejemplo más como el cálculo del factorial en un tutorial sobre recursividad recibiría muchas visitas).
Un saludo
MAC. |
|
|
Mie Jun 08, 2005 3:55 am
|
|
macgregor
Perlero Frecuente
|
Registrado: 09 Dic 2004
Mensajes: 117
Ubicación: españa
|
|
| Recursividad |
|
|
En el mensaje anterior parece que dejé en mal lugar a la recursividad y no es esa mi intención.
Suele ser una solución muy intuitiva y sencilla de programar.
En el caso de los números de fibonacci al tratar con números muy grandes se llega a tener problemas de memoria, pero normalmente no sucede esto.
Además aunque con recursividad se realizan muchas veces los mismos cálculos, hay que tener en cuenta que los aciertos de la caché serán altísimos, mientras que sin recursividad hay menos aciertos 
En el caso de fibonacci por el tipo de datos la solución más rápida y efectiva es la segunda, pero muchas veces la solución recursiva es la más potente y sencilla.
PD: hace unos años un profesor de programación de la universidad nos puso como problema calcular de forma recursiva el número de fibonacci que desbordaba las maquinas SUN del laboratorio.
Todos dimos el mismo resultado y nos suspendió a todos
Nos dijo: Ese es el último número que la máquina es capaz de calcular, no el que hace desbordar la pila.....  |
|
|
Mie Jun 08, 2005 7:39 am
|
|
kidd
Creador de Perl en Español
|
Registrado: 15 Oct 2003
Mensajes: 1389
Ubicación: México
|
|
|
|
|
Hola:
Desde cuando puse el planteamiento del problema estuve probando y llegué a una posible solución. Aquí se las pongo a ver que les parece:
| Código: |
#!/usr/bin/perl -w
use strict;
#Números iniciales
my ($a,$b) = (1,1);
#Switch para que siga el bucle while
my $loop = "true";
#Vamos a calcular los números hasta:
my $ln = 100000000;
while($loop eq "true"){
print "$a\n"; #imprimimos el número
($a, $b) = ($b, $a+$b); #asignamos nuevos valores
$loop = "false" if $a > $ln; #checamos si llegamos al límite
} |
La opción no usa recursividad como la de MacGregor, pero es bastante eficiente.
Si tienen otras soluciones pónganlas; es interesante ver como cada uno de nosotros llega a la solución de problemas 
SALUDOS |
|
|
Mie Jun 08, 2005 11:27 am
|
|
Perl user
Maestro Honorario
|
Registrado: 03 Nov 2004
Mensajes: 385
|
|
|
|
|
Después de unas largas vacaciones, me pareció interesante que comenzaran con cuestiones matemáticas (de implementación), así que tomaré el post de macgregor que fué al que le encontré algunas pequeñas fallas de implementación, para en general explicar la cuestión recursiva y su funcionamiento.
Efectivamente, la posibilidad más instructiva para el problema de la sucesión de fibonacci es utilizando la ayuda de las matemáticas y su implementación computacional, es decir, generar la función recurrente del problema como se menciona abajo:
| macgregor escribió: |
el numero de fibonacci se calcula como
| Cita: | f(1)=1 caso base
f(2)=1 caso base
f(n)=f(n-1)+f(n-2) caso recursivo
|
|
Aqui hay 2 cosas importantes... la función recurrente está correcta, pero... le hace falta su condición de comienzo y los casos bases dados, estan "correctos" si así se quiere ver... pero... falta uno muy importante: f(0). Entonces nuestra recurrencia quedaría planteada de la siguiente manera:
| Código: |
f(0) = 0;
f(1) = 1;
f(n) = f(n-1) + f(n-2) cuando n >= 2 |
Consta de 2 casos base (los cuales computacionalmente detendrán las llamadas recursivas) y luego viene el caso recursivo o matemáticamente llamado también caso hipotético (es simple inducción matemática), donde se asume que la sucesión se calcula a partir de los 2 valores anteriores dados a la función.
Esto nos permite ver que computacionalmente, generaremos una función, cuyos valores de parada serán, al recibir un número con valor 0 ó 1, y que mientras no se cumpla dicha condición, se llame asímisma con los valores anteriores.
Veamos la implementación dada:
| macgregor escribió: |
| Código: |
sub fibo
{
my $n=@_[0];
if ($n==0){return 1;}
else
{
if ($n==1){return 1;}
else
{
return( fibo($n-1)+fibo($n-2) );
{
}
} |
|
Bueno, si se prueba dicho código utilizando use warnings se podrá observar que el intérprete nos advertirá sobre una pequeña falla de asociación de valores: intentaste utilizar un slice en vez de un simple valor escalar sobre los parámetros enviados.
Funciona.... claro... por qué? porque dicho slice a fin de cuentas regresa un valor... pero ¿sabes que retorna? retorna una lista, una lista con un solo valor (que escalarmente es un 1, así que cuidado).
La otra cuestión es... no hay necesidad de separar los 2 casos base, y generar 4 condiciones, con 1 sola condición es suficiente, por lo tanto el código quedaría de la siguiente manera:
| Código: |
sub fib {
my $n = shift; # o $_[0]
return $n if ( $n == 0 or $n == 1 ); #casos base
return fib( $n-1 ) + fib( $n-2 ); #caso recursivo
} |
El orden de dicho algoritmo es O(n^n), por lo tanto como se mencionó en el post de macgregor, crece exponencialmente de acuerdo al parámetro mandado. Dependiendo de la pila máxima soportada, es el nivel de recursividad que el algoritmo podrá soportar.
Recomendaciones:
No es comercial pero... es 100 no.... 10000% recomendado el nuevo libro Higher Order Perl del autor Mark Jason Dominus, editorial Morgan Kauffman (or something like that), el cual tiene como finalidad aplicar conocimientos del paradigma funcional en el lenguaje de programación Perl. Así que esto de la recursividad es un tópico en el libro, y una técnica muy buena para "salvar" recursos llamada Memoization.
Saludos, |
|
|
Mie Jun 08, 2005 1:40 pm
|
|
kidd
Creador de Perl en Español
|
Registrado: 15 Oct 2003
Mensajes: 1389
Ubicación: México
|
|
|
|
|
| Perl user escribió: | Recomendaciones:
No es comercial pero... es 100 no.... 10000% recomendado el nuevo libro Higher Order Perl del autor Mark Jason Dominus, editorial Morgan Kauffman ( or something like that ), el cual tiene como finalidad aplicar conocimientos del paradigma funcional en el lenguaje de programación Perl. Así que esto de la recursividad es un tópico en el libro, y una técnica muy buena para "salvar" recursos llamada Memoization. |
El libro es:
Higher-Order Perl de Mark Jason Dominus
Click para comprar (ahora si es un comercial de "Perl en Español", jeje )
SALUDOS |
|
|
Mie Jun 08, 2005 10:40 pm
|
|
QUEDIFICILPERL
Perlero Nuevo
|
Registrado: 17 Nov 2004
Mensajes: 22
Ubicación: México
|
|
| Mi respuesta al programa sucesión de fibonacci |
|
|
Que tal amigos. Me disponía a dormir y me dije voy a ver que hay de nuevo en el foro y me encuentro con la propuesta de Kidd sobre la sucesión de fibonacci, se me hizo interesante y decidí posponer unos minutos el sueño, así que antes de leer sus propuestas para el programilla de la sucesión decidi hacerlo sólo y con lo poco que sé, el código que se me ocurrio es:
| Código: |
@fibonacci=(1,1);
print "$fibonacci[0]\n";
print "$fibonacci[1]\n";
for ($z=2;$z<=10;$z++)
{
$fibonacci[$z]=$fibonacci[$z-1]+$fibonacci[$Z-2];
print "$fibonacci[$z]\n";
} |
No alcancé a analizar las otras respuestas (ya saben ahi que levantarse temprano) pero al parecer mi respuesta es similar a la de MCGregor y por lo que veo Perl User la critica extensamente, y lo que hace Kidd se ve muy interesante así que manaña en la noche la checare con detalle; ¿saben que me da gusto? que empiezo a deletrear Perl.......  |
|
|
Jue Jun 09, 2005 5:37 am
|
|
macgregor
Perlero Frecuente
|
Registrado: 09 Dic 2004
Mensajes: 117
Ubicación: españa
|
|
|
|
|
| Cita: | my $Código:
| Código: |
sub fibo
{
my $n=@_[0];
if ($n==0){return 1;}
else
{
if ($n==1){return 1;}
else
{
return( fibo($n-1)+fibo($n-2) );
{
}
} |
Comentario de PerlUser:
Bueno, si se prueba dicho código utilizando use warnings se podrá observar que el intérprete nos advertirá sobre una pequeña falla de asociación de valores: intentaste utilizar un slice en vez de un simple valor escalar sobre los parámetros enviados.
Funciona.... claro... por qué? porque dicho slice a fin de cuentas regresa un valor... pero sabes que retorna? retorna una lista, una lista con un solo valor ( que escalarmente es un 1, asi que cuidado ).
La otra cuestión es... no hay necesidad de separar los 2 casos base, y generar 4 condiciones, con 1 sola condición es suficiente, por lo tanto el código quedaría de la siguiente manera:
(PerlUser) Código:
| Código: |
sub fib {
my $n = shift; # o $_[0]
return $n if ( $n == 0 or $n == 1 ); #casos base
return fib( $n-1 ) + fib( $n-2 ); #caso recursivo
} |
|
En cuanto a la mejora del codigo simplificando los casos base me parece muy buena.
Pero creo que que es incorrecto decir que f(0)=0 ya que el primer numero de la sucesion es un 1. quiero decir que si preguntas al programa el valor del primer numero de fibonacci debe responder un 1 y no un 0.
creo que cuando escribi :
| Cita: | el numero de fibonacci se calcula como
f(1)=1 caso base
f(2)=1 caso base
f(n)=f(n-1)+f(n-2) caso recursivo |
deberia haber puesto:
| Código: |
el numero de fibonacci se calcula como
f(0)=1 caso base
f(1)=1 caso base
f(n)=f(n-1)+f(n-2) caso recursivo |
Pero la verdadera intencion al escribir este mensaje es decir que no entiendo la parte en la que PerlUser habla del slice (que es un slice? ) y me gustaria que explicaras con mas detalle que significa que retorne un valor que escalarmente es un 1 ???
Creo que no hay nada peor que quedarse con dudas sobre algo, ya que saber a medias se parece mas a no saber nada que a conocer algo.
PD: QUEDIFICILPERL, MACGREGOR se escribe con A.
Sin ella es anglosajon  en lugar de hispano. 
Verdad que a nadie se le ocurriria escribir Mcario?
MACARIO es un nombre hispano, ni escoces (MAC) ni aleman(ARIO), pues lo mismo le pasa a mi alias !!!
PD2: PerlUser me alegra volver a verte por aqui, espero ansioso tu respuesta. Gracias de antemano. |
|
|
Jue Jun 09, 2005 10:15 am
|
|
Perl user
Maestro Honorario
|
Registrado: 03 Nov 2004
Mensajes: 385
|
|
|
|
|
| macgregor escribió: |
En cuanto a la mejora del codigo simplificando los casos base me parece muy buena.
Pero creo que que es incorrecto decir que f(0)=0 ya que el primer numero de la sucesion es un 1. quiero decir que si preguntas al programa el valor del primer numero de fibonacci debe responder un 1 y no un 0.
creo que cuando escribi :
| Cita: | el numero de fibonacci se calcula como
f(1)=1 caso base
f(2)=1 caso base
f(n)=f(n-1)+f(n-2) caso recursivo |
deberia haber puesto:
| Código: |
el numero de fibonacci se calcula como
f(0)=1 caso base
f(1)=1 caso base
f(n)=f(n-1)+f(n-2) caso recursivo |
|
Nope, f(0) no puede ser 1, el algoritmo explícitamente dice que cuando el parámetro de la función sea un 0, el valor retornado es 0, puesto que no hay sucesión de fibonacci para dicho número. Y nuevamente te faltó la condición de recursividad de que para todo n >= 2 se ejecutará.
| macgregor escribió: |
Pero la verdadera intencion al escribir este mensaje es decir que no entiendo la parte en la que PerlUser habla del slice (que es un slice? ) y me gustaria que explicaras con mas detalle que significa que retorne un valor que escalarmente es un 1 ???
Creo que no hay nada peor que quedarse con dudas sobre algo, ya que saber a medias se parece mas a no saber nada que a conocer algo.
|
Ok, normalmente el acceso a una lista puede darse desde 2 ámbitos:
1) Un valor único ( escalar )
2) Una lista
El último caso, no solamente es explícitamente la lista en sí, sino que puedes obtener una sublista, ejemplo:
| Código: |
my @list = qw( "foo", "bar", "baz" ); # la lista
my $value = $list[2] # "baz"
my $value = $list[-1] # "baz"
my @sublist = @list[1,2]; # ( "bar", "baz" );
my @sublist = @list[1,-1]; #( "foo", "baz" );
|
Los 2 últimos casos son slices ( particiones ), es decir un subconjunto de tu lista, el cual puede ser un número explícito de elementos o un rango.
por lo tanto en el ejemplo @a[1]; lo que te regresa no es el elemento 1 de la lista, te regresa una lista con dicho elemento... es decir:
| Código: |
my @a = ( "foo", "bar", "baz" );
my $val = $a[1]; # "bar"
my @val = @a[1]; # ( "bar" );
my $val = @a[1]; # 1, lo cual es incorrecto
|
La última expresion por ser una lista evaluada en contexto escalar, regresa la cantidad de elementos en la lista. Pero como el interprete de Perl es muy inteligente y ese es un error común en los programadores iniciales, te lo evaluará como $a[1] ( o sea como debería ser correctamente ) PERO te dará la advertencia de que eso está mal escrito de tu parte y que debes corregirlo.
| macgregor escribió: |
PD2: PerlUser me alegra volver a verte por aqui, espero ansioso tu respuesta. Gracias de antemano. |
Gracias, estuve ocupado mucho tiempo escribiendo un compilador y un lenguaje para un proyecto, el cual ya está terminado.
Saludos, |
|
Powered by phpBB © 2001, 2005 phpBB Group
|
aquí va unos links para que aprendan un poco de matemáticas