ON ALGORITHMS FOR ORDINARY LEAST SQUARES REGRESSION SPLINE FITTING A COMPARATIVE STUDY

https://www.doczj.com/doc/7a18532055.html,put.Simul.,2002,V ol.72(8),pp.647–663

ON ALGORITHMS FOR ORDINARY LEAST

SQUARES REGRESSION SPLINE FITTING:

A COMP ARATIVE STUDY

THOMAS C.M.LEE*

Department of Statistics,Colorado State University,Fort Collins,CO80523-1877,USA

(Received25October2001;In?nal form4March2002)

Regression spline smoothing is a popular approach for conducting nonparametric regression.An important issue associated with it is the choice of a‘‘theoretically best’’set of knots.Different statistical model selection methods,such as Akaike’s information criterion and generalized cross-validation,have been applied to derive different‘‘theoretically best’’sets of knots.Typically these best knot sets are de?ned implicitly as the optimizers of some objective functions.Hence another equally important issue concerning regression spline smoothing is how to optimize such objective functions.In this article different numerical algorithms that are designed for carrying out such optimization problems are compared by means of a simulation study.Both the univariate and bivariate smoothing settings will be considered.Based on the simulation results,recommendations for choosing a suitable optimization algorithm under various settings will be provided.

Keywords:Bivariate smoothing;Generalized cross-validation;Genetic algorithms;Regression spline;Stepwise selection

1INTRODUCTION

An increasingly popular approach for performing nonparametric curve estimation is regres-sion spline smoothing.For this approach it is customary to assume that the‘‘true’’curve fexTto be recovered admits the expression

fexT?b0tb1xtááátb r x rt

X m

j?1b jexàk jTr

t

;e1T

where r is the order of the regression spline(usually chosen a priori),k j is the j th knot, b?eb0;...;b r;b1;...;b mTT is a set of coef?cients andeaTt?maxe0;aT.In order to esti-mate fexTusing(1),one needs to choose the number and the placement of the knots,as well as to estimate b.As mentioned in Wand(2000),there are two general strategies for carrying out this task.The?rst strategy is to select a relatively small number of knots and estimate b using ordinary least squares(further details will be given below).With this strategy,the choice of the knots is extremely important.Regression spline smoothing procedures follow-ing this strategy include Friedman and Silverman(1989),Koo(1997),Kooperberg,Bose and *Tel.:(970)4912185;Fax:(970)4917895;E-mail:tlee@https://www.doczj.com/doc/7a18532055.html,

ISSN0094-9655print;ISSN1563-5163online#2002Taylor&Francis Ltd

DOI:10.1080=0094965021000024035

648T.C.M.LEE

Stone(1997),Lee(2000),Pittman(1999)and Stone,Hansen,Kooperberg and Truong (1997).The second strategy is to use a relatively large number of knots,but do not use or-dinary least squares to estimate b.In contrast to the?rst strategy,for this second strategy the importance of the choice of knots is relatively minor:the crucial aspect is how b is estimated (e.g.,by penalized least squares).Recent related references include Denison,Mallick and Smith(1998a),DiMatteo,Genovese and Kass(2001),Eilers and Marx(1996),Lindstrom (1999),Ruppert and Carroll(2000),Smith and Kohn(1996).

This article focuses on the?rst strategy.Many regression spline smoothing procedures adopting this strategy are composed of two major components.The?rst component concerns the use of some sort of statistical model selection principle for de?ning a‘‘theoretically best’’set of knots.Quite often,such a‘‘theoretically best’’set of knots is de?ned implicitly as the optimizer of some objective function.The second component is hence a practical algorithm for performing the corresponding optimization.Typically this optimization is a very hard pro-blem,as(i)the search space is usually huge and(ii)different candidate solutions may have different dimensions.The main purpose of this paper is to provide a study for the perfor-mances of some common algorithms that are designed for carrying out such optimization problems.Both the univariate and bivariate settings will be considered(but the question of which is the most appropriate principle for de?ning a‘‘theoretically best’’set of knots will not be considered here).Our hope is that,by separating the two issues of‘‘de?ning the best’’and‘‘locating the de?ned best’’,and that by performing a focused study on the latter one,useful computational hints can be obtained for reference by future researchers.

Due to the complicated nature of the regression spline optimization algorithms,theoretical comparison seems to be very dif?cult.Therefore,the study to be presented is entirely based on empirical experiments.Of course it is impossible to exhaust all possible experimental set-tings,but we shall follow Wand(2000)to use a family approach to alleviate this problem. The idea is to change one experimental factor(e.g.,signal-to-noise ratio)at a time so that patterns can be more easily detected.

In(1)it is clear that fexTis a linear combination of f x j g r j?0and fexàk jTrtg m j?1.This set of functions is known as the truncated power basis of degree r.Other basis functions for regres-sion spline?tting also exist,such as those for B-splines,natural splines and radial basis func-tions(e.g.,see Eilers and Marx,1996;Green and Silverman,1994).However,as pointed out by Wand(2000),numerical experimental results should not be very sensitive to the choice of basis functions.Therefore for simplicity this article shall concentrate on the truncated power basis.

The rest of this article is organized as follows.In Section2further background details on univariate regression spline smoothing and the use of generalized cross-validation(GCV)for de?ning a‘‘best’’estimate will be provided.Then Sections3and4describe six different optimization algorithms.These six algorithms will be,in Section5,compared through a simulation study.Finally Section6considers the bivariate setting.Conclusions and recom-mendations for the univariate and the bivariate cases are reported in Sections5.5and6.3 respectively.

2REGRESSION SPLINE SMOOTHING USING GCV

Suppose that n pairs of measurements f x i;y i g n i?1satisfying

y i?fex iTte i;e i$iid Ne0;s2T;

are observed.The goal is to estimate f which is assumed to satisfy(1).In this article it is assumed r?3and minex iT

GCVe^hT?1=n

P n

i?1

f y ià^fex iTg2

f1àdemT=n g2

:e2T

Here demTis an increasing function of the number of the knots m.In order to penalize the additional?exibility inherited by the free choice of knot locations,Friedman and Silverman (1989)suggested using demT?3mt1instead of the conventional GCV choice demT?mt1.In the sequel this GCV choice of^h,with demT?3mt1,will be taken as the target that the optimization algorithms should aim at.

Let x?ex1;...;x nTT,y?ey1;...;y nTT and^k?e^k1;...;^k^mTT be an estimate of k. Denote the‘‘design matrix’’as X?e1;x;...;x r;exà^k11Trt;...;exà^k^m1TrtT,where1is a n?1vector of ones.If r and^k are speci?ed beforehand,then the unique maximum like-lihood estimate^b of b(conditional on r and^k)can be obtained by applying ordinary least squares regression,and admits the closed form expression^b?eX T XTà1X T y.This means that^h?f^k;^b g is completely determined by^k.Therefore the only effective argument for the minimization of GCVe^hT(or any other similar criteria)is k;i.e.,the knots.In the next two sections two classes of knot-based optimization algorithms will be described.Their ef-fectiveness,in terms of minimizing GCVe^hT,will be studied in Section5via simulations. Besides GCV,other model selection principles that have also been applied to derive various‘‘best’’knot sets include Akaike’s information criterion(AIC)(e.g.,Koo,1997; Kooperberg et al.,1997)and the minimum description length(MDL)principle(e.g.,Lee, 2000).Some preliminary numerical experiments were also conducted for both AIC and MDL.Empirical conclusions obtained from these experiments are similar to those for GCV.Due to space limitation,results of these experiments are not reported here.

3STEPWISE KNOT SELECTION

The most popular method for searching the minimizer of GCVe^hT(or any other similar criter-ia)seems to be stepwise knot selection(e.g.,see Friedman,1991;Friedman and Silverman, 1989;Hansen,Kooperberg and Sardy,1998;Koo,1997;Kooperberg et al.,1997;Lee,2000 and references given therein).The idea is very similar to stepwise regression for the classical subset selection problem.It begins with an initial model as the current model.Then at each time step a new model is obtained by either adding a new knot to or removing an existing knot from the current model.This process continues until a certain stopping criterion is met.Amongst all the candidate models that have been visited by the algorithm,the one that gives the smallest value of GCVe^hTis chosen as the?nal model.In this article the

LEAST SQUARES REGRESSION SPLINE FITTING649

650T.C.M.LEE

following four versions of this stepwise method are considered.A comparison of the relative computational speeds amongst these versions is given in Section5.5.

1.Forward Addition(ForAdd):Set the initial model as the model with no knots and com-pute its GCVe^hTvalue.Add a new knot to the current model at each time step.The knot is chosen in such a way that,when it is added,it produces the largest reduction(or smallest increase)in the current value of GCVe^hT.Continue this knot addition process until the num-ber of knots added hits a pre-selected limit.Throughout our simulation study reported below, this pre-selected limit was set to n=3.Finally,when the knot-adding process?nishes,a nested sequence of candidate models is produced and the one that minimizes GCVe^hTis selected as the?nal model.

2.Backward Elimination(BackElim):This version begins with placing a relatively large number of knots in the initial model.One typical strategy for placing these knots is to place a knot at every s(usually3s5)sorted values of the design points x i’s.In our si-mulation study we used s?

3.Then the algorithm proceeds to remove one knot at a time, until there are no more knots to be removed.At each time step the knot to be removed is chosen in such a way that,when it is removed,it provides the largest reduction(or smallest increase)in the current value of GCVe^hT.Similar to ForAdd,at the end of the process a nested sequence of candidate models is obtained.Select the one that gives the smallest GCVe^hTas the?nal model.

3.Addition followed by Elimination(AddElim):This version uses the?nal model selected by a?rst application of ForAdd as the initial model for the execution of BackElim.The resulting model obtained from such an execution of BackElim is taken as the?nal model.

4.Elimination followed by Addition(ElimAdd):This version uses the?nal model selected by a?rst application of BackElim as the initial model for the execution of ForAdd.The resulting model obtained from such an execution of ForAdd is taken as the?nal model.

4GENETIC ALGORITHMS

Another class of optimization algorithms that have been applied to regression spline smooth-ing is genetic algorithms;e.g.,see Lee(2002),Pittman(1999),Pittman and Murthy(2000) and references given therein.Below we begin with a brief description of genetic algorithms. As we shall see,an important issue in applying genetic algorithms is how to represent a can-didate model as a chromosome.Two different chromosome representation methods will be described and compared.For general introductions to genetic algorithms,see for examples Davis(1991),Fogel(2000)and Michalewicz(1996).

4.1General Description

The use of genetic algorithms for solving optimization problems can be brie?y described as follows.An initial set,or population,of possible solutions to an optimization problem is obtained and represented in vector form.Typically these vectors are of the same length and are often called chromosomes.They are free to‘‘evolve’’in the following way.Firstly parent chromosomes are randomly chosen from the initial population:chromosomes having lower or higher values of the objective criterion to be minimized or maximized,respectively, would have a higher chance of being chosen.Offspring are then reproduced from either applying a crossover or a mutation operation to these chosen parents.Once a suf?cient num-ber of such second generation offspring are produced,third generation offspring are further produced from these second generation offspring in a similar manner as before.This

LEAST SQUARES REGRESSION SPLINE FITTING651 reproduction process continues for a number of generations.If one believes in Darwin’s Nat-ural Selection,the expectation is that the objective criterion values of the offspring should gradually improve over generations;i.e.,approaching the optimal value.For the current pro-blem,the objective function is GCVe^hTand one chromosome represents one^h.

In a crossover operation one child chromosome is reproduced from‘‘mixing’’two parent chromosomes.The aim is to allow the possibility that the child would receive different best parts from its parents.A typical‘‘mixing’’strategy is that every child gene location would have equal chances of either receiving the corresponding father gene or the corresponding mother gene.This crossover operation is the distinct feature that makes genetic algorithms different from other optimization methods.

In a mutation operation one child chromosome is reproduced from one parent chromo-some.The child would essentially be the same as its parent except for a small number of genes where randomness is introduced to alter the types of these genes.Such a mutation op-eration prevents the algorithm being trapped in local optima.

For the reason of preserving the best chromosome of a current generation,an additional step that one may perform is the elitist step:replace the worst chromosome of the next gen-eration with the best chromosome of the current generation.Inclusion of this elitist step would guarantee the monotonicity of the algorithm.

4.2Chromosome Representations

This section describes two methods for representing a^h in a chromosome form:the?rst method is described in Lee(2002),while the second method can be found in Pittman (1999).First recall that for the current curve?tting problem a possible solution^h can be uni-quely speci?ed by^k,and that^k is assumed to be a subset of the design points f x1;...;x n g. Thus for the present problem a chromosome only needs to carry information about^k.

1.Fixed-Length Representation(GeneFix):In this representation method all chromosomes are binary vectors with the same length n,the number of data points.A simple example will be used to illustrate its idea.Suppose n?15and^k?f x3;x8;x14g;i.e.,there are three knots in this candidate model and they are located at x3;x8and x14.If we use‘‘0’’to denote a nor-mal gene and‘‘1’’to denote a knot gene,then the chromosome for this example is 001000010000010.One advantage of this method is that,it can be easily extended to handle cases when outliers and/or discontinuities are allowed:simply introduces two additional types of genes,outlier genes and discontinuity genes.

2.Variable-Length Representation(GeneV ar):For this method the chromosomes are not binary nor having the same length.Here the location of a knot is represented by one integer-valued gene,and hence the length of a chromosome is equal to the number of knots in the candidate model.For the previous example,the corresponding chromosome is 3-8-14(the hyphens were merely used to separate the genes).Since the chromosomes are generally not of the same length,the optimization is done in the following way.First pre-specify the minimum and the maximum number of knots that any candidate model can have.Denote them as K MIN and K MAX respectively.Then for each K?K MIN;...;K MAX,apply the algo-rithm to?nd the best candidate model amongst only those candidate models that have K knots.That is,for this particular run of the algorithm,all chromosomes are restricted to have the same length K.Then,after the execution of the algorithm for every value of K,a sequence of K MAXàK MINt1models is obtained.The one that minimizes GCVe^hTwill be chosen as the?nal model.Please consult Lee(2002)and Pittman(1999)for further details on the implementations of these algorithms.

5SIMULATION STUDY

This section presents results of a series of numerical experiments which were conducted to evaluate the performances of the various optimization algorithms (four stepwise and two genetic)described above.These experiments were designed to study the effects of varying the (i)noise level,(ii)design density,(iii)noise variance function,and (iv)degree of spatial variation.

The simulation was conducted in the following way.For each of the experimental setups described below,100arti ?cial noisy data sets,each with 200design points x i ,were generated.Then,for each of these 100data sets,the above six algorithms were applied to minimize GCV e^h Tand the corresponding ^f is obtained.For each obtained ^f ,both the GCV value and the mean-squared error (MSE)value,de ?ned as 1=n P i f f ex i Tà^f ex i Tg 2,are computed and recorded.Paired Wilcoxon tests were then applied to test if the difference between the median GCV (and MSE)values of any two algorithms is signi ?cant or not.The signi ?cance level used was 5=6%?0:83%.If the median GCV (or MSE)value of an algorithm is sig-ni ?cantly less than the remaining ?ve,it will be assigned a GCV (or MSE)rank 1.If the median GCV (or MSE)value of an algorithm is signi ?cantly larger than one but less than four algorithm,it will be assigned a GCV (or MSE)rank 2,and similarly for ranks 3to

6.Algorithms having non-signi ?cantly different median values will share the same averaged rank.Ranking the algorithms in this manner provides an indicator about the relative merits of the methods (see Wand,2000).Since the main interest of this article is to compare the algo-rithms in terms of their abilities for conducting numerical minimization,GCV seems to be a more appropriate performance measure here than MSE.

5.1Varying Noise Level

For this ?rst experiment four test functions were used.They are given in Table I and are also plotted in Figure 1.These test functions possess different characteristics and were also used by many previous authors.

The data ex i ;y i Twere generated using y i ?f ex i Tte i ,where f is a test function,x i is drawn from Unif[0,1],and e i is a zero-mean Gaussian error with variance s 2.Three signal-to-noise ratios (SNRs)were used:SNR ?2,4and 6,where SNR is de ?ned as k f k =s .Boxplots of the GCV and log(MSE)values for the six algorithms,together with their Wilcoxon test rankings,are given in Figures 2and 3.

5.2Varying Design Density

The same four test functions as in the V arying Noise Level experiment were used.The data ex i ;y i Twere also generated from y i ?f ex i Tte i with s ?k f k =4(i.e.,SNR ?4),but now the x i ’s were drawn from three different densities.The three densities are Beta(1.2,1.8),

TABLE I Formulae for Test Functions.

Test Function 1:

f (x )?(4x 72)t2exp{à16(4x 72)2},x 2[0,1]Test Function 2:

f (x )?sin 3(2p x 3),x 2[0,1]Test Function 3:

f ex T?4x 2e3à4x T;x 2?0;0:5T43x e4x 2à10x t7Tà32;x 2?0:5;0:75T16x ex à1T2;

x 2?0:75;1 8<:Test Function 4:f (x )?sin (8p x ),x 2[0,1]

652T.C.M.LEE

Beta(1.5,1.5)and Beta(1.8,1.2),and their probability density functions are plotted in Figure

4.Boxplots of the GCV and log(MSE)values,and Wilcoxon test rankings of the algorithms are displayed in Figures 5and 6in a similar manner as before.

5.3Varying Noise Variance Function

Again,the same four test functions as in the V arying Noise Level experiment were used,but the variance of the Gaussian noise was not the same for all values of x i .Rather,the variance was speci ?ed by a variance function v ex T,and the data ex i ;y i Twere generated

from FIGURE 1Four test

functions.

FIGURE 2Boxplots of the GCV values for the ‘‘Varying Noise Level ’’experiment.In each panel the boxplots correspond respectively to,from left to right,ForAdd ,BackElim ,AddElim ,ElimAdd ,GeneFix and GeneV ar .The number below each boxplot is the Wilcoxon test ranking.

LEAST SQUARES REGRESSION SPLINE FITTING 653

y i ?f ex i Ttv ex i Te i ,where s ?k f k =4and the x i ’s were drawn from Unif[0,1].The following three variance functions v ex Twere used:

Variance Function 1

v ex T?0:5tx ;x 2?0;1 ;Variance Function 2

v ex T?1:3à1:2x x 2?0;0:5T;0:2t1:2x x 2?0:5;1 ;(Variance Function 3v ex T?1:5àx ;x 2?0;1

:

FIGURE 3Similar to Figure 2but for

log(MSE).

FIGURE 4Plots of the three different design densities.

654T.C.M.LEE

These variance functions are plotted in Figure7.Boxplots of the GCV and log(MSE)values, together with the Wilcoxon test rankings are given in Figures8and9in a similar manner as before.

5.4Varying Spatial Variation

In this experiment the six test functions were taken from Wand(2000),all have different de-grees of spatial variation.They are indexed by a single integer parameter j,and have the form

f jexT?

????????????????

xe1àxT

p

sin

2p f1t2e9à4jT=5g

xt2

;j?1;...;6

: FIGURE7Plots of the noise variance

functions.

Note that it is of the same structural form of the Doppler function introduced by Donoho and Johnstone(1994).

The dataex i;y iTwere generated from y i?f jex iTte i with s?k f j k=4and the x i’s drawn from Unif[0,1].The test functions,together with typical simulated data sets,are plotted in Figure10.In a similar fashion as before,boxplots of GCV and log(MSE)values,and Wilcoxon test rankings of the algorithms are displayed in Figures11and12.

5.5Empirical Conclusions and Recommendations

The six algorithms gave fairly consistent performances for the above different experimental settings.The averaged Wilcoxon GCV and MSE test rankings are given in Tables II and III respectively.Judging from the overall averaged rankings,it seems that the two genetic algorithms are superior to the stepwise procedures,especially in terms of minimizing GCVe^hT.

The computation times taken for the stepwise procedures to?nish one run under various settings were reasonably constant.The typical running times on a Sun Ultra-60Work-station for ForAdd,BackElim,AddElim and ElimAdd were respectively15s,38s,15s and53s.These timings are best to be served as upper bounds,as we did not optimize

the codes in our implementation.For the genetic algorithms,the execution times were

quite variable:for GeneFix it ranged from 50s to 70s,while for GeneV ar it ranged from 50s to 100s.Therefore,if computation time is not an issue,then one should perhaps use the genetic algorithms.However,if time is an important issue,then AddElim seems to be a good

compromise.

FIGURE 10Plots of the test functions,together with typical simulated data sets,for the V arying Spatial V ariation

experiment.

FIGURE 11Similar to Figure 2but for the V arying Spatial V ariation experiment.

658T.C.M.LEE

One last interesting observation is that,for some settings the GCV and MSE values are not linearly related;i.e.,a ^h that has a small GCV value does not guarantee to have a small MSE value,and vice versa.This may suggest that GCV e^h Tis not the best criterion if the goal is to obtain the ^h

that minimizes

MSE.TABLE III Similar to Table II but for the Wilcoxon MSE Test Rankings.

Algorithm

NoiseL DesignD V arFn SpaV ar Overall ForAdd

3.33 3.21 3.08 2.50 3.03BackElim

4.96

5.13 5.21 5.50 5.20AddElim

4.08 3.50 3.88 2.92 3.60ElimAdd

4.25 4.03 4.54 4.33 4.29GeneFix

2.21 2.29 2.29 2.25 2.26GeneV ar 2.17 2.83 2.00

3.50 2.63

TABLE II Average Wilcoxon GCV Test Rankings for the Four Univariate

Experimental Settings:Noise Level (NoiseL),Design Density (DesignD),Variance

Function (VarFn)and Spatial Variation (SpaVar).

Algorithm

NoiseL DesignD V arFn SpaV ar Overall ForAdd

6.00 5.96 6.00 4.67 5.66BackElim

4.50 4.54 4.50

5.17 4.68AddElim

3.84 3.62 3.71 2.83 3.50ElimAdd

3.33 3.21 3.33 3.92 3.45GeneFix

1.71 1.88 1.88 1.42 1.72GeneV ar 1.63 1.79 1.59 3.00

2.00

LEAST SQUARES REGRESSION SPLINE FITTING 659

6BIV ARIATE SMOOTHING

This section considers bivariate smoothing.Due to space limitation,the description will be kept minimal.Important references include Friedman(1991)and Kooperberg et al.(1997).

6.1Background

The data f y i;x1i;x2i g n i?1are now assumed to satisfy

y i?fex1i;x2iTte i;e i$iid Ne0;s2T;e3Twhere f is the bivariate‘‘true’’surface to be recovered.It is assumed that f can be modeled by

fex1;x2T?X

b j B jex1;x2T;

where the basis functions B jex1;x2T’s are of the form1;x1;x2,ex1àk1uTt;ex2àk2vTt;x1x2, x2ex1àk1uTt;x1ex2àk2vTtandex1àk1uTtex2àk2vTt.Also,the knots are restricted to be a subset of the marginal values of the design pointsex1i;x2iT.In our simulation a bivariate ver-sion of GCVehTis used to de?ne a‘‘best’’^f.

Driven by the univariate simulation results,two algorithms for minimizing the GCV func-tion are investigated:stepwise knot addition followed by elimination and genetic algorithms with?xed-length chromosomes.These two algorithms are simple straightforward extensions of their univariate counterparts.In fact the stepwise procedure to be compared in our simula-tion below was taken from the POL YMARS package mainly developed by Charles Kooperberg (see the unpublished manuscript Kooperberg and O’Connor n.d.).Note that in POL YMARS a‘‘no interactions if no main effects’’constraint is placed on all the possible candidate mod-els.The same constraint was also imposed for the genetic algorithm.

6.2Simulation

A simulation study was conducted.Although it was done at a smaller scale when comparing to the univariate setting,we believe that useful empirical conclusions can still be drawn.Five bivariate test functions were used.They are listed in Table IV and are plotted in Figure13. These functions have been used by for example Denison,Mallick and Smith(1998b)and Hwang,Lay,Maechler,Martin and Schimert(1994),and were constructed to have a unit standard deviation and a non-negative range.The data were generated according to(3), with the design points drawn from Unif?0;1 2.The number of design points was100,and three SNRs were used:2,4and6.The number of replicates was100.

TABLE IV Five Test Functions for the Bivariate Setting.

Test Function1:fex1;x2T?10:391fex1à0:4Tex2à0:6Tt0:36g

Test Function2:fex1;x2T?24:234f r2e0:75àr2Tg;r2?ex1à0:5T2tex2à0:5T2

Test Function3:fex1;x2T?42:659f0:1t~x1e0:05t~x41à10~x21~x22t5~x42Tg;~x1?x1à0:5;~x2?x2à0:5 Test Function4:fex1;x2T?1:3356?1:5e1àx1Tte2x1à1sin f3pex1à0:6T2gte3ex2à0:5Tsin f4pex2à0:9T2g Test Function5:fex1;x2T?1:9?1:35te x1sin f13ex1à0:6T2g eàx2sine7x2T

660T.C.M.LEE

FIGURE 14Boxplots of GCV values for the bivariate smoothing experiment.Numbers in parentheses are Wilcoxon test rankings.

LEAST SQUARES REGRESSION SPLINE FITTING 661

For each simulated data set,the two algorithms were applied to minimize the GCV func-tion and obtain the corresponding^f.As for the univariate case,both the GCV and MSE va-lues were computed.The MSE values were computed over a grid of25?25grid points. Boxplots of the GCV and log(MSE)values,together with the Wilcoxon test rankings,are provided in Figures14and15.Typically it took less than5s for the POL YMARS stepwise procedure to?nish,while for the genetic algorithm the computation times ranged from50s to300s.

6.3Results and Some Suggestions

In terms of minimizing the GCV function,the stepwise procedure performed better for Test Function1,while the genetic algorithm performed better for the remaining four test func-tions.However,both procedures gave similar performances in terms of MSE.It seems to sug-gest that,when the‘‘true’’surface is simple in structure(such as Test Function1),the greedy nature of the stepwise procedure can reliably locate good intermediate search directions dur-ing the minimization of GCV.However,when the‘‘true’’surface is more complicated,the stepwise procedure may fail to do so,and one may need to switch to the computationally-very-expensive genetic algorithm.

Acknowledgement

The author would like to thank one referee for his/her constructive comments.

LEAST SQUARES REGRESSION SPLINE FITTING663 References

Davis,L.(1991)Handbook of Genetic Algorithms,New Y ork,Van Nostrand Reinhold.

Denison,D.G.T.,Mallick,B.K.and Smith,A.F.M.(1998a)Automatic bayesian curve?tting,Journal of the Royal Statistical Society Series B,60,333–350.

Denison,D.G.T.,Mallick,B.K.and Smith,A.F.M.(1998b)Bayesian MARS,Statistics and Computing,8, 337–346.

DiMatteo,I.,Genovese,C.R.and Kass,R.E.(2001)Bayesian curve?tting with free-knot splines,Biometrika,88, 1055–1071.

Donoho,D.L.and Johnstone,I.M.(1994)Ideal spatial adaptation by wavelet shrinkage,Biometrika,81,425–455. Eilers,P.H.C.and Marx,B.D.(1996)Flexible parsimonious smoothing and additive modeling(with discussion), Statistical Science,89,89–121.

Fogel,D.B.(2000)Evolutionary computing,IEEE Spectrum,pp.26–32.

Friedman,J.H.(1991)Multivariate adaptive regression splines(with discussion),The Annals of Statistics,19,1–141. Friedman,J.H.and Silverman,B.W.(1989)Flexible parsimonious smoothing and additive modeling(with discussion),Technometrics,31,3–21.

Green,P.J.and Silverman,B.W.(1994)Non Parametric Regression and Generalized Linear Models,London, Chapman and Hall.

Hansen,M.H.,Kooperberg,C.and Sardy,S.(1998)Triogram models,Journal of the American Statistical Association,93,101–119.

Hwang,J.-N.,Lay,S.-R.,Maechler,M.,Martin,R.D.and Schimert,J.(1994)Regression modeling in back-propagation and projection pursuit learning,IEEE Transactions on Neural Networks,5,342–353.

Koo,J.-Y.(1997)Spline estimation of discontinuous regression functions,Journal of Computational and Graphical Statistics,6,266–284.

Kooperberg,C.and O’Connor,M.(n.d.)POL YMARS(unpublished manuscript).

Kooperberg,C.,Bose,S.and Stone,C.J.(1997)Polychotomous regression,Journal of the American Statistical Association,92,117–127.

Lee,T.C.M.(2000)Regression spline smoothing using the minimum description length principle,Statistics and Probability Letters,48,71–82.

Lee,T.C.M.(2002)Automatic smoothing for discontinuous regression functions,Statistica Sinica(to appear). Lindstrom,M.J.(1999)Penalized estimation of free-knot splines,Journal of Computational and Graphical Statistics,8,333–352.

Michalewicz,Z.(1996)Genetic AlgorithmstData Structures?Evolution Programs,3rd revised and extended ed.Berlin,Heidelberg,Springer-Verlag.

Pittman,J.(1999)Adaptive splines and genetic algorithms,Journal of Computational and Graphical Statistics(to appear).

Pittman,J.and Murthy,C.(2000)Fitting optimal piecewise linear functions using genetic algorithms,IEEE Transactions on Pattern Analysis and Machine Intelligence,22,701–718.

Ruppert,D.and Carroll,R.J.(2000)Spatially-adaptive penalties for spline?tting,Australian and New Zealand Journal of Statistics,42,205–223.

Smith,M.and Kohn,R.(1996)Nonparametric regression using Bayesian variable selection,J.Econometrics,75, 317–344.

Stone,C.J.,Hansen,M.,Kooperberg,C.and Truong,Y.K.(1997)Polynomial splines and their tensor products in extended linear modeling(with discussion),The Annals of Statistics,25,1371–1470.

Wand,M.P.(2000)A comparison of regression spline smoothing procedures,Computational Statistics,15, 443–462.

我发现了筛法的计算公式(最后稿)

我发现了筛法的计算公式 孟庆馀［江苏连云港］ 2010年5月 [摘要]： 笔者在探索中，发现了有关素数与合数关系的三条主要规律： １、区段（区域）性的规律。 ２、逐项相除四舍五入的规律。 ３、随从数的规律。 根据这三条规律推导出一个公式, 它可以计算出任一已知素数后边紧跟的那个素数和任意大的一个自然数之前共有多少个素数的问题。 这个公式是： m p = 2N -N [ (211p p +311p p -3211p p p ±…±13211-n p p p p Λ)+ （ )1111132131211-±±++-n p p p p p p p p p ΛΛ（-n p 1）]+（1-n ） [关键词]： 筛法公式、逐项相除、四舍五入、区段、随从数。 [正文]： 笔者在多年的探索中，发现了有关素数与合数关系的一些规律，根据这些规律找到了一个可以对埃拉多斯染尼氏（Eratosthenes ）筛法进行计算的公式，即“筛法计算公式”(它包括计算素数和计算奇合数两个公式)，计算素数的公式也可以称为“素数公式"。给素数找出一个通项表达式，即已知任一素数后边紧跟的那个素数的公式，这是一个缠绕着数学家的世界难题，时至今日都没有解决。笔者的这个公式能较好地解决任一已知素数后边紧跟的那个素数的问题。 一、“筛法计算公式”(用于计算素数) m p = 2N -N [ (211p p +311p p -3211p p p ±…±13211-n p p p p Λ)+ （)1111132131211-±±++-n p p p p p p p p p ΛΛ（-n p 1）]+（1-n ） …（1） 式中m p 为1~N 数列中素数个数；N 为任意大的自然数（2n p ≤N <21+n p ） ；n p p p p ,,,,321K 为素数，其中：1p = 2，2p = 3，3p = 5，…,6p = 13，…；n ≥2 。

简单易学的两种还原魔方的口诀及公式图解详解

图解简单易学的两种还原魔方的常用口诀公式 前言 我们常见的魔方是3x3x3的三阶魔方，英文名Rubik's cube。是一个正6 面体，有6种颜色，由26块组成，有8个角块；12个棱块；6个中心块（和中心轴支架相连）见下图： （图1） 学习魔方首先就要搞清它的以上结构，知道角块只能和角块换位，棱块只能和棱块换位，中心块不能移动。 魔方的标准色： 国际魔方标准色为：上黄－下白，前蓝－后绿，左橙－右红。 （见图2）注：（这里以白色为底面，因为以后的教程都将以白色为底面， 为了方便教学，请都统一以白色为准）。 （图 2）

认识公式 （图3）（图4）公式说明：实际上就是以上下左右前后的英文的单词的头一个大写字母表示 （图5）

（图6） （图7）

（图8） 三阶魔方入门玩法教程（一） 步骤一、完成一层 首先要做的是区分一层和一面：很多初学者对于“一面”与“一层”缺乏清楚的认识，所以在这里特别解释一下。所谓一层,就是在完成一面(如图2的白色面)的基础上,白色面的四条边,每条边的侧面只有一种颜色,图(2). 如图（1）中心块是蓝色，则它所在面的角和棱全都是蓝色，是图(2)的反方向 图（3）和（4）则是仅仅是一面的状态,而不是一层! （1）（2） （3）（4） 注：图（2）和（4）分别是图（1）和（3）的底面状态 想完成魔方，基础是最重要的，就像建筑一样，魔方也如此，基础是最重要的。

由于上文提到过中心块的固定性，这一性质，在魔方上实质起着定位的作用，简单的说就是中心块的颜色就代表它所在的面的颜色。 一、十字（就是快速法中的CROSS ） 第一种情况如图所示： 公式为R2 第二种情况如图所示： （白色下面颜色为橙色，为方便观察，特意翻出颜色） 橙白块要移到上右的位置，现在橙白块在目标位置的下面。但其橙色片没有和橙色的中心块贴在 一起。为此我们先做D’ F’ 即把橙色粘在一起，接着 R 还原到顶层,， F 是把蓝白橙还原到正确的位置(上面的F’ 使蓝白块向左移了九十度)。 公式为D’ F’ R F 图解： 当然，架十字不只只有上面两种情况，现我们在分析下其它的一些情况吧！ 如下图： 橙白块的位置己对好，但颜色反了，我就先做R2化成第二种情况，然后用还原第二种情况的 （橙色下面颜色为白色，为方便观察，特意翻出颜色）

sap query的使用

SAP中QUERY的介绍和制作 研发二部SAP科林如意 QUERY是SAP的一项简单的报表制作工具，它可以为没有编程基础的用户用来生成简单的查询报表。QUERY有图形化的界面，你可以在上面托托拽拽，然后就可以见到你想要的报表了，但是实际上它跟ABAP开发报表没有实质的区别，也是基于代码的，只是系统在你操作的基础上已经自动为你生成了代码。同时在SAP QUERY中还允许添加ABAP代码，当存在附加表和附加字段时尤其重要。总的来说，QUERY作为查询工具已经相当完善，足以满足用户一般的查询和统计了。 QUERY的制作步骤很简单，主要有3步。 1、创建功能区（Functional area），也就是所谓的信息集，T_CODE为SQ02； 2、创建用户组，并分配用户和功能区，T_CODE为SQ03； 3、创建SAP QUERY,T_CODE为SQ01。 功能区（Functional area）中定义了QUERY中需引用的表和字段，是报表显示的数据源。创建了一个功能区之后，要把功能区分配给相应的用户组，这样该用户组中的用户才能访问该功能区。 1、创建功能区（信息集） 信息集是数据集的特定视图，根据用户的需求，数据集可以来自一张表或多表连接或逻辑数据库（如下图）。 从sq02进入上图界面。在界面上可以看到上图中红线圈出的两个地方。查询范围是指所制作的QUERY所能应用的范围，有标准区域和全局区域两种。标准区域表示QUERY 只能在特定的client使用，不能跨client；全局是指该QUERY是跨多个client的。 标准区域的QUERY如果要在别的client使用的话，需要通过传输（图上的那个小汽车按钮）。查询范围可以通过上图菜单中的环境选项中查询区域来设置。区域设置完成后点击‘创建’就进如了信息集的新建界面（如下图）。

素数普遍公式

素数普遍公式 目录[隐藏] 一、引言 二、素数普遍公式 三、素数的个数 四、公式的用途 五、素数普遍公式在认识形成中的作用和意义 思考题 一、引言 二、素数普遍公式 三、素数的个数 四、公式的用途 五、素数普遍公式在认识形成中的作用和意义 思考题 [编辑本段] 一、引言 2000多年前欧几里德在证明素数无穷多时就埋下了寻求素数普遍公式的伏笔 素数普遍公式 ，以布劳维尔为首的直觉主义学派认为：“你没有给出第n个素数是如何构造的，就不能算是好的证明”。2000多年来，数论学最重要的一个任务，就是寻找素数普遍公式，为此，一代又一代数学精英，耗费了巨大的心血，始终未获成功。黎曼曾想用他的ζ函数数的“零点”来逼近素数普遍公式，至今未获成功。也有人反向思考，用素数普遍公式逼近“零点”来解决黎曼猜想。希尔伯特在1900年的国际数学家大会上说：对黎曼公式进行了彻底讨论之后，或许就能够严格解决哥德巴赫问题和孪生素数问题。实际在哲学上，只要有一个明确的定义，就应该有一个公式。 [编辑本段] 二、素数普遍公式

公元前250年同样是古希腊的数学家埃拉托塞尼提出一种筛法： （一）“要得到不大于某个自然数N的所有素数，只要在2---N中将不大于√N的素数的倍数全部划去即可”。 （二）将上面的内容等价转换：“如果N是合数，则它有一个因子d满足1

魔方快速还原方法-增加图案魔方的方法

魔方的还原方法 第一步:先选定一个中心块颜色作为底层,然后将底层四个边块和四个角块向上，也就是我们通常说的转一面。具体方法略。 第二步:所有的色块都变成一面后，我们需要调整底面的角块和边块，实现 完成第二步后，我们就会得到这样的效果

接下来就要开始学习公式还原了。在开始之前先了解一下魔方复原的术语。 首先要知道3×3×3 魔方的 6 个面的相对叫法和英文缩写: 如图示:前--Front (F),后--Back(B),左--Left(L),右--Right (R),上--Up (U),下-- Down(D). 注:各个面的叫法是根据它们对你的方向所定的,不是根据颜色! 我们还要把这26 块分类: 1) 中心块----六个面的中心就叫中心块(只有一种颜色) 2) 边块----和中心块相邻的由两种颜色组成的块 3) 角块----8 个在角上由三种颜色组成的块

注:a)不管怎样旋转魔方,中心块的位置是不会变的 b)旋转魔方时,边块和角块都会移动,但边块不会移动到角块的位置,同样角块也不会移动到边块的位置!!(这里我们就会想到复原魔方的基本思想就是把角块和边块移动到它"该到的"位置上!!!!) 这里还要理解复原魔方的又一思想----我们是按层的思想复原魔方的,显而易见 3×3×3 魔方分了 3 层---- 上层; 中层; 底层.换句话说就是先复原上面或下面,然后把这层作为底层,然后复原中层,最后是上层!!!! 然后要理解拧法,在本篇文章里归纳起来一共有 3 种法: 1)顺时针旋转(90 度) 2)逆时针旋转(90 度) 3)半圈旋转(180 度) 表示方法: a)顺时针一般不用符号标识 b)逆时针--(') c)半圈--(2 或") 举例: R 顺时针直角旋转右面； U' 逆时针直角旋转上面； F" 旋转前面 180 度 好!理解了以上所讲的内容后我们就可以开始复原魔方了!!!! 第三步:前两步已经把上层复原,这时把魔方颠倒一下,即底层全部复原.所以第三步的目的就是使中层四个边块复位.先在上层找一个应该去中层的边块,然后转动上面,使该边块的侧面与同色的侧面中心块对齐, 然后看符合图 3 还是图 4的情况 , 如果是图 3 做 URU'R'U'F'UF, 如果是图 4 做 U'F'UFURU'R',这样原来在上层的边块就可以复原了. 如果要复原的中层边块就在中层,则应先随便取一个上层边块用图 3 或图 4 的方法去占据要复位的边块所在的位置,使它到上层来再用前面的方法使它复位. 第三步做完后魔方就是这样的了

SAP query操作手册

基本概念 QUERY是SAP的一项简单报表工具，它可为没有编程基础的用户用来生成简单的报表。它有图形化的界面，你可在上面托托拽拽，然后就可以见到你要的报表，可是这只是简单的应用，其实每个工具功能都是比较完善的，QUERY也不例外。 1．生成用户组 SAP菜单→工具→ABAP工作台→实用程序→SAP查询→用户组 T-Code：SQ03 2。创建Functional area（功能区） SAP菜单→工具→ABAP工作台→实用程序→SAP查询→信息集 T-Code：SQ02 3。创建SAP Query SAP菜单→工具→ABAP工作台→实用程序→SAP查询→查询 T-Code：SQ01 2．这些组件之间的关系有： 1。Query的管理包括建立Functional area（功能区）和User Group（用户组），并将功能区分配到相应的用户组中去。 2。Functional area（功能区）中定义query中需引用的表和字段。 3。只有当一个用户属于至少一个用户组才可以创建、运行Queries。一个用户可以属于几个用户组。用户组中的用户享有相同的权力。 4。当Functional area（功能区）分配给了某用户组，该用户组的成员即可以访问此功能区。 5。一个Functional area（功能区）可以分配给多个用户组；多个Functional area（功能区）可以分配给一个用户组。 6。Queries通常为特定的用户组和特定的功能区而建立。这个用户组的用户可以访问所有分配给这个用户组的Queries。 3．还有一点值得注意，在QUERY的管理时，有这样的概念： 标准区（Standard Area）：建立在标准区的查询往往用以满足特定用户的特定需求，因此属于Client独立（client-specific）的查询。这些查询不会连接到SAP工作台组织器（Workbench Organizer）上。 全局区域（Global Area）：建立在全局区域的查询是为整个系统开发的，因此属于Client交叉（cross-client）的查询。这些查询会在SAP 工作台组织器（Workbench Organizer）上注册，可以利用正常的流程传输到其他系统中。 这里提到的标准区的INFOSET，就是指QUICKVIWER中的一个数据源InfoSet（信息集），而全局区域的InfoSet是不支持QUICKVIWER的。 操作步骤 1.建立用户组

魔方公式口诀图解教程

新魔方新手教程 前言 我们常见的魔方是3x3x3的三阶魔方，英文名Rubik's cube。是一个正6 面体，有6种颜色，由26块组成，有8个角块；12个棱块；6个中心块（和中心轴支架相连）见下图： （图1） 学习魔方首先就要搞清它的以上结构，知道角块只能和角块换位，棱块只能和棱块换位，中心块不能移动。 魔方的标准色： 国际魔方标准色为：上黄－下白，前蓝－后绿，左橙－右红。 （见图2）注：（这里以白色为底面，因为以后的教程都将以白色为底面， 为了方便教学，请都统一以白色为准）。 （图2）

认识公式 （图3）（图4）公式说明：实际上就是以上下左右前后的英文的单词的头一个大写字母表示 （图5）

（图6） （图7）

（图8） 步骤一、完成一层 首先要做的是区分一层和一面：很多初学者对于“一面”与“一层”缺乏清楚的认识，所以在这里特别解释一下。所谓一层,就是在完成一面(如图2的白色面)的基础上,白色面的四条边,每条边的侧面只有一种颜色,图(2). 如图（1）中心块是蓝色，则它所在面的角和棱全都是蓝色，是图(2)的反方向 图（3）和（4）则是仅仅是一面的状态,而不是一层! （1）（2） （3）（4） 注：图（2）和（4）分别是图（1）和（3）的底面状态 想完成魔方，基础是最重要的，就像建筑一样，魔方也如此，基础是最重要的。 由于上文提到过中心块的固定性，这一性质，在魔方上实质起着定位的作用，简单的说就是中心块的颜色就代表它所在的面的颜色。 一、十字（就是快速法中的CROSS）

第一种情况如图所示： （橙色下面颜色为白色，为方便观察，特意翻出颜色） 公式为R2 第二种情况如图所示： （白色下面颜色为橙色，为方便观察，特意翻出颜色） 橙白块要移到上右的位置，现在橙白块在目标位置的下面。但其橙色片没有和橙色的中心块贴在一起。为此我们先做D’F’即把橙色粘在一起，接着 R 还原到顶层,，F 是把蓝白橙还原到正确的位置(上面的F’使蓝白块向左移了九十度)。 公式为D’F’R F 图解： 当然，架十字不只只有上面两种情况，现我们在分析下其它的一些情况吧！ 如下图： 橙白块的位置己对好，但颜色反了，我就先做R2化成第二种情况，然后用还原第二种情况的公式即可！

SAP Query 操作手册

QUERY是SAP提供的方便无编程基础用户的报表工具，使用图形化的界面，让用户托托拽拽就能轻松完成报表编写。 Query的操作简单，包括建立用户组、建立信息集和建立查询报表，分别对应Tcode ：SQ01/SQ02/SQ03,下面以资产全息查询报表的建立介绍Query操作的完整理步骤。 一．建立Query用户组(Tcode:SQ03) 如上图,你可能为各个模块建立查询报表,这些报表和SAP Tcode一样需要进行权限控制。 [1].走菜单环境->查询区域可选择查询的工作区,标准区域表示特定client(译成客户真是有才),全局区域则表示该用户组是跨client端的,大家知道同一SAP Server可允许多个client存在，象标准的ABAP程序就是跨client的，SAP已经为各模块预制了很多跨Client的查询,资产查询比较多，此处选择特定client, 特定client查询不会连接到SAP工作台组织器（Workbench Organizer）,可使用程序RSAQR3TR进行传输。 [2].传输用户组，调用程序RSAQR3TR，也可以直接使用SE38执行RSAQR3TR传输,稍后详细介绍如何传输。 [3].建立用户组名为ZFICO。 [4].将用户组分配到SAP用户,比如将需要使用查询的财务关键用户和最终用户的SAP用户帐号分配到该用户组。 二．建立信息集(Tcode:SQ02)

信息集是数据集的特定视图,数据集主要来自多表连接或逻辑数据库,建立信息集如下图: [1].假设建立信息集ZFIAM001,建立信息集时,用户可自由选择基于表还是基于逻辑数据库,本例使用到资产相关表格ANLA,ANLB,ANLC,ANLU,ALNZ共5个表。 [2][3].按“角色/用户组分配”按钮将信息集分配到用户组ZFICO,你可将一个信息集分配给多个用户组，比如投资项目管理组用户也希望看到该资产查询。 到此，信息集->Query用户组->SAP用户就关联起来了。 介绍一下信息集的详细建立步骤，分abc三个步骤： a．添加信息集Table 新建信息集ZFIAM001的数据源选择“使用基础表进行表连接”,输入表ANLC,进入后到下图:

筛法求素数

筛法求素数 目录 基本思想 C语言实现 pascal实现: 1C++实现: 2python 实现: 基本思想 用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列，1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。如有： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 1不是素数，去掉。剩下的数中2最小，是素数，去掉2的倍数，余下的数是： 3 5 7 9 11 13 15 17 19 21 23 25 27 29 剩下的数中3最小，是素数，去掉3的倍数，如此下去直到所有的数都被筛完，求出的素数为： 2 3 5 7 11 13 17 19 23 29 C语言实现 1、算法一：令A为素数，则A*N（N>1;N为自然数）都不是素数。 #define range 2000 bool IsPrime[range+1]; //set函数确定i是否为素数，结果储存在IsPrime[i]中，此函数在DEV C++中测试通过 void set(bool IsPrime[]) { int i,j; for(i=0;i<=range;++i) IsPrime[i]=true; IsPrime[0]=IsPrime[1]=false; for(i=2;i<=range;++i) { if(IsPrime[i]) { for(j=2*i;j<=range;j+=i) IsPrime[j]=false; } } } 2、 说明：解决这个问题的诀窍是如何安排删除的次序，使得每一个非质数都只被删除一次。中学时学过一个因式分解定理，他说任何一个非质（合）数都可以分解成质数的连乘积。例如，16=4^2，18=2 * 3^2，691488=2^5 * 3^2 * 7^4等。如果把因式分解中最小质数写在最左边，有16=4^2，18=2*9,691488=2^5 * 21609,；换句话说，把合数N写成N=p^k * q，此时q当然是大于p的，因为p是因式分解中最小的质数。由于因式分解的唯一性，任何一个合数N，写成N=p^k * q;的方式也是唯一的。由于q>=p的关系，因此在删除非质数时，如果已知p是质数，可以先删除P^2,p^3,p^4,... ，再删除pq,p^2*q,p^3*q,...,（q是比p大而没有被删除的数），一直到pq>N为止。 因为每个非质数都只被删除一次，可想而知，这个程序的速度一定相当快。依据Gries与Misra的文章，线性的时间，也就是与N成正比的时间就足够了（此时要找出2N的质数）。（摘自《C语言名题精选百则（技巧篇）》，冼镜光编著，机械工业出版社，2005年7月第一版第一次印刷）。代码如下： #include #include using namespace std; int main() { int N; cin>>N; int *Location=new int[N+1]; for(int i=0;i!=N+1;++i) Location[i]=i; Location[1]=0; //筛除部分int p,q,end; end=sqrt((double)N)+1; for(p=2;p!=end;++p) { if(Location[p]) { for(q=p;p*q<=N;++q) { if(Location[q]) { for(int k=p*q;k<=N;k*=p) Location[k]=0; } } } } int m=0; for(int i=1;i!=N+1;++i) { if(Location[i]!=0) { cout<

sap中sq01的使用方法.docx

1.概述 SAP Query为我们提供了三种Query工具 SAP Query、InfoSet (Ad Hoc) Query、QuickViewer。通常在不特指的情况下我们所说的Query Report就是SAP Query，因为它的功能较其它两个工具更加强大些。 InfoSet Query的特点： ? Quick Viewer所生成的报表是用户自定义的报表，只能由此用户自己使用、维护。 ? Quick Viewer只能使用存于数据库内的数据，不能进行计算（除小计、累计）。? 提供与 SAP内部工具如EIS，ABC，ALV及外部工具如 Word，Excel接口。? 无须也无法利用用户组、Functional area统一管理 ? 无法传输 SAP Query的特别： ? Query的管理包括建立 Functional area（功能区）和User Group（用户组），并将功能区分配到相应的用户组中去。 ? Functional area（功能区）中定义query中需引用的表和字段。 ? 只有当一个用户属于至少一个用户组才可以创建、运行 Queries。一个用户可以属于几个用户组。用户组中的用户享有相同的权力。 ? 当 Functional area（功能区）分配给了某用户组，该用户组的成员即可以访问此功能区。 ? 一个 Functional area（功能区）可以分配给多个用户组；多个Functional area（功能区）可以分配给一个用户组。 ? Queries通常为特定的用户组和特定的功能区而建立。这个用户组的用户可以访问所有分配给这个用户组的Queries。 2.实例操作讲解SAP Query 简单来讲，制作SAP Query可以用到SQ03(创建用户组并分配用户)、SQ02(创建InfoSet并分配到用户组)、SQ01(在分配好的用户组中使用信息集来生成Query Reporting)这三个事务代码。 2.1 创建用户组并分配用户 Tcode：SQ03

用筛法求出100以内的全部素数

例6、用筛法求出100以内的全部素数，并按每行五个数显示。 【问题分析】 ⑴把2到100的自然数放入a[2]到a[100]中（所放入的数与下标号相同）； ⑵在数组元素中，以下标为序，按顺序找到未曾找过的最小素数minp,和它的位置p（即下标号）； ⑶从p+1开始，把凡是能被minp整除的各元素值从a数组中划去（筛掉），也就是给该元素值置0； ⑷让p=p+1，重复执行第②、③步骤，直到minp>Trunc(sqrt(N)) 为止； ⑸打印输出a数组中留下来、未被筛掉的各元素值，并按每行五个数显示。 用筛法求素数的过程示意如下（图中用下划线作删去标志）： ① 2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100 ｛置数｝ ② 2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100 {筛去被2整除的数} ③ 2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100 {筛去被3整除的数} …… 2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100 {筛去被整除的数} Program Exam53; const N=100; type xx=1 .. N; {自定义子界类型xx（类型名）} Var a: array[xx] of boolean; i,j: integer; Begin Fillchar(a,sizeof(a),true); a[1] := False; for i:=2 to Trunc(sqrt(N)) do if a[I] then for j := 2 to N div I do a[I*j]:= False; t:=0; for i:=2 to N do if a[i] then Begin write(a[ i ]:5); inc(t); if t mod 5=0 then writeln end; End. 【例3】输入十个正整数，把这十个数按由大到小的顺序排列（将数据按一定顺序排列称为排序，排序的算法有很多，其中选择排序中的“简单选择排序”是一种较简单的方法） 分析：要把十个数按从大到小顺序排列，则排完后，第一个数最大，第二个数次大，……；因此，我们第一步可将第一个数与其后的各个数依次比较，若发现，比它大的，则与之交换，比较结束后，则第一个数已是最大的数。同理，第二步，将第二个数与其后各个数再依次比较，又可得出次大的数。如此方法进行比较，最后一次，将第九个数与第十个数比较，以决定次小的数。于是十个数的顺序排列结束。 例如下面对5个进行排序，这个五个数分别为829105。按选择排序方法，过程如

魔方20秒快速法入门教程

我的魔方解法----简化的CFOP法 魔方快速还原方法中Fridrich的CFOP (Cross+F2L+OLL+PLL魔方吧叫“20秒还原法”)法是很主流的方法，还原速度很快但是有100多个公式要掌握。通过在“魔方吧”的学习，我整理出一个简化的CFOP 方法，这样只需记15个公式就可实现较快的还原魔方。要更快一点，就再多记1个架“十”字公式，本法推荐记16个公式(教程中红色显示)。这比起完整CFOP的（41+57+21=119）个公式来说已大大减轻了负担，本法是一种“中级”的魔方解法，不太适合初学者（初学者还是推荐最简单、公式最少的基本层先法）和只想学会还原的朋友。主要适合学习对象为：1）不愿意记非常多的公式又想还原得快一点的朋友；2）完整CFOP方法的初学者。此法可作为Fridrich方法（CFOP）的入门教程。 一、技术路线 第一、二层采用基本层先的方法（第二层3个公式），第三层采用CFOP法的棱和角一起翻色（此时采用先架棱“十”字，再后用7个OLL公式来完成顶面翻色），然后调棱位置，再调角位置（由于是简化所以不能同时调角和棱的位置），其实就就是把PLL的角和棱分开来完成。 二、具体步骤 1、第一层 现在的目标是在顶上完成第一层（顶层），用架好棱十字（要求顶层四棱的相对位置正确，也就是棱块的侧面色要和对应魔方面的中心块的颜色相同如图1）再对好四角的方法。此步的小技巧是：可以将目标棱块和对应的中心块并到一起后再参加架“十”字。加好顶棱十字后再对好四个角（位置和色向都要对）详细方法可见魔方吧“笑面虎”方法中的内容，因为简单可以自己想出来不再多说了。这时就完在了一层。图2 图1图2 附1：架“十”字另一方法是先将四个目标棱块都转上去架起“十”字，再来调节它们的相对位置，这时要用到两个公式中的一个： 1、相对棱对调R’L U2 R L’ 2、相邻棱对调R’U’R U R’ 2、第二层 由于中心块已固定，所以第二层只有四个棱块没解决了，现在就来解决它。先将第一步中做好的的魔方倒过来（如图3）一般都会出现下面（图4、5、6）几种情况，（有一种特殊情况是四个中层棱都在不在顶上，而是相对错位，此时只要用图4图5的公式做一次便可出现4、5的情况）用对应的公式来解决它们。 图示公式录像

三阶魔方公式口诀图解[新手快速入门]

三阶魔方玩法与口诀 目录 一、前言_________________________________________________ - 2 - 二、认识公式 _____________________________________________ - 2 - 三、拧魔方的步骤与口诀 ___________________________________ - 4 - 步骤一、完成一层_______________________________________ - 4 - （一）完成第一层十字________________________________ - 4 - （二）完成第一层角块________________________________ - 5 - 步骤二、完成第二层_____________________________________ - 7 - 步骤三、完成顶层_______________________________________ - 8 - （一）顶层十字______________________________________ - 8 - （二）顶层平面_____________________________________ - 10 - （三）顶层角块_____________________________________ - 11 - （四）顶层棱块_____________________________________ - 12 -

一、前言 魔方是3x3x3的三阶魔方，英文名Rubik's cube。是一个正 6 面体，有6种颜色，由26块组成，有8个角块；12个棱块；6个中心块（和中心轴支架相连）见下图： 学习魔方首先就要搞清它的以上结构，知道角块只能和角块换位，棱块只能和棱块换位，中心块不能移动。 魔方的标准色： 国际魔方标准色为：上黄－下白，前蓝－后绿，左橙－右红。 二、认识公式

素数的线性筛法

素数的线性筛法 //整体思想是从自然数 2 开始与所有之前已经确定的素数相乘后的数标记为合数就能把素数一个不漏地找出来 #include #include

魔方教程公式口诀

魔方教程 前言 我们常见的魔方是3x3x3的三阶魔方，英文名Rubik's cube。是一个正6 面体，有6种颜色，由26块组成，有8个角块；12个棱块；6个中心块（和中心轴支架相连）见下图： （图1） 学习魔方首先就要搞清它的以上结构，知道角块只能和角块换位，棱块只能和棱块换位，中心块不能移动。 魔方的标准色： 国际魔方标准色为：上黄－下白，前蓝－后绿，左橙－右红。 （见图2）注：（这里以白色为底面，因为以后的教程都将以白色为底面， 为了方便教学，请都统一以白色为准）。 （图 2） 认识公式 （图3）（图4） 公式说明：实际上就是以上下左右前后的英文的单词的头一个大写字母表示

（图5） （图6）

（图7） （图8）步骤一、完成一层

首先要做的是区分一层和一面：很多初学者对于“一面”与“一层”缺乏清楚的认识，所以在这里特别解释一 下。所谓一层,就是在完成一面(如图2的白色面)的基础上,白色面的四条边,每条边的侧面只有一种颜色,图(2). 如图（1）中心块是蓝色，则它所在面的角和棱全都是蓝色，是图(2)的反方向 图（3）和（4）则是仅仅是一面的状态,而不是一层 ! （1） （2） （3） （4） 注：图（2）和（4）分别是图（1）和（3）的底面状态 想完成魔方，基础是最重要的，就像建筑一样，魔方也如此，基础是最重要的。 由于上文提到过中心块的固定性，这一性质，在魔方上实质起着定位的作用，简单的说就是中心块的颜色就代表它所在的面的颜色。 一、十字（就是快速法中的CROSS ） 第一种情况如图所示： 公式为R2 第二种情况如图所示： （白色下面颜色为橙色，为方便观察，特意翻出颜色） 橙白块要移到上右的位置，现在橙白块在目标位置的下面。但其橙色片没有和橙色的中心块贴在 （橙色下面颜色为白色，为方便观察，特意翻出颜色）

素数的几种判断方法和实现

PS：本来没有决心把这个东西写完的，结果早上写到一半，出去吃个饭，没保存，回来手一抖直接关掉了，好不容易写了一大半了，只能重新写了，坑爹啊，但就是这个插曲，本来还没有决心的我，一下子却坚定了信念，一点要把这个东西写完。就这样开始吧 BY：Lee 下面，我们重新开始 ═══════════════════════════════════════════ 如何判断一个数是否是素数呢 ═══════════════════════════════════════════也许你会认为这是一个简单的问题，但事实上，世界上任何一个问题，都没有你想象中的那么简单1 + 1 是否等于2 ，这便是一个简单而又复杂的问题，呵呵。 突然想把这个东西换一种风格来写了，就这样扯淡扯下去吧。扯的时候文章中多少有内容来自于网络，没有侵权的意思，如果作者看到还请见谅。 ═══════════════════════════════════════════下面正式进入正题 ═══════════════════════════════════════════ 一、朴素判断素数 ═══════════════════════════════════════════1. 这种方法被誉为笨蛋的做法： 一个数去除以比它的一半还要大的数，一定除不尽的，这还用判断吗？？ 很容易发现的，这种方法判断素数，对于一个整数n，需要n-2 次判断，时间复杂度是O(n)在n非常大或者测试量很大的时候，这种笨蛋做法肯定是不可取的。

2. 改进一下下小学生的做法： 3. 再改进一下聪明的小学生的做法 对于一个小于n的整数X，如果n不能整除X,则n必定不能整除n/X。反之相同一个明显的优化，就是只要从2枚举到√n 即可。 因为在判断2的同时也判断了n/2。到√n时就把2到n-1都判断过了。 在这里，这个聪明的小学生还用了i*i <= n 来代替sqrt（n）， 这里是避免了调用函数sqrt（），其消耗时间很大， 特别是在大量数据测试的时候消耗很明显。 这个算法的时间复杂度，与最前面的笨蛋做法就好多了， 不过这里好像用sqrt()也没问题啊，，，，这个就不太清楚了。 但是做一个测试发现，如果是这样额话，每一次判断都要计算i*i，

魔方20秒快速法入门解法及16个公式

20秒魔方快速入门解法 我的魔方解法----简化的CFOP法 魔方快速还原方法中Fridrich的CFOP (Cross+F2L+OLL+PLL魔方吧叫“20秒还原法”)法是很主流的方法，还原速度很快但是有100多个公式要掌握。通过在“魔方吧”的学习，我整理出一个简化的CFOP 方法，这样只需记15个公式就可实现较快的还原魔方。要更快一点，就再多记1个架“十”字公式，本法推荐记16个公式(教程中红色显示)。这比起完整CFOP的（41+57+21=119）个公式来说已大大减轻了负担，本法是一种“中级”的魔方解法，不太适合初学者（初学者还是推荐最简单、公式最少的基本层先法）和只想学会还原的朋友。主要适合学习对象为：1）不愿意记非常多的公式又想还原得快一点的朋友；2）完整CFOP方法的初学者。此法可作为Fridrich方法（CFOP）的入门教程。 一、技术路线 第一、二层采用基本层先的方法（第二层3个公式），第三层采用CFOP法的棱和角一起翻色（此时采用先架棱“十”字，再后用7个OLL公式来完成顶面翻色），然后调棱位置，再调角位置（由于是简化所以不能同时调角和棱的位置），其实就就是把PLL的角和棱分开来完成。 二、具体步骤 1、第一层 现在的目标是在顶上完成第一层（顶层），用架好棱十字（要求顶层四棱的相对位置正确，也就是棱块的侧面色要和对应魔方面的中心块的颜色相同如图1）再对好四角的方法。此步的小技巧是：可以将目标棱块和对应的中心块并到一起后再参加架“十”字。加好顶棱十字后再对好四个角（位置和色向都要对）详细方法可见魔方吧“笑面虎”方法中的内容，因为简单可以自己想出来不再多说了。这时就完在了一层。图2 附1：架“十”字另一方法是先将四个目标棱块都转上去架起“十”字，再来调节它们的相对位置，这时要用到两个公式中的一个： 2、第二层 由于中心块已固定，所以第二层只有四个棱块没解决了，现在就来解决它。先将第一步中做好的的魔方倒过来（如图3）一般都会出现下面（图4、5、6）几种情况，（有一种特殊情况是四个中层棱都在不在顶上，而是相对错位，此时只要用图4图5的公式做一次便可出现4、5的情况）用对应的公式来解

线性筛法求素数的原理与实现

何为线性筛法，顾名思义，就是在线性时间内（也就是O（n））用筛选的方法把素数找出来的一种算法，没用过线性筛素数法的人可能会奇怪，用遍历取余判定素数不是也是线性时间的吗，没错，但是确切的说线性筛法并不是判定素数的，而是在线性时间内求出一个素数表，需要判定是否是素数的时候只要看该数是否在表内就可以瞬间知道是不是素数。 比如想求10000以内的素数，定义表int a[10000]，进行线性筛选后，a[n]的值就代表n是不是素数，a[n]如果是1，就代表n是素数，a[n]如果是0，就代表n不是素数，这就是查表。再判定其他的素数也是一样，不用再做任何计算。 而如果用遍历取余，那么每判定一个数都要从头开始再遍历一遍，而线性筛法只在开始一次性运算完，以后只要查表即可，查表通常只需要1条语句。所以如果你的程序从始至终只需要判定那么几次素数那么用遍历取余即可，但是如果需要多次判定素数，而且这个数还不是很小的话，那么线性筛法就会体现出巨大的优越性来。 线性筛法的核心原理就是一句话：每个合数必有一个最大因子（不包括它本身），用这个因子把合数筛掉，还有另一种说法（每个合数必有一个最小素因子，用这个因子筛掉合数，其实都一样，但是我觉得这种方法不太容易说明，这种方法我会在最后给出简略说明）。这个很容易证明：这个小学就知道合数一定有因子，既然是几个数，就一定有最大的一个。最大因子是唯一的，所以合数只会被它自己唯一的因子筛掉一次，把所有合数筛掉后剩下的就全是素数了。 先假设一个数i，一个合数t，i是t最大的因数，t显然可能并不唯一（例如30和45的最大因数都是15）。那么如何通过i知道t呢，t必然等于i乘以一个比i小的素数。先来说这个数为什么一定要比i小，这很显然，如果是i乘上一个比它大的素数，那么i显然不能是t 最大的因子。再来说为什么要是素数，因为如果乘上一个合数，我们知道合数一定可以被分解成几个素数相乘的结果，如果乘上的这个合数x=p1*p2*……，那么 t = i * x = i * p1 * p2……很显然p1* i也是一个因数，而且大于i。所以必须乘上一个素数。 比i小的素数一定有不少，那么该乘哪一个呢，既然t不唯一，那么是不是都乘一遍呢？很显然不行，虽然t不唯一，但全乘一遍很显然筛掉的数的数量远远超过合数的数量。我们先给出结论： 任意一个数i = p1*p2*……*pn，p1、p2、……pn都是素数，p1是其中最小的素数， 设T 为i * M的积（显然T就成了一个合数），也就是T = i * M，（M是素数，并且M<=p1）,那么T的最大的因数就是i。 是的，乘上的数要小于等于i最小的质因数。