Algoritmia (Como repartir tareas)

No se muy bien lo que andarás haciendo pero lo que quieres es algo así (creo)



No lo he probado mucho... pero esa podría ser la idea... a lo mejor no... qué se yo

Saludos.Ferdy

Ferdy escribió:No lo he probado mucho... pero esa podría ser la idea... a lo mejor no... qué se yo smile_:)

Jajaja, disculpa Ferdy, pero es que como dije antes me explico fatal.

No entiendo lo que me quieres decir con ese trozo de codigo, lo siento.

Haber, que vuelvo a intentarlo.

Voy a explicar en que consiste el proyecto de pe a pa, así igual te aclaras y otra gente entiende un poco lo que pido.

Consiste en un programa en C, que tiene que recoger una serie de parametros del usuario, entre ellos número de tareas globales y número de etapas, para posteriormente generar un programa que se ejecute en varias máquinas a la vez (un programa paralelo) mediante MPI, además de un grafo de ejecución. Las tareas dependiendo de los parametros que entre el usuario, se repartirán de una forma o de otra, siendo una opción, ésta que he nombrado, tomar forma de triangulo decreciente, de modo que necesito encontrar el algoritmo para repartir las tareas de forma que quede un triangulo óptimo si es posible, o lo más optimo posible, en el caso que no pueda ser. (Una tarea menos por cada etapa, y que la última tenga 1 o 2 tareas, (preferiblemente 2, sería lo óptimo), pero como saber cuantas etapas tiene la inicial??? Porque si empiezo por la última y pongo 2, en la siguiente 3.. y sucesivamente, a lo mejor en la primera resulta que me quedan las 100 etapas restantes.

Vaya tocho... Lo siento, espero haber aclarado un poco mas la idea de lo que estoy haciendo. Haber si me instalo graphviz, y dibujo un grafo de ejecucion de ejemplo, para que lo podais ver mas claro.

Ferdy, por otro lado, sería posible (si crees que la solucion que has dado antes és valida), que me explicaras el fragmento de codigo? ya que no entiendo muy bien lo que hace...

Saludos y gracias!!!

EDITO: Ya he colgado el grafo para que os hagais una idea, cada línea vertical de nodos representa una etapa, y como podeis ver, hay respectivamente en cada etapa 4,3,2 y 1 nodo (tareas).

Lo siento, lo había entendido todo al revés. Olvida mi mensaje anterior

La verdad es que no se me ocurre muy bien cómo hacerlo... luego lo pienso y si me sale algo vuelvo a postear.

De todas formas, esto tiene pinta de venir en los libros.... parece un problema 'tipo'.

Saludos.Ferdy

Hombre, hacer un algoritmo que busque el incremento es bastante sencillo, basta con hacer un bucle , ir sumando y comparar con el número total de tareas, pero no sé si es lo que quieres.

Un saludo.

C++... hace tiempo que no lo veia... cuantos recuerdos XD

Bueno mi solucion es esta...

while (etapas>0)
{
for (i=0; i {
[ AQUI SE ASIGNA LA TAREA A LA ETAPA "i" ]
tareas--;
}
etapas--;
}

Esa es la idea masomenos... que se asignen las tareas a las etapas de una en una, de manera que en la etapa final se asigne una tarea, luego al repetirse el bucle de while, se asignará una tarea mas a cada etapa de manera que queden 2 en cada una excepto en la ultima etapa que quedaría con 1 tarea, y asi sucecivamente... me doy a entender?

Salu2.

Buenas de nuevo, lo siento pero he estado fuera el fin de semana y no he podido echar un vistazo .

Ferdy, gracias por tu interés de todas formas . Se agradece siempre tu ayuda.

jazomand, gracias tambien. Tu solucion parece valida, pero tampoco alcanza lo que quiero, porque por ejemplo, si entran 10 tareas y 2 etapas, pues la primera tiene 9 y la segunda 1, cuando me parecería mas correcto que fueran 5 i 4 respectivamente. Pero creo que puedo trabajar con tu algoritmo, comparando el número de tareas restantes, y si es mayor que el número de etapas... Bueno no.... tampoco. Nada, que gracias a los dos y intentaré seguir buscando haber.

Saludos y mil gracias!!!

DeaDlocK escribió:si entran 10 tareas y 2 etapas, pues la primera tiene 9 y la segunda 1, cuando me parecería mas correcto que fueran 5 i 4 respectivamente.

¿No querrás decir 5 y 5? ¿O 6 y 4?

Creo que este problema tienes que abordarlo con trigonometria pura y dura. O también puedes tratar el problema de forma distinta cuando la forma de repartir tareas te de numeros pares o impares.

hombre, creo que tu mayor problema es que no sabes como repartir las tareas...

partiendo de la base que un triangulo tal como el que quieres construir tiene el mismo numero de bolos en todos sus lados, es bien sencillo

supongamos que quieres repartir 20 tareas en 5 etapas, coges 5 de esas 20 tareas y llenas la primera etapa:

***** (ya tienes la priemra etapa y te sobran 15 bolos)

ahora con los 15 bolos que te sobran sigues rellenando etapas, pero esta vez con un bolo menos.

*****
**** (segunda etapa, sobran 11 bolos)

y sigues asi...

*****
****
*** (sobran 8 bolos)

*****
****
***
** (sobran 6 bolos)

*****
****
***
**
* (sobran 5 bolos)


ya tienes tu triangulo perfecto, pero sobran 5 bolos...

otra cosa es que tu digas que dado un numero determinado de tareas se forme un triangulo lo mas perfecto posible pero sin determinar las etapas
o bien, que dado un numero de etapas determinadas, tuvieras que decir cuantas tareas serian necesarias...

no se si yo no te he entendido o es que tu no te explicas...

Buenas de nuevo.

J0han escribió:¿No querrás decir 5 y 5? ¿O 6 y 4?

En efecto, son 6 4 lo deseable, por lo que esto indica que tampoco tiene que ser siempre 1 tarea la diferencia de tareas con la etapa anterior.

f5inet esos 5 que sobran podrían ir uno en cada etapa perfectamente, ya que sería el resultado que busco, no tiene porqué acabar la última etapa en 1 tarea. Pero claro, lo que tu propones es un caso concreto, pero no sirve como solucion generica, aunque trataré de buscar algo por ahí, puede dar resultado también.

Ferdy, he estado buscando por ahí, pero no encuentro ningun problema parecido que ya se haya resuelto.

Creo que voy a tener que consultar al profesor de álgebra, haber si se le ocurre algo. jajaja

Saludos y gracias!!

Lo que tienes que hacer es coger lápiz y papel y plantearte bien el problema, porque todavía no tienes claro lo que tienes que hacer y te contradices en las explicaciones. Una vez que hayas hecho un montón de ejemplos con los posibles casos, y sepas cómo se debe comportar, es fácil sacar el algoritmo.

vamos a ver, entonces te contradices.

por un lado dices que te dan un numero de etapas y un numero de tareas, y que tienes que optimizar el reparto...

expuesto asi, el problema es sencillo, y se resuelve como te he dicho.

el problema seria que SOLO TE DIERAN EL NUMERO DE TAREAS TOTALES, y tu tuvieras que calcular cual seria el numero de etapas optimo a lanzar en esa progresion de 'bolos' que has dicho antes.

explicate bien primero, por favor.

Indicadme alguno donde me he contradicho, y os lo explico otra vez. He releído mis posts y veo claro lo que he expuesto.

El número de etapas y el de tareas lo tienes SIEMPRE. Pero en tu caso, como sabes el resultado que va a dar, pues lo puedes asignar coherentemente, pero el programa, como sabe que tiene que partir de 5?

Ahí es donde veo el mayor problema...

Saludos y gracias a todos de nuevo!

Ya tengo la solucion:

sacas la media de tareas que necesitas por cada etapa

ej .: 100 tareas repartidos en 14 etapas
100/14=7,14
7*14=98

nos da que a cada etapa le corresponden 7 tareas y nos sobrarian 2 que utilizaremos mas adelante.

Podriamos crear una matriz con las 14 etapas y asignarles el valor 7 a cada elemento de la matriz.

a(1),a(2),a(3)..... a(13),a(14)
buscamos la mitad de la matriz

seria 14/2=7

partimos la matriz en esas dos mitades

a(1)..... a(7)
a(8)......a(14)

Y realizamos la siguiente operacion:

a(8)= a(8)
a(7)=a(7)
los dejamos igual porque son los valores intermedios de la matriz, al ser esta par

si la mitad de la matriz fuera impar, tan solo se dejaria el elemento central de esta igual.



a(9)=a(9)-1
a(6)=a(6)-2

........


hasta llegar a: a(14)=a(14)-6
a(1)=a(1)+6

Como nos sobraban dos elementos lo repartimos según nuestra necesidad podria ser: a(14)=a(14)+1
a(1)=a(1)+1

No me pidas que te escriba el codigo porque con est esquema deberias saber desarrollarlo tu.

No es tan dificil... si lo haces de una forma "poco elegante" como la mia, es más pense que ya lo habia resuelto, en mi primer post al parecer entendi mal el enunciado... bueno ahi les va mi solucion nro 2:

. for (i=0; i. {
. for (j=0; j. {
. Codigo para asignar tarea a la etapa " i+1 ";
. tareas--;
. }
. }
.
.// Hasta este punto se esta llenando las etapas con tareas en
.// forma decreciente, por ejemplo:
.// Si tiene 3 etapas entonces en la etapa 1, habran 3 tareas,
.// en la etapa 2, habran 2 tareas y en la etapa 3 habra 1 tarea.
.
.while (tareas>0)
.{
. for (i=0; i. {
. Codigo para asignar tarea a la etapa " i+1 ";
. tareas--;
. }
.}
.
.// En esta segunda parte del codigo se llena con una tarea cada
.// etapa para mantener la simetria lograda anteriormente.


Esto es lo que buscabas?
Si no es esto... debe ser que entiendo mal o algo asi...

Salu2.

PD: Obviamente se logran mejores resultados cuando el número
total de tareas excede al necesitado por la primera parte del
código.