DO KTERÉHO INTERVALU PATŘÍ?

PROBLÉM
Je dáno číselné pole A.J, J=1,...,N, s prvky, které tvoří buď roztoucí nebo klesající posloupnost, a číslo V. Určete přirozené číslo J takové, že hodnota V patří do intervalu [A.J,A.Jp1], kde Jp1=J+1.

ALGORITMUS
Použijeme-li metodu půlení intervalu (vlastně dichotomické vyhledávání), získáme odpověď v průměru po lgN porovnáních.

IMPLEMENTACE
Jednotka: vnitřní funkce
 
Globální proměnné: roztoucí nebo klesající posloupnost A.1,...,A.N
 
Parametry: přirozené číslo N, číslo V
 
Vrací: číslo J takové, že V patří do intervalu [A.J,A.Jp1], kde Jp1=J+1. Je-li J=0 nebo J=N, pak V neleží v žádném ze zadaných intervalů.

 

LOCATE: procedure expose A.
parse arg N, V
L = 0; U = N + 1; Ascnd = (A.N >= A.1)
do while (U - L) > 1
  M = (U + L) % 2
  if (V >= A.M) = Ascnd then L = M
    else U = M
end
if V = A.1 then return 1
if V = A.N then return N - 1
return L

 

SOUVISLOSTI

Literatura
Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. Numerical Recipes in C the art of scientific computing
2nd ed. University Press, Cambridge, 1992


Obálka Obsah Index Hlavní stránka

změněno 30. července 2000
Copyright © 2000-2001 Vladimír Zábrodský, RNDr.