[ Foro de Pascal ]

secuencias ordenadas

Hola a todos!! estoy intentando sacar un problema que me mandaron en la facultad y bueno, lo piden con tipos simples y llevo dias intentando sacar una solucion y por mas vueltas que le doy no soy capaz de resolverlo con tipos simples: Posteo el enunciado:

Supongamos que tenemos una caja que contiene infinitas fichas, cada ficha tiene escrita un número del 1 al 9. Queremos evaluar el número de veces que podemos ordenar las fichas de las que disponemos para que los números que muestren sumen una cierta cantidad.
Por ejemplo, si queremos obtener 4 como valor de la suma, tenemos 8 maneras
diferentes de disponer las fichas.
1 1 1 1
1 1 2
1 2 1
1 3
2 1 1
2 2
3 1
4
En la solución mostrada hemos seguido una ordenación similar al diccionario, donde
todas las palabras que empiezan por la ‘a’ aparecen antes que las que empiezan por la ‘b’. y aquellas empezando por ‘aa’ comienza antes que aquellas empezando por ‘ab’.
Hemos mostrado primero todas las que empiezan por 1 antes de aquellas que empiezan por 2 y lo mismo con las que empiezan por 1 1 antes que las que empiezan por 1 2.
Práctica:
Escribe un programa, que podrá tener los subprogramas que estimes convenientes, para determinar la n-ésima forma de ordenar las fichas para hacer una suma fija. Tú
programa debería recibir un entero s (1 0 s 0 32) y otro n (1 0 n < 231) y mostrar la nésima forma de ordenar las fichas, en orden de diccionario, para hacer la suma s.
Supondremos que el programa no recibirá un valor de n mayor que el número de formas de ordenar los bloques.
Ejemplo:
Veamos un ejemplo en el que se nos muestra la quinta forma de sumar el número
cuatro.
s -->4
n -->5
2 1 1


alguien me puede ayudar?? habia pensado hacerlo con reales pero da un error de llenado de pila...

no se que mas vueltas darle...


muchas gracias!!!

Hola. Vi el otro día el post pero no tuve tiempo ni de plantearme la cuestión.

No sé si estaré un poco despistado, pero no entiendo eso de "s (1 0 s 0 32) y otro n (1 0 n < 231)". ¿Qué significa?

Otra pregunta también: ¿Con qué nivel de conocimientos contamos en el asunto?

Hasta luego.

hola!!

te explico, lo que quiero decir es s (1<=s<=32) y n (1<=n<231), vamos que s este entre 1
y 32 y los posibles valores de n sean entre 1 y 231. Lo consegui sacar haciendolo con
reales (a lo basto) y la verdad que para ciertos valores de numeros grandes no funcionaba
bien... para mi el problema esta en que hay que hacerlo con tipos simples, no puedes usar
por ejemplo strings, y estoy muuuuy muuuy saturado, no se me ocurre nada y lo unico que
me dijeron que podria hacerlo con recursividad por ejemplo, pero ya te digo no se me
ocurre nada. El caso que seguramente sea bastante sencillo y una vez que lo vea diré: la
solucion es trivial, pero ahora estoy q no se como hacerlo.

Muchas gracias por tu interes!! si se te ocurre alguna idea indicamelo por favor.

Un saludo,

Es una función recursiva. Piensa si existe un caso base, y cómo pasar de él al siguiente caso en complejidad (se suele diseñar al revés, pero creo que me entiendes ;-) ):


El caso más sencillo es el 1, que sólo tiene una descomposición:
1


El siguiente en complejidad es el 2, que se puede expresar como 2 o como un el siguiente (1) seguido de la descomposición de n-1 (1):
2
1 (1)

(marco entre paréntesis lo que depende de "números más sencillos)


El siguiente es el 3, también se puede expresar como 3 o como el siguiente (2) y la descomposición del resto (1), o s siguiente (1) seguido de la descomposicón del resto (2), así:
3
2 (1)
1 [2]
1 [1 1]


Sólo falta que plantees eso como función recursiva...  ;-)

gracias por contestar!!

pero como controlar la n-esima forma?? ya que tienes que sacar por pantalla solo la n por ejemplo la 3 forma y solo esa, y de esta manera los resultados no coincidirian no??

saludos,

No has puesto el fragmento de código que genera todas. Lo primero es entender eso. ;-)

Para mostrar sólo una secuencia, se me ocurren al menos dos formas:

- La más sencilla, pero también la más lenta, es generar todas las combinaciones en orden (creciente, en el ejemplo que te proponen), contando "cuantas llevas", y "cortar" cuando alcanzas la buscada.

- Una solución más rápida, pero más compleja de programar, sería tentativa: si sabes que para n=4 tienes 4 secuencias que empiezan por 1, 2 que empiezan por 2, etc., la secuencia 5 estaría después de las 4 primeras del 1, y sería la 1ª del número 2.