elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Arreglado, de nuevo, el registro del warzone (wargame) de EHN


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Como planteariais este problema?( en C)
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: 1 [2] Ir Abajo Respuesta Imprimir
Autor Tema: Como planteariais este problema?( en C)  (Leído 5,037 veces)
leosansan


Desconectado Desconectado

Mensajes: 1.314


Ver Perfil
Re: Como planteariais este problema?( en C)
« Respuesta #10 en: 5 Noviembre 2012, 22:56 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!.


En línea

BatchianoISpyxolo

Desconectado Desconectado

Mensajes: 166


Ver Perfil
Re: Como planteariais este problema?( en C)
« Respuesta #11 en: 6 Noviembre 2012, 01:39 am »

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.


En línea

Puede que desees aprender a programar desde 0: www.espascal.es
oxi12pek

Desconectado Desconectado

Mensajes: 15



Ver Perfil
Re: Como planteariais este problema?( en C)
« Respuesta #12 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!
En línea

Algun dia lo sere...
BatchianoISpyxolo

Desconectado Desconectado

Mensajes: 166


Ver Perfil
Re: Como planteariais este problema?( en C)
« Respuesta #13 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.
« Última modificación: 6 Noviembre 2012, 16:19 pm por BatchianoISpyxolo » En línea

Puede que desees aprender a programar desde 0: www.espascal.es
oxi12pek

Desconectado Desconectado

Mensajes: 15



Ver Perfil
Re: Como planteariais este problema?( en C)
« Respuesta #14 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.
En línea

Algun dia lo sere...
Páginas: 1 [2] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Ayudenme con este problema, q nose como se hace y ni lo entiendo
.NET (C#, VB.NET, ASP)
luix87 9 5,023 Último mensaje 28 Septiembre 2009, 16:27 pm
por Atrum
ayuda como soluciono este problema :)
PHP
sh0ck-r00t 1 2,128 Último mensaje 3 Octubre 2009, 03:55 am
por Embusterillo de bolsillo
como puedo solucionar este problema con actiosnscript 3 en flash cs4?
Diseño Gráfico
Belial & Grimoire 1 5,104 Último mensaje 13 Enero 2010, 22:15 pm
por peib0l
como solucono este problema
Desarrollo Web
cotin 2 2,191 Último mensaje 22 Marzo 2017, 00:18 am
por cotin
(Pregunta): ¿Como se solucionaria este problema de actualización?
PHP
Leguim 3 2,321 Último mensaje 14 Octubre 2019, 03:23 am
por Leguim
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines