programa tarjetas

[m@o_614]

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 (c) [Seleccionar] Expandir

#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

Código (c) [Seleccionar] Expandir

#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

[rir3760]

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

El problema que te piden resolver es Wikipedia: Longest increasing subsequence

Un saludo

[m@o_614]

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