Título: programa tarjetas Publicado por: m@o_614 en 9 Noviembre 2013, 06:02 am Saludos
Tengo el siguiente programa que dice: Tengo n tarjetas numeradas en cierto orden(al azar), y hay que eliminar algunas de esas tarjetas, de tal forma que las que queden esten ordenadas ascendentemente, y cuyos valores esten entre el rango 1 <= valores <= 100,000, esto ya lo codifique pero el problema que tengo es que me pide encontrar el menor numero de tarjetas que se pueden eliminar y es lo que no entiendo como hacerlo, o sea que tengo que buscar todas las posibilidades y despues verificar cual es la que puede eliminar el menor numero de tarjetas?? el codigo es el siguiente: Código
esta la hice con listas con apuntadores porque pense que seria mas facil hacer las eliminaciones, aunque tambien lo habia hecho de esta otra manera, y las dos funcionan solo que no se como hacer un algoritmo que me determine cual es el menor numero de tarjetas que se pueden eliminar Código
por ejemplo si tengo los numeros [11,500][22,924][13,449][21,933][13,150][1,858][11,516], se que el menor numero de eliminaciones serian 4, y quedaria asi: [11,500][13,449][21,933], pero trate de buscarle la logica y no supe como de antemano gracias Título: Re: programa tarjetas Publicado por: rir3760 en 9 Noviembre 2013, 15:59 pm Tengo el siguiente programa que dice: El problema que te piden resolver es Wikipedia: Longest increasing subsequence (http://en.wikipedia.org/wiki/Longest_increasing_subsequence)Tengo n tarjetas numeradas en cierto orden(al azar), y hay que eliminar algunas de esas tarjetas, de tal forma que las que queden esten ordenadas ascendentemente, y cuyos valores esten entre el rango 1 <= valores <= 100,000, esto ya lo codifique pero el problema que tengo es que me pide encontrar el menor numero de tarjetas que se pueden eliminar y es lo que no entiendo como hacerlo Un saludo Título: Re: programa tarjetas Publicado por: m@o_614 en 11 Noviembre 2013, 00:31 am muchas gracias rir3760 por tu respuesta, estuve leyendo el enlace que pusiste y ahi dice que se puede resolver el problema utilizando solamente arrays y busqueda binaria, pero que la busqueda binaria no es solo para los array ordenados?? o sea que tengo antes que nada ordenar el vector y despues realizar la busqueda binaria del elemento menor del arreglo?? el parrafo dice:
procesa la secuencia de elementos en orden, manteniendo la subsecuencia de incrementos mas larga obtenida hasta ahora. Aqui no se a que se refiere con subsecuencia obtenida, obtenida cuando?? si hasta ahora solo se ha ordenado el arreglo de nuevo gracias |