Wartość najbliższa do danej - jaki algorytm ?

0

Mamy problem tego rodzaju:

  • na wejściu dostajemy jedną liczbę M
  • następnie na wejściu mamy podane N-liczb
  • liczbę M zapisujemy sobie do pojedynczej zmiennej
  • N-liczb zapisujemy sobie do tablicy (np. dynamicznej jednowymiarowej w C++)

Teraz trzeba znaleźć wśród liczb w tablicy pierwszą z kolei liczbę, która jest najbliższa (lub równa) liczbie M. Dla wyjaśnienia: "pierwsza z kolei" to ta, która będzie najbliższa M przy iteracji od początku tablicy. Założenie jest takie, że (przynajmniej na razie) rozpatruję tylko liczby naturalne (unsigned int).

Np.: (--> wynik)

M: 5
N: 7 1 3 5 3
--> 5

M: 4
N: 1 2 3 5
--> 3

M: 3
N: 9 8 7 6 5
--> 5

M: 8
N: 1 2 3 4
--> 4

Jest jakiś (pewnie jest) algorytm, który pomaga w takim sprawdzaniu ?

Pierwsze rozwiązanie, które przychodzi mi do głowy to sprawdzanie mniej więcej tak:

  1. Iterujemy po wszystkich elementach tablicy.
  2. Przy każdej iteracji sprawdzamy czy i-ty element jest równy M.
    2a. TAK: wiadomo, przerywamy pętlę i zwracamy wartość i-tego elementu.
    2b. NIE: sprawdzamy wartość bezwzględną. Każdą z takich wartości trzeba gdzieś zapisać.
  3. Wynikiem będzie i-ty element, do którego będzie "przypisana" najmniejsza wartość bezwzględna.

Myślę, że sprawdzanie z pkt. 2 jest ok. To, co się wykonuje w 2a jest logiczne. Gdy liczby nie będą równe można nieco rozwinąć algorytm (2b):

Tworzymy dwie zmienne - jedna przechowuje indeks (index), druga wartość bezwzględną (abs). Wartość bezwzględna jest sprawdzana, jeśli przy którymś elemencie będzie mniejsza, niż aktualnie przechowywana, wtedy zmieniamy zawartość index i abs. Ostatecznie zwracamy zawartość tab[index].

Czy takie postępowanie jest dobre ?

0

Problem jest na tyle prosty (zwłaszcza, że nie szukasz najwydajniejszego rozwiązania, a jakiegokolwiek), że odeślę cię do googli:
finding closest (albo nearest) number in a set (array)

0

http://ideone.com/0LHvv mam takie coś, nie wiem, gdzie leży błąd. Program niby kompiluje się i wykonuje, ale nic nie zwraca.

1 użytkowników online, w tym zalogowanych: 0, gości: 1