c3-4 (779474)
Текст из файла
3.4 How to Search an Ordered Table1173.4 How to Search an Ordered Tablevoid locate(float xx[], unsigned long n, float x, unsigned long *j)Given an array xx[1..n], and given a value x, returns a value j such that x is between xx[j]and xx[j+1]. xx must be monotonic, either increasing or decreasing. j=0 or j=n is returnedto indicate that x is out of range.{unsigned long ju,jm,jl;int ascnd;}jl=0;Initialize lowerju=n+1;and upper limits.ascnd=(xx[n] >= xx[1]);while (ju-jl > 1) {If we are not yet done,jm=(ju+jl) >> 1;compute a midpoint,if (x >= xx[jm] == ascnd)jl=jm;and replace either the lower limitelseju=jm;or the upper limit, as appropriate.}Repeat until the test condition is satisfied.if (x == xx[1]) *j=1;Then set the outputelse if(x == xx[n]) *j=n-1;else *j=jl;and return.A unit-offset array xx is assumed.
To use locate with a zero-offset array,remember to subtract 1 from the address of xx, and also from the returned value j.Search with Correlated ValuesSometimes you will be in the situation of searching a large table many times,and with nearly identical abscissas on consecutive searches. For example, youmay be generating a function that is used on the right-hand side of a differentialequation: Most differential-equation integrators, as we shall see in Chapter 16, callSample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).Suppose that you have decided to use some particular interpolation scheme,such as fourth-order polynomial interpolation, to compute a function f(x) from aset of tabulated xi ’s and fi ’s. Then you will need a fast way of finding your placein the table of xi ’s, given some particular value x at which the function evaluationis desired.
This problem is not properly one of numerical analysis, but it occurs sooften in practice that it would be negligent of us to ignore it.Formally, the problem is this: Given an array of abscissas xx[j], j=1, 2, . . . ,n,with the elements either monotonically increasing or monotonically decreasing, andgiven a number x, find an integer j such that x lies between xx[j] and xx[j+1].For this task, let us define fictitious array elements xx[0] and xx[n+1] equal toplus or minus infinity (in whichever order is consistent with the monotonicity of thetable). Then j will always be between 0 and n, inclusive; a value of 0 indicates“off-scale” at one end of the table, n indicates off-scale at the other end.In most cases, when all is said and done, it is hard to do better than bisection,which will find the right place in the table in about log2 n tries.
We already did usebisection in the spline evaluation routine splint of the preceding section, so youmight glance back at that. Standing by itself, a bisection routine looks like this:118Chapter 3.3264513281(b)hunt phase7 10142238bisection phaseFigure 3.4.1. (a) The routine locate finds a table entry by bisection. Shown here is the sequenceof steps that converge to element 51 in a table of length 64. (b) The routine hunt searches from aprevious known position in the table by increasing steps, then converges by bisection.
Shown here is aparticularly unfavorable example, converging to element 32 from element 7. A favorable example wouldbe convergence to an element near 7, such as 9, which would require just three “hops.”for right-hand side evaluations at points that hop back and forth a bit, but whosetrend moves slowly in the direction of the integration.In such cases it is wasteful to do a full bisection, ab initio, on each call. Thefollowing routine instead starts with a guessed position in the table. It first “hunts,”either up or down, in increments of 1, then 2, then 4, etc., until the desired value isbracketed.
Second, it then bisects in the bracketed interval. At worst, this routine isabout a factor of 2 slower than locate above (if the hunt phase expands to includethe whole table). At best, it can be a factor of log2 n faster than locate, if the desiredpoint is usually quite close to the input guess. Figure 3.4.1 compares the two routines.void hunt(float xx[], unsigned long n, float x, unsigned long *jlo)Given an array xx[1..n], and given a value x, returns a value jlo such that x is betweenxx[jlo] and xx[jlo+1].
xx[1..n] must be monotonic, either increasing or decreasing.jlo=0 or jlo=n is returned to indicate that x is out of range. jlo on input is taken as theinitial guess for jlo on output.{unsigned long jm,jhi,inc;int ascnd;ascnd=(xx[n] >= xx[1]);True if ascending order of table, false otherwise.if (*jlo <= 0 || *jlo > n) {Input guess not useful. Go immediately to bisec*jlo=0;tion.jhi=n+1;} else {inc=1;Set the hunting increment.if (x >= xx[*jlo] == ascnd) { Hunt up:if (*jlo == n) return;jhi=(*jlo)+1;while (x >= xx[jhi] == ascnd) {Not done hunting,*jlo=jhi;inc += inc;so double the incrementjhi=(*jlo)+inc;if (jhi > n) {Done hunting, since off end of table.jhi=n+1;break;}Try again.Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).1(a)Interpolation and Extrapolation3.4 How to Search an Ordered Table119}If your array xx is zero-offset, read the comment following locate, above.After the HuntThe problem: Routines locate and hunt return an index j such that yourdesired value lies between table entries xx[j] and xx[j+1], where xx[1..n] is thefull length of the table.
But, to obtain an m-point interpolated value using a routinelike polint (§3.1) or ratint (§3.2), you need to supply much shorter xx and yyarrays, of length m. How do you make the connection?The solution: Calculatek = IMIN(IMAX(j-(m-1)/2,1),n+1-m)(The macros IMIN and IMAX give the minimum and maximum of two integerarguments; see §1.2 and Appendix B.) This expression produces the index of theleftmost member of an m-point set of points centered (insofar as possible) betweenj and j+1, but bounded by 1 at the left and n at the right. C then lets you call theinterpolation routine with array addresses offset by k, e.g.,polint(&xx[k-1],&yy[k-1],m,. .
. )CITED REFERENCES AND FURTHER READING:Knuth, D.E. 1973, Sorting and Searching, vol. 3 of The Art of Computer Programming (Reading,MA: Addison-Wesley), §6.2.1.Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).}Done hunting, value bracketed.} else {Hunt down:if (*jlo == 1) {*jlo=0;return;}jhi=(*jlo)--;while (x < xx[*jlo] == ascnd) {Not done hunting,jhi=(*jlo);inc <<= 1;so double the incrementif (inc >= jhi) {Done hunting, since off end of table.*jlo=0;break;}else *jlo=jhi-inc;}and try again.}Done hunting, value bracketed.}Hunt is done, so begin the final bisection phase:while (jhi-(*jlo) != 1) {jm=(jhi+(*jlo)) >> 1;if (x >= xx[jm] == ascnd)*jlo=jm;elsejhi=jm;}if (x == xx[n]) *jlo=n-1;if (x == xx[1]) *jlo=1;120Chapter 3.Interpolation and Extrapolation3.5 Coefficients of the Interpolating Polynomialy = c 0 + c1 x + c2 x 2 + · · · + cN x N(3.5.1)then the ci ’s are required to satisfy the linear equation1x01...1x20x1...x21...xNx2N c· · · xN00· · · xN1 c1·..
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
