2011-09-25 40 views
5

Un caracol se arrastra x pies por una pared durante el día. Después de todo el trabajo que hace durante el día, se detiene un momento ... ¡pero se duerme! A la mañana siguiente se despierta y descubre que se ha caído mientras duerme.Soluciones optimizadas para mi tarea

Si esto ocurre todos los días, ¿cuántas veces se arrastrará el caracol para cubrir n paredes de diferente altura?

He escrito una función para contar el número de pelos de punta del caracol como se muestra a continuación:

void count(int move_forward, int move_backward, int number_walls, int[] height) 
    { 
     int count = number_walls, diff = move_forward - move_backward; 
     while (number_walls--) 
      for (move_backward = move_forward; move_backward < height[number_walls]; move_backward += diff) 
       count++; 
    } 

Está funcionando bien. Pero quería saber si hay alguna otra forma de resolver este problema para optimizar aún más la velocidad del programa.

+3

(height-x)/(x-y) +1, no se requieren bucles – amit

+2

@Jay, BTW - El consejo que recibió en la pregunta inicial sobre el uso de nombres de variables significativos es discutible en el contexto de bucles internos. Demasiados nombres demasiado largos hacen que su código sea tan ilegible como un montón de nombres crípticos de una y dos letras. Se trata de equilibrio. – dmckee

+1

Un comentario más, siempre y cuando esté metiendo la nariz. El objetivo de este ejercicio puede ser mostrarte ese poco sentado y pensar por un rato que puedes resolver el problema de las paredes individuales desde 'O (altura)' (el forma en que lo estabas intentando) a 'O (1)' (la forma en que amit lo resuelve). – dmckee

Respuesta

7

solución es ((height-x)/(x-y))+1, no se requieren bucles.

el caracol tiene que subir a: height-x, y le toma ((height-x)/(x-y)) días. Una vez que está allí, le toma un día extra escalar las x restantes.

EDIT: como se ha mencionado en los comentarios, esta solución resuelve el problema para cada pared, que necesita para iterar sobre la matriz heights, y resumir estos resultados, que le ahorra al menos el bucle interno, por lo que es O (n), en su lugar O (n * h), donde n es el número de muros, y h es la altura de las paredes.

(*) nota: que es posible que desee guardar el recordatorio para cada pared [es decir cuánto puede seguir el caracol después de haber pasado este muro], y restarlo de la próxima pared, depende de la descripción de la tarea ... Si el caracol puede pasar un máximo de una pared por día, ignore este último comentario.

+0

¿elaborará el infractor? – amit

+2

No soy el que menosprecia, pero creo que es porque la altura es una matriz de valores. Aún necesitará un bucle para obtener la altura total o aplicar la solución a cada altura. – tinman

+0

@tinman: tiene razón, esta respuesta muestra cómo hacerlo para una sola pared, lo mencionaré explícitamente. gracias por el comentario. – amit

Cuestiones relacionadas