Foro de elhacker.net

Programación => Programación C/C++ => Mensaje iniciado por: oxi12pek en 5 Noviembre 2012, 17:13 pm


Título: Como planteariais este problema?( en C)
Publicado por: oxi12pek en 5 Noviembre 2012, 17:13 pm
Tengo un problemilla.Tengo que entregar esta semana un trabajo en el que hay un ejercicio en el que me pide que guarde en una variable el numero mas alto de un array y el segundo mas alto. No tengo ningun problema para conseguir el mas alto, pero el segundo me cuesta entenderlo. Como lo planteariais? No os pido que me hagais el ejercicio si no comentarme los conceptos para que yo pueda avanzar en mi aprendizaje. No soy de esos que pide ayuda muy facilmente y menos para quitarme trabajo, especialmente en esta aficcion!!!
Gracias.

Título: Re: Como planteariais este problema?( en C)
Publicado por: xiruko en 5 Noviembre 2012, 17:28 pm
pide los numeros y almacenalos en el array, luego ordenalo de mayor a menor y quedate con los 2 primeros.

un saludo!

Título: Re: Como planteariais este problema?( en C)
Publicado por: BatchianoISpyxolo en 5 Noviembre 2012, 17:30 pm
La manera más sencilla de pensar es lo siguiente:

Creas una función de máximo y declaras una variable struct con dos campos, x e y de tipo int o simplemente dos variables x e y de tipo int.

x = maximo(vector[0..n-1]); // máximo de todos
y = maximo(vector[0..n-2]); // segundo máximo

En el segundo vector, no puede estar x.

Advertencia - mientras estabas escribiendo, una nueva respuesta fue publicada. Probablemente desees revisar tu mensaje.

Si utilizas MergeSort, HeapSort o QuickSort (por ejemplo) sí sería buena idea ordenarlos.

Si no, puedes usar mi método que también vale.

Título: Re: Como planteariais este problema?( en C)
Publicado por: Oblivi0n en 5 Noviembre 2012, 17:51 pm
El codigo está en java, pero creo que lo entenderas
El caso es tener 2 variables, uno para el maximo, y otro para el submaximo, cuando el maximo cambie, submaximo pasa a valer el anterior valor de maximo

(devuelve una array con los 2 numeros)
P.D: La funcion recibe un array de enteros llamado "numeros"

Código
  1. int [] devolver = new int[2];
  2. 		int maximo = numeros[0];
  3. 		int submaximo = numeros[0];
  4.  
  5. 		for(int i = 0; i < numeros.length;i++){
  6. 			if(numeros[i] > maximo){
  7. 				int aux = maximo;	
  8. 				maximo = numeros[i];
  9. 				submaximo = aux;
  10.  
  11. 			}
  12. 		}
  13.  
  14. 		devolver[0] = maximo;
  15. 		devolver[1] = submaximo;
  16. 		return devolver;

Título: Re: Como planteariais este problema?( en C)
Publicado por: oxi12pek en 5 Noviembre 2012, 18:29 pm
Me han gustado mucho las dos ideas. Ahora las planteo y subo el resultado haber que os parece.
Muchas gracias por responder.

Título: Re: Como planteariais este problema?( en C)
Publicado por: oxi12pek en 5 Noviembre 2012, 18:39 pm
Perdon Oblivi0n no he visto tu respuesta antes de responder. Lo entiendo si. Habia pensado en ese mismo ejemplo . Muchas gracias!!!

Título: Re: Como planteariais este problema?( en C)
Publicado por: leosansan en 5 Noviembre 2012, 19:11 pm
Cita de: Oblivi0n en  5 Noviembre 2012, 17:51 pm
El caso es tener 2 variables, uno para el maximo, y otro para el submaximo, cuando el maximo cambie, submaximo pasa a valer el anterior valor de maximo
Citar
No exactamente, ya que un número podría ser menor que max y superior a cuasi_max, con lo que éste tomaría su valor.
Sin necesidad de ordenar previamente:
Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. #define N   15
  5. int main()
  6.  
  7. {
  8.     int i,a[N],aux,max,cuasi_maxi;
  9.     srand(time(0));
  10.  
  11.     for (i = 0; i < N; i++)
  12.         {
  13.             a[i]= 25+rand() % (101-25) ;
  14.             printf("%d, ", a[i]);
  15.  
  16.         } printf("\b\b \n");
  17.     if (a[0]<=a[1]) {max= a[1]; cuasi_maxi=a[0];}
  18.     else {max= a[0]; cuasi_maxi=a[1];}
  19.     for (i = 2; i < N; i++)
  20.     if (a[i]>=max) {aux=max;max=a[i];cuasi_maxi=aux;}
  21.     else if (a[i]>cuasi_maxi ) {cuasi_maxi=a[i];}
  22.         printf("%d   %d",max,cuasi_maxi);
  23.     return 0;
  24. }
Saludos!.

Título: Re: Como planteariais este problema?( en C)
Publicado por: oxi12pek en 5 Noviembre 2012, 19:20 pm
Bueno lo he terminado, pero justo cuando lo he terminado me ha entrado la curiosidad de como haria un programa que ordenara los numeros de menor a mayor y he hecho esto:
Código:
int main(void)
{
  int A[N],*p;
  printf("Escribe %d numeros por favor\n",N);
  for(p=A;p<A+N;p++)
    scanf("%d",p);
  standard_atoi(A,N);
  printf("Numeros ordenados de menor a mayor: ");
  for(p=A;p<A+N;p++)
    printf("%d ",*p);
    
}
void standard_atoi(int a[],int n)
{
  int *q,x;
  for(q=a;q<a+n;q++)
    if(*(q-1)>*q){
      x=*q;
      *q=*(q-1);
      *(q-1)=x;
    }


}
Porque no me funciona?

Título: Re: Como planteariais este problema?( en C)
Publicado por: BatchianoISpyxolo en 5 Noviembre 2012, 19:35 pm
Código:
Lo único que haces es intercambiar los valores cuando a[i-1] es mayor que a[i]

Ordenación por inserción:
Código
  1. void ord_ins(int v[], int n) {
  2.     int i,j,x;
  3.     for (i=1;i<n;i++) {
  4.         x = v[i];
  5.         j = i-1;
  6.         while ( (j>-1) && (v[j]>x) )
  7.             v[j+1] = v[j--];
  8.         v[j+1] = x;
  9.     }
  10. }

Ordenación por quicksort (mediana de 3). Teniendo en cuenta la macro UMBRAL:
Código
  1. void ord_ins(int v[], int n) {
  2.     int i,j,x;
  3.     for (i=1;i<n;i++) {
  4.         x = v[i];
  5.         j = i-1;
  6.         while ( (j>-1) && (v[j]>x) )
  7.             v[j+1] = v[j--];
  8.         v[j+1] = x;
  9.     }
  10. }
  11.  
  12. void intercambiar(int v[], int izq, int der) {
  13.     int t;
  14.     t = v[izq];
  15.     v[izq] = v[der];
  16.     v[der] = t;
  17. }
  18.  
  19. void mediana3 (int v[], int izq, int der) {
  20.     int k = (int)((izq+der)/2);
  21.     if ( v[k] > v[der] ) intercambiar(v, k, der);
  22.     if ( v[k] < v[izq] ) intercambiar(v, k, izq);
  23.     if ( v[k] > v[der] ) intercambiar(v, k, der);
  24. }
  25.  
  26. void quicksort(int v[], int n) {
  27.     void ordenarAux(int v[], int izq, int der) {
  28.         if ( izq+UMBRAL <= der ) {
  29.             mediana3(v,izq,der);
  30.             int pivote = v[izq];
  31.             int i = izq;
  32.             int j = der;
  33.             do {
  34.                 do i++;
  35.                 while ( v[i] < pivote );
  36.                 do j--;
  37.                 while ( v[j] > pivote );
  38.                 intercambiar(v, i, j);
  39.             } while (j > i);
  40.             intercambiar(v,i,j);
  41.             intercambiar(v,izq,j);
  42.             ordenarAux(v,izq,j-1);
  43.             ordenarAux(v,j+1,der);
  44.         }
  45.     }
  46.     ordenarAux(v,0,n-1);
  47.     if ( UMBRAL == 1 ) ord_ins(v,n);
  48.  
  49. }

Ahí tienes dos algoritmos de ordenación en C. Los tengo a mano porque tengo que implementarlos y analizar su complejidad para una práctica en estos momentos.

Saludos.

Título: Re: Como planteariais este problema?( en C)
Publicado por: Oblivi0n en 5 Noviembre 2012, 22:31 pm
No tiene sentido ordenar y luego extraer, quicksort en el mejor caso es n*log(n), unido a extraer quedaría O(n*log(n) + n).En el caso peor, sería O(n2).La complejidad de mi algoritmo es simplemente O(n). ( ya sé que no estamos discutiendo eficiencia)

Título: Re: Como planteariais este problema?( en C)
Publicado por: leosansan en 5 Noviembre 2012, 22:56 pm
Cita de: Oblivi0n en  5 Noviembre 2012, 22:31 pm
.La complejidad de mi algoritmo es simplemente O(n). ( ya sé que no estamos discutiendo eficiencia)
Citar
Eso no lo dudo, pero te recuerdo que el algoritmo, tal como lo planteates daría para la serie de números:
121 174 39 158 144 167 76 80 112 167 59 152 161 136 129
max=174    cuasi_max=121, cuando este último debería ser 167.
De ahí la introducción de :
Código
  1. else if (a[i]>cuasi_maxi ) {cuasi_maxi=a[i];}
Saludos!.

Título: Re: Como planteariais este problema?( en C)
Publicado por: BatchianoISpyxolo en 6 Noviembre 2012, 01:39 am
Cita de: Oblivi0n en  5 Noviembre 2012, 22:31 pm
No tiene sentido ordenar y luego extraer, quicksort en el mejor caso es n*log(n), unido a extraer quedaría O(n*log(n) + n).En el caso peor, sería O(n2).La complejidad de mi algoritmo es simplemente O(n). ( ya sé que no estamos discutiendo eficiencia)

Extraer es constante, no lineal: O(2) = O(1). Pero que sí, que se puede hacer lineal llevando el max y el cuasi_max a la par.

Título: Re: Como planteariais este problema?( en C)
Publicado por: oxi12pek en 6 Noviembre 2012, 11:32 am
Muchas gracias a todos por responder. Oye BatchianoISpyxolo!!! Podrias explicarme lo que ocurre en la funcion ord_ins?¿?¿ Es que no lo entiendo del todo.
Saludos!

Título: Re: Como planteariais este problema?( en C)
Publicado por: BatchianoISpyxolo en 6 Noviembre 2012, 16:08 pm
Lo mejor para entender como funciona sería una explicación gráfica. Así que te recomiendo algún pdf o algún vídeo incluso mejor.

Pongo el código para que lo puedas leer mejor:

Ordenación por inserción:
Código
  1. void ord_ins(int v[], int n) {
  2.     int i,j,x;
  3.     for (i=1;i<n;i++) {
  4.         x = v[i];
  5.         j = i-1;
  6.         while ( (j>-1) && (v[j]>x) )
  7.             v[j+1] = v[j--];
  8.         v[j+1] = x;
  9.     }
  10. }

índices del vector: 0..N-1 y ordenación ascendente

Bueno supongamos que tenemos el array { 7, 2, 6, 4, 8, -3 }

1º. Suponemos que el primer elemento está ordenado.

2º. Recorremos el array desde 1 hasta N-1, porque el primer elemento suponemos que está ordenado.

3º. Entonces teniendo en cuenta el for de 1 a N-1, en cada iteración del for escogeremos el elemento
Código:
array[i]
. Es decir, en la primera iteración el 2, en la siguiente al 6, en la siguiente al 4... Es decir x =
Código:
array[i]

4º Insertamos ordenadamente x en el subvector generado por los índices 0 e i-1. En este caso insertar x en el subvector { 7 }, porque va desde 0 a i-1, y como i vale 1, pues es el subvector array(0..0). Como 2 es menor que siete, lo insertamos delante.

array { 2, 7, 6, 4, 8, -3 } Hay que mover el 7 a la derecha y el 2 situarlo en la primera posición

5º Volvemos al paso 3 hasta terminar el ciclo for

-> { 2, 7, 6, 4, 8, -3 } seleccionamos el 6 e insertamos en { 2, 7 } => { 2, 6, 7, 4, 8, -3 }

-> { 2, 6, 7, 4, 8, -3 } seleccionamos el 4 e insertamos en { 2, 6, 7 } => { 2, 4, 6, 7, 8, -3 }

-> { 2, 4, 6, 7, 8, -3 } seleccionamos el 8 e insertamos en { 2, 4, 6, 7 } => { 2, 4, 6, 7, 8, -3 } <= El elemento está ya ordenado

-> { 2, 4, 6, 7, 8, -3 } seleccionamos el -3 e insertamos en { 2, 4, 6, 7, 8 } => { -3, 2, 4, 6, 7, 8,} <= Vualá, vector ordenado

Recuerda que para cada inserción tenemos que mover todos los elelementos desde la posición donde vamos a insertar hasta i-1 una posición hacia adelante.

Saludos y espero que lo entiendas.

Título: Re: Como planteariais este problema?( en C)
Publicado por: oxi12pek en 6 Noviembre 2012, 16:40 pm
Vale vale ahora lo veo mejor. Es que entregar un trabajo que no entiende ni lo que pasa no es muy educativo... jajajaja
Muchas gracias por la explicacion, esta muy bien.


Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines