Muy buenas,
necesito ayuda con un ejercicio en Python por el que no se ni por donde empezar. es sobre unas escaleras, puedo subir de 1, 2 o 3 escalones de vez, y al programa le entra n, que sera el numero de escalones, de tal manera que:
si n=1 -> 1
devuelve 1 (1 forma distinta de subir 1 escalon)
si n=2 -> 1, 1; 2
devuelve 2 (2 formas distintas de subir 2 escalones)
si n=3 -> 1, 1, 1; 2, 1; 1, 2; 3
devuelve 4 (4 formas distintas de subir 3 escalones)
....
Me tiene que devolver el nº de posibilidades del n que le meto, como puedo hacerlo? llevo dandole vueltas al tema y no se me ocurre nada de nada
muchas gracias!
lectura obligatoria
10 pasos para plantear una duda informática (http://foro.elhacker.net/index.php/topic,159345.msg751417.html#msg751417)
FAQ : Como hacer preguntas "inteligentes" (http://foro.elhacker.net/index.php/topic,7122.0.html)
no somos adivinos...
lenguaje, como está el ejercicio, detalles, que problemas tienes, habla sobre todo eso si quieres ayuda
1)¿números de posibilidades de qué? por ejemplo: de combnaciones de 2 números, posibilidades 2 , que alguien adivine tu planteo posibilidades 0
2)¿cómo puedes hacerlo? relativamente fácil, con un planteo correcto
3)posibilidades de lenguajes de programación para resolverlo, me mataste! ni idea cuantos querés usar.
4)por lo tanto posibilidades de adivinos en el foro = 0
Cita de: engel lex en 16 Abril 2015, 15:23 PM
lectura obligatoria
10 pasos para plantear una duda informática (http://foro.elhacker.net/index.php/topic,159345.msg751417.html#msg751417)
FAQ : Como hacer preguntas "inteligentes" (http://foro.elhacker.net/index.php/topic,7122.0.html)
no somos adivinos...
lenguaje, como está el ejercicio, detalles, que problemas tienes, habla sobre todo eso si quieres ayuda
Cita de: ruperz en 16 Abril 2015, 15:59 PM
Perdon, ya esta modificado, lo he copiado y pegado y se a puesto mal
un saludo
Perdon, ya esta modificado, lo he copiado y pegado y se ha puesto mal
un saludo
soy muy perro para las mátematicas, sobre todo en combinatorias y probabilidades, pero lo plantearía así:
para 1 2 y 3 escalones ya lo tenés pero si fuesen más?
la máxima posibilidad de combinaciones son 4 porque lo máximo que subis son 3 escalones
que se obtiene de 3! - 2!
entonces m!/4 debería dar
o sea 5 escalones sería 5.4.3.2.1 / 4 = 30 para 5 escalones 30 posibilidades
para 4 escalones sería 4.3.2.1 / 4 = 6
seguramente le erré de acá la luna, pero creo te puede orientar.
Edito: recién me doy cuenta que hay que tener cuidado en cuanto a combinaciones que incluyan permutaciones, me explico una posibilidad de subir seria 1 + 1+ 2 y otra sería 2+ 1+ 1 y en este caso la combinación es la misma, pero la permutación no.
la verdad que me fui a trabajar y cuando volví me puse a mirar este problema y llegué a dos conclusiones:
1) lo que puse antes no sirve para nada!
2) la única forma que se me ocurre para resolverlo es por recursividad, igual que fibonacci, salvo que son tres valores.
paso a explicar a1=1 a2=2 a3=4 ¿an+1?
an+1= an1+an-1+an-2
el valor siguiente seria
4 escalones = 4(an1) + 2(an-1) + 1(an-2) = 7 para 4 escalones 7 combinaciones
5 escalones = 7(an1) + 4(an-1) + 2(an-2) = 13 para 5 escalones
6 escalones = 13(an1) + 7(an-1) + 4(an-2) = 24 para 6 escalones
y así sucesivamente hasta el escalón buscado.
ahora depende de vos en que lenguaje lo programes.
Cualquier cosa veo si más tarde lo hago en python porque ahora hay tormenta eléctrica y apago todo.
Perdón por la respuesta anterior que la vi muy superficial y como dije la matemática no es mi fuerte.(bah nada es mi fuerte)
Edito:
código en python
def escalon_posible(n):
if n == 1:
return 1
if n == 2:
return 2
if n == 3:
return 4
else:
return (escalon_posible(n-1) + escalon_posible(n-2)+ escalon_posible(n-3))
print("Ingrese un número mayor que 0")
Escalon_final=int(input("Ingrese el escalón final: "))
print (escalon_posible(Escalon_final))
Perdón, pero para subir 4 escalones a mi me salen 8 combinaciones:
4
3,1
2,2
2,1,1
1,3
1,2,1
1,1,2
1,1,1,1
Muestro aquí mi solución, usando el motor de expresiones regulares de Perl, realizando una búsqueda exhaustiva por todas las combinaciones, al provocar un fallo premeditado que obliga a que el motor haga "backtracking" y busque una nueva solución.
Como no sé mucho de Python, lo dejo en Perl, pero es fácil pasarlo a Python (creo). Primero, la versión que se puede ejecutar desde la línea de comandos:
$ perl -E '$n = shift; $rx = ("(1*?)" x ($n-1)) . "(1+)"; $rx = qr/^$rx$/; $x = "1" x $n; $x =~ m/$rx(?{$visto{ join "," => grep { $_ > 0 } map { $+[$_] - $-[$_] } 1..$n }++ })(*FAIL)/; say join "; " => sort keys %visto' 4
1,1,1,1; 1,1,2; 1,2,1; 1,3; 2,1,1; 2,2; 3,1; 4
Y ahora la versión más normal:
#!/usr/bin/env perl
use feature 'say';
my %visto; # memoria de combinaciones ya vistas (evitar repeticiones)
my $escalones = shift; # leemos los escalones
my $rx = ("(1*?)" x ($escalones-1)) . "(1+)"; # creamos el patrón de búsqueda. Es de la forma (1*?)(1*?)...(1+)
$rx = qr/^$rx$/;
my $x = "1" x $escalones; # esta var. contiene tantos '1' como indiquen los $escalones
$x =~ m/
$rx # buscamos una combinación
(?{
$visto{ # la decodificamos
join "," => grep { $_ > 0 } map { $+[$_] - $-[$_] } 1..$escalones
}++
})
(*FAIL) # provocamos un fallo de 'backtraking'
/x;
say join "; " => sort keys %visto; # resultado, formateado
Ejemplo:
$ descompon.pl 5
1,1,1,1,1; 1,1,1,2; 1,1,2,1; 1,1,3; 1,2,1,1; 1,2,2; 1,3,1; 1,4; 2,1,1,1; 2,1,2; 2,2,1; 2,3; 3,1,1; 3,2; 4,1; 5
Ya se me ha quejado alguno diciendo que mi solución es muy complicada :xD
Aquí pongo la solución usando recursión.
#!/usr/bin/env perl
my $escalones = 0 + shift; # leemos el número de escalones
if ($escalones > 0) { # si es un número positivo
my @combinaciones = descompon($escalones); # sacamos todas las @combinaciones
print "Hay ", scalar(@combinaciones), " combinaciones:\n"; # informamos del número de @combinaciones
print join('; ' => @combinaciones), "\n"; # y las propias combinaciones
}
sub descompon() { # devuelve una lista de combinaciones
my $escalones = shift; # para un determinado número de $escalones
my @combinaciones; # aquí guardaremos las @combinaciones encontradas
for my $salto (1 .. $escalones) { # damos un $salto cada vez mayor
my $resto = $escalones - $salto; # después del $salto, nos queda un $resto de $escalones
if (not $resto) { # si hemos llegado arriba
push @combinaciones, $salto; # guardamos ese $salto como nueva combinación
}
else { # si aún no hemos llegado
for my $combina_resto (descompon($resto)) { # vemos todas las combinaciones que quedan para subir
# y las guardamos
push @combinaciones, join "," => $salto, $combina_resto;
}
}
}
return @combinaciones; # devolvemos las @combinaciones encontradas
}
Ejemplo:
$ ./descompon2.pl 6
Hay 32 combinaciones:
1,1,1,1,1,1; 1,1,1,1,2; 1,1,1,2,1; 1,1,1,3; 1,1,2,1,1; 1,1,2,2; 1,1,3,1; 1,1,4; 1,2,1,1,1; 1,2,1,2; 1,2,2,1; 1,2,3;
1,3,1,1; 1,3,2; 1,4,1; 1,5; 2,1,1,1,1; 2,1,1,2; 2,1,2,1; 2,1,3; 2,2,1,1; 2,2,2; 2,3,1; 2,4; 3,1,1,1; 3,1,2; 3,2,1;
3,3; 4,1,1; 4,2; 5,1; 6
Naturalmente, existen más soluciones... :silbar:
explorer:
no veo las 8 combinaciones para subir 4 escalones! salvo que para vos el 4 sea una opción, pero no es posible porque el planteo es claro, el tipo puede subir hasta un máximo de 3 escalones por vez! el 4 no existe.
¡Ah!, entiendo: hay una limitación en el número de escalones que se pueden subir, de hasta 3.
Claro... muy poca gente podría dar un salto de muchos escalones para subir :laugh:
Entonces, mis soluciones no sirven.
Pero... con dos pequeños cambios, ya vuelve a funcionar ;D
#!/usr/bin/perl
my $escalones = 0 + shift; # leemos el número de escalones
if ($escalones > 0) { # si es un número positivo
my @combinaciones = descompon($escalones); # sacamos todas las @combinaciones
print "Hay ", scalar(@combinaciones), " combinaciones:\n"; # informamos del número de @combinaciones
print join('; ' => @combinaciones), "\n"; # y las propias combinaciones
}
sub descompon { # devuelve una lista de combinaciones
my $escalones = shift; # para un determinado número de $escalones
my @combinaciones; # aquí guardaremos las @combinaciones encontradas
for my $salto ( 1 .. 3 ) { # damos un $salto cada vez mayor
next if $salto > $escalones;
my $resto = $escalones - $salto; # después del $salto, nos queda un $resto de $escalones
if ( not $resto ) { # si hemos llegado arriba
push @combinaciones, $salto; # guardamos ese $salto como nueva combinación
}
else { # si aún no hemos llegado
my @resto_combinaciones = descompon($resto); # vemos todas las combinaciones que quedan para subir
for my $combina_resto ( @resto_combinaciones ) {
# y las guardamos
push @combinaciones, join "," => $salto, $combina_resto;
}
}
}
return @combinaciones; # devolvemos las @combinaciones encontradas
}