duda ejercicio combinatoria

[ruperz]

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!

[engel lex]

lectura obligatoria

10 pasos para plantear una duda informática
FAQ : Como hacer preguntas "inteligentes"

no somos adivinos...

lenguaje, como está el ejercicio, detalles, que problemas tienes, habla sobre todo eso si quieres ayuda

[tincopasan]

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

[ruperz]

lectura obligatoria

10 pasos para plantear una duda informática
FAQ : Como hacer preguntas "inteligentes"

no somos adivinos...

lenguaje, como está el ejercicio, detalles, que problemas tienes, habla sobre todo eso si quieres ayuda

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

[tincopasan]

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.

[tincopasan]

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

Código (python) [Seleccionar] Expandir

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))


[explorer]

Perdón, pero para subir 4 escalones a mi me salen 8 combinaciones:

Código [Seleccionar] Expandir

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:

Código (bash) [Seleccionar] Expandir

$ 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:

Código (perl) [Seleccionar] Expandir

#!/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:

Código [Seleccionar] Expandir

$ 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

[explorer]

Ya se me ha quejado alguno diciendo que mi solución es muy complicada 

Aquí pongo la solución usando recursión.

Código (perl) [Seleccionar] Expandir

#!/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:

Código [Seleccionar] Expandir

$ ./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...

[tincopasan]

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.

[explorer]

¡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 

Entonces, mis soluciones no sirven.

Pero... con dos pequeños cambios, ya vuelve a funcionar   

Código (perl) [Seleccionar] Expandir

#!/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
}