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:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define VALORES 100000
typedef struct nodo
{
int dato;
struct nodo *sig;
}Nodo;
void agregarTarjetas(int x,Nodo **cabeza);
void imprimirTarjetas(Nodo *cabeza);
void eliminarTarjetas(Nodo *cabeza);
Nodo *crearNodo(int x);
int main()
{
int numeroTarjetas,i,x;
Nodo *cabeza;
cabeza = NULL;
srand(time(NULL));
do
{
printf("Dame numero de tarjetas: ");
scanf("%d",&numeroTarjetas);
system("cls");
}while((numeroTarjetas < 1)||(numeroTarjetas > 100));
for(i = 0;i < numeroTarjetas;i++)
{
x = rand()% VALORES+1;
agregarTarjetas(x,&cabeza);
}
printf("Archivo original\n");
imprimirTarjetas(cabeza);
eliminarTarjetas(cabeza);
printf("despues\n");
imprimirTarjetas(cabeza);
return 0;
}
void agregarTarjetas(int x,Nodo **cabeza)
{
Nodo *nuevo;
nuevo = crearNodo(x);
nuevo->sig = *cabeza;
*cabeza = nuevo;
}
Nodo *crearNodo(int x)
{
Nodo *p;
p = (Nodo*)malloc(sizeof(Nodo));
p->dato = x;
p->sig = NULL;
return p;
}
void imprimirTarjetas(Nodo *cabeza)
{
Nodo *ptr;
for(ptr = cabeza;ptr!=NULL;ptr = ptr->sig)
printf("[%d]",ptr->dato);
}
void eliminarTarjetas(Nodo *cabeza)
{
Nodo *ptr1,*ptr2;
for(ptr1 = cabeza,ptr2 = ptr1->sig;ptr2!=NULL;ptr2 = ptr2->sig)
{
if(ptr2->dato < ptr1->dato)
ptr1->sig = ptr2->sig;
else
ptr1 = ptr1->sig;
}
}
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define VALORES 100000
int *ingresarValores(int numeroTarjetas,FILE *fd);
void eliminarTarjetas(int tarjetas[],int numeroTarjetas,FILE *fd);
int main()
{
FILE *fd;
int numeroTarjetas,*tarjetas;
srand(time(NULL));
if((fd = fopen("F:\\Archivo_Analisis_Algoritmos.txt","w"))!= NULL)
{
do
{
printf("Dame el numero de tarjetas: ");
scanf("%d",&numeroTarjetas);
system("cls");
}while((numeroTarjetas < 1)||(numeroTarjetas > 1000));
fprintf(fd,"Archivo de Texto:\n\n");
tarjetas = ingresarValores(numeroTarjetas,fd);
eliminarTarjetas(tarjetas,numeroTarjetas,fd);
}
else
printf("No se pudo crear archivo\n");
return 0;
}
int *ingresarValores(int numeroTarjetas,FILE *fd)
{
int i,*buffer;
buffer = (int*)malloc(numeroTarjetas*sizeof(int));
for(i = 0;i < numeroTarjetas;i++)
{
buffer[i] = rand()% VALORES+1;
printf("[%d]",buffer[i]);
fprintf(fd,"%d,",buffer[i]);
if((i%10==0)&&(i!=0))
fprintf(fd,"\n");
}
return buffer;
}
void eliminarTarjetas(int tarjetas[],int numeroTarjetas,FILE *fd)
{
int i,j;
for(i=0;i < numeroTarjetas;i++)
{
for(j=i+1;j < numeroTarjetas;j++)
{
if(tarjetas[j] < tarjetas[i])
tarjetas[i] = -1;
}
}
fprintf(fd,"\n\nTarjetas eliminadas\n");
for(i=0;i < numeroTarjetas;i++)
{
if(tarjetas[i] != -1)
fprintf(fd,"[%d]",tarjetas[i]);
}
}
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
Cita de: m@o_614 en 9 Noviembre 2013, 06:02 AMTengo 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
El problema que te piden resolver es Wikipedia: Longest increasing subsequence (http://en.wikipedia.org/wiki/Longest_increasing_subsequence)
Un saludo
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