Desafio 04 "Busqueda" Muy Avanzados

[JoRgE-1987]

Enunciado del problema:

El problema consiste en escribir una funcion MitadMasUno que calcule, si existe, el elemento "Mitad-Mas-Uno" de un vector de "n" numeros naturales, con por lo menos un elemento. Los elementos pueden estar desordenados.

Se entiende por elemento "Mitad-Mas-Uno" a aquel que aparezca repetido en una cantidad de veces mayor a la mitad de la cantidad de elementos que posee el conjunto.
Ej: En un array de 10 elementos, va a ser Mitad-Mas-Uno, aquel elemnto que se repita, una vez mas que la mitad de elementos, osea que si la mitad de elementos es 5, el elemento "Mitad-MasUno", va a ser aquel, que se repita por lo menos 6 veces.

La funcion MitadMasUno devera ser programada para trabajar sobre un vector o arreglo unidimensional que contenga los elementos del conjunto.
Devera devolver el numero natural que sea el elemento "Mitad-Mas-Uno" si es que existe, o bien -1 si no existe tal elemento.

No solo se devera codificar la funcion MitadMasUno, sino tambien mostrar su invariacion con distintos vectores o arreglos diferentes (En tamaño y elementos) para verificar su correctividad.

Criterio por orden de importancia:
* Que resuelva el problema planteado
* Que recorra como maximo dos veces el vector, para hallar la solucion.
* Que use la menor cantidad de espacio posible (Memoria y/o disco) para resolver el problema.
* Que funcione eficientemente (Que no haga cosas inecesarias).
* Que sea solida (No aborte la ejecucion, no acceda afuera de los limites del vector, etc...).

El codigo de fuente, deve estar comentado, para comprobar su realizacion real por parte del programador.


Bueno, este es un desafio real, no es de esos desafios, que mas que desafios son juegos, este es un desafio real, de un campeonado de programacion de Argentina.
Bue, oviamente yo no gane, pero por lo menos hice el intento, otro año sera.

Espero que lo disfruten, y que aprendan cosas nuevas intentando resolver este desafio.

Saludos :D

[JoRgE-1987]

Vamos che, que pasa? Andan con mucho laburo, mucho estudio, o que pasa?

Todabia, ni siquiera una pregunta hicieron.

Saludos :D

[jb]

necesito un ejemplo por favor: no entiendo sobre todo esta frase: " No solo se deberá codificar la función MitadMasUno, sino también mostrar su invariación con distintos vectores o arreglos diferentes (En tamaño y elementos) para verificar su correctividad."

Gracias

[JoRgE-1987]

necesito un ejemplo por favor: no entiendo sobre todo esta frase: " No solo se deberá codificar la función MitadMasUno, sino también mostrar su invariación con distintos vectores o arreglos diferentes (En tamaño y elementos) para verificar su correctividad."

Gracias

Osea, que la funcion que uses, tiene que funcionar, tanto para un vector de 7 elementos, como para uno de 153, o para uno de 3, o para uno de 32, osea, se tiene que demostrar que la funcion es realmente inteligente en la busqueda, y no que es una suma matematica para llegar al resultado.

Saludos :D

[jb]

Código

unit mitad_mas_uno;
 
interface
 
const
  n=20;
type
  telem=integer;
  tvector=array[1..n] of telem;
var
  v:tvector=(1,10,2,10,3,10,4,10,5,10,6,10,7,10,8,10,9,10,10,10);
 
function Posicion_Elemento_Mitad_mas_Uno(v:tvector):integer;
 
implementation
uses dialogs,sysutils;
 
function Posicion_Elemento_Mitad_mas_Uno(v:tvector):integer;
var
  cont,i,j,mitad_1,accesos:integer;
  valor,sig:telem;
begin
  accesos:=0;
  mitad_1:=n div 2 + 1;
  result:=0;
  i:=1;
  while (i<mitad_1) and (result=0) do
  begin
    valor:=v[i];
    inc(accesos);
    cont:=1;
    sig:=v[i+1];
    inc(accesos);
    while (valor=sig) and (i<mitad_1) and (result=0)do
    begin
      inc(cont);
      inc(i);
      if cont=mitad_1
      then Result:=i
      else begin
        sig:=v[i+1];
        inc(accesos);
      end;
    end;
    j:=i+1;
    while (j<=n) and (result=0) and (n-j+cont+1>=mitad_1) do
    begin
      if valor=v[j] then inc(cont);
      inc(accesos);
      if cont=mitad_1 then Result:=i;
      inc(j);
    end;
    inc(i);
  end;
  ShowMessage(&#39;Accesos: &#39;+IntToStr(accesos)+&#39; Posición: &#39;+IntToStr(Result));
end;
 
end.

[JoRgE-1987]

Dame unos dias, que verifico si cumple con todas los requerimientos.

Igual, no hay premio, pero ganas reconocimiento, es una lastima que no estes registrado en el foro.

Saludos :D