Web Log di Adrian Florea

"You know you've achieved perfection in design, not when you have nothing more to add, but when you have nothing more to take away." Antoine de Saint-Exupery
posts - 440, comments - 2715, trackbacks - 3944

My Links

Archives

Post Categories

Image Galleries

.RO Blogs

.RO People

.RO Sites

Blogs

Furls

Links

vinCitori

Sogno di una notte di mezza estate - #1 (i vincitori con le loro soluzioni)

Come promesso, ecco i vincitori con le loro soluzioni. Ricordiamoci prima il problema:

Dato un array di interi dispari, oddArray, che determina una sequenza monotona crescente, e un intero pari, evenValue, si chiede di implementare la funzione:

public static int IndexOfOddGreaterThanEven(int[] oddArray, int evenValue)

che ritorni l'indice del primo elemento di oddArray maggiore di evenValue. Nel caso evenValue > max(oddArray) la funzione ritorna -1. Si presuppone che i parametri siano validi e che quindi l'implementazione non richieda una verifica di questi. Nell'implementazione è vietato l'uso di istruzioni di selezione, istruzioni di iterazione oppure dell'operatore condizionale "?"!

Abbiamo un array ordinato di elementi (interi dispari) e dobbiamo cercare al suo interno in base a un elemento (intero pari) che sappiamo non fare parte di esso. L'elemento dispari che stiamo cercando dev'essere il primo maggiore dell'intero pari (siccome l'array è una sequenza monotona crescente, il primo sarà anche il più piccolo). Il Framework ci offre il metodo statico System.Array.BinarySearch che, nel caso evenValue > max(oddArray) ritorna "the bitwise complement of (the index of the last element + 1)", mentre nel caso evenValue < max(oddArray) ritorna "the bitwise complement of the index of the first element that is larger than value". In tutti e due i nostri casi, ritorna quindi il complemento binario di un indice. Conviene perciò concentrarsi sulla funzione ~System.Array.BinarySearch (cioè abbiamo applicato il complemento binario al valore ritornato - perché? perché l'operatore complemento binario è identico al suo inverso o, in altre parole, il complemento binario doppiamente applicato non cambia l'operando). Cosa ritorna allora nel nostro caso ~System.Array.BinarySearch?

  • oddArray.Length quando evenValue > max(oddArray)
  • l'indice del primo elemento di oddArray maggiore di evenValue quando evenValue < max(oddArray)

Ci siamo quasi. Manca solo che ritorni -1 al posto di oddArray.Length. Dobbiamo quindi trovare una funzione che ritorni:

  • x quando x è da 0 a oddArray.Length - 1
  • -1 quando x = oddArray.Length

Sembra una specie di modulo. Il modulo x % oddArray.Length cosa avrebbe ritornato?

  • x quando x è da 0 a oddArray.Length - 1
  • 0 quando x = oddArray.Length

Come fare a ottenere -1 al posto di 0? Semplice: (x + 1) % (oddArray.Length + 1) - 1. Per non lasciare spazio a dubbi dimostriamo che (x + 1) % (oddArray.Length + 1) - 1 è:

  • x per x da 0 a oddArray.Length - 1
  • -1 per x = oddArray.Length

Abbiamo che (x + 1) % (oddArray.Length + 1) - 1 è:

  • x + 1 - 1 per x + 1 da 0 a oddArray.Length + 1 - 1
  • 0 - 1 per x + 1 = oddArray.Length + 1 - 1

cioè (x + 1) % (oddArray.Length + 1) - 1 è:

  • x per x + 1 da 0 a oddArray.Length
  • -1 per x + 1 = oddArray.Length

oppure:

  • x per x da -1 a oddArray.Length - 1
  • -1 per x = oddArray.Length - 1

Ci sta benissimo il fatto che la funzione ritorni x quando x = -1. Quindi? Quindi abbiamo dimostrato che:

// la soluzione di Ernest Morariu (3), Roberto Messora (4)
public static int IndexOfOddGreaterThanEven(int[] oddArray, int evenValue)
{
  return (~Array.BinarySearch(oddArray, evenValue) + 1) % (oddArray.Length + 1) - 1;
}

è una soluzione. Ma con il vostro aiuto, non l'unica!

Flavio Polesello è stato il primo che mi ha mandato una soluzione corretta. Eccola qui:

// la soluzione di Flavio Polesello (1)
public static int IndexOfOddGreaterThanEven(int[] oddArray, int evenValue)
{
  return ~(Array.BinarySearch(oddArray, evenValue) % (~oddArray.Length));
}

Complimenti Flavio! Flavio ieri sera mi ha mandato un suo quiz con una soluzione di una bellezza non da poco... (e l'ho convinto di aprirsi un blog qui perchè mi sa che ne abbia di cose da dire - ho fatto bene?)

M.rkino (cliccate sul link, non porta al suo blog! :-)) è stato il secondo che mi ha mandato una soluzione corretta:

// la soluzione di Marco Barzaghi (2)
public static int IndexOfOddGreaterThanEven(int[] oddArray, int evenValue)
{
  ArrayList numbers = new ArrayList(oddArray);
  numbers.Add(evenValue);
  numbers.Sort();
  numbers.Add(string.Empty);
  int evenIndex = numbers.IndexOf(evenValue);
  object itemGreaterThanEven = numbers[evenIndex + 1];
  return Array.IndexOf(oddArray, itemGreaterThanEven);
}

Ernest Morariu è stato il primo che ha trovato la mia stessa identica soluzione e il terzo che mi ha mandato una soluzione corretta.

Roberto Messora è stato il secondo che ha trovato la mia stessa identica soluzione e il quarto che mi ha mandato una soluzione corretta.

Marco Poponi è stato il quinto e l'ultimo che mi ha mandato una soluzione corretta:

// la soluzione di Marco Poponi (5)
public static int IndexOfOddGreaterThanEven(int[] oddArray, int evenValue)
{
  int[] temparray= new int[oddArray.Length + 1];
  oddArray.CopyTo(temparray, 0);
  temparray[oddArray.Length] = int.MinValue;
  return Array.IndexOf(oddArray, temparray[-1 - Array.BinarySearch(oddArray,evenValue)]);
}

In tanti avete provato e questa è la roba più importante.

Grazie a tutti e tenete d'occhio Flavio Polesello! :-)

Print | posted on mercoledì 14 luglio 2004 18:01 | Filed Under [ Test Sharp ]

Powered by:
Powered By Subtext Powered By ASP.NET