3. Rekursion

Rekursion

  • M

    Hi, ich schon wieder...:)
    Kann mir jemand sagen wie ich dies mittels Schleife und Rekursion für die Berechnung von Pn(x) für ein zulässiges x und n algorithmiere?
    P1(x)=1
    P2(x)=x;
    n*Pn(x)=(2n-1)x*P_n-1(x)-(n-1)P_n-2(x) für n=2,3... .
    Schöne Grüße
    MIkka

    0
  • V
     

    rek:
int P(int n,double x){
  if(n<=1) //Fehler in Deiner Definition. P2(x) bezieht sich auf P0(x)! Deshalb <=
    return 1;
  else
    return (2*n-1)*x*P(n-1,x)-(n-1)*P(n-2,x);
}
iter:
int P(int n,double x){
  double a,b=1,c={rechne selber P1(x) aus};
  for(int i=2;i<=n;++i){
    a=b,b=c;
    c=(2*n-1)*x*b-(n-1)*a;
  }
  return c;
}
    0
  • ?

    n*Pn(x) = ...

    Also noch durch n teilen.

    0
  • M

    Oh cool...vielen Dank!
    VG Mikka

    0
  • W

    mikka7019 schrieb:

    P1(x)=1
    P2(x)=x;
    n*Pn(x)=(2n-1)x*P_n-1(x)-(n-1)P_n-2(x) für n=2,3... .

    Hallo Mikka,

    wie nennt man dieses Polynom? Es sieht so ähnlich aus wie das Tschebyschow-Polynom und hat auch ähnliche Eigenschaften. Gibt es einen Namen für Pn(x)?

    Gruß
    Werner

    0
  • B

    Ich glaub das sind die Legendre-Polynome.

    0
  • P

    Ist N bei dir eine Compilezeit-Konstante? Dann kann man den Laufzeit-Aufwand der Rechnungen deutlich reduzieren.

    Laut Wikipedia ist eine alternative Darstellung der Polynome

    P\_n(x) = \sum\_{k=0}^{k_\mathrm{MAX}} (-1)^k \frac{(2n - 2k)! \ x^{n-2k}}{(n-k)! \ (n-2k)! \ k! \ 2^n}$$, mit $$k_\text{MAX} = \begin{cases} \frac{n}{2} & n \ \text{gerade}\\ \frac{n-1}{2} & n \ \text{ungerade} \end{cases}

    Das heißt $$P_n(x) = \sum_{k=0}^{k_\mathrm{MAX}} c(n,k) x^{n-2k}$$ mit $$c(n,k) = (-1)^k \frac{(2n - 2k)! }{(n-k)! \ (n-2k)! \ k! \ 2^n}$$

    c rekursiv definiert ergibt $$c(n,k) = c(n,k-1) \cdot -\frac{(n-k+1) \ (n-2k+1)(n-2k+2)}{k(2n-2k+1)(2n-2k+2)}$$ für k>0 und

    c(n,0)=(2n)!n! n!2nc(n,0) = \frac{(2n)!}{n! \ n! 2^n}

    Definiert man jetzt $$s(n,i,x) = \sum_{k=0}^{i} c(n,k) x^{n-2k}$$ und $$s(n,0,x) = c(n,0) x^{n}$$
    Kann man auch s rekusiv definieren als $$s(n,i,x) = c(n,i) x^{n-2i} + s(n,i-1,x)$$

    als einziges "schwierig" zu berechnen (im Sinne von C++-Compilezeit Berechnungen) ist dabei jetzt noch die Potenz von x, die durch eine Hilfsvariable y=x^(n-2i+2) gelöst werden kann:

    s(n,i,x,y) = c(n,i) y + s(n,i-1,x, y\*x\*x)

    Alles zusammen ergibt sich

    P\_n(x) = s(n,k\_\mathrm{MAX},x,y_0)$$ mit $$y_0 = \begin{cases} 1 & n \ \text{gerade}\\ x & n \ \text{ungerade} \end{cases}

    Als Template-möglichst-Meta-Programm:

    template <int N>
struct fac { enum {value = N*fac<N-1>::value}; };
template <>
struct fac<0> {enum {value = 1};};

template <int N, int I>
struct S
{
  const static int c = -( (N-I+1)*(N-2*I+1)*(N-2*I+2) ) / ( I*(2*N-2*I+1)*(2*N-2*I+2) ) * S<N, I-1>::c;

  static double eval(double x, double y)
  {
    return c*y + S<N, I-1>::eval(x, y*x*x);
  }
};

template <int N>
struct S<N,0>
{
  const static int c = fac<2*N>::value / (fac<N>::value * fac<N>::value * (1<<N));

  static double eval(double x, double y)
  {
    return c*y;
  }
};

template <int N>
struct P
{
  double operator()(double x)
  {
    return S<N,N/2>::eval(x, (N%2) ? 1.0 : x);
  }
};

    Hier werden jetzt bei gegebenem N alle Koeffizienten zur Compilezeit ausgerechnet, zur Laufzeit gibts pro Berechnung N Multiplikationen und N/2 Additionen.

    Ungetestet und evtl. noch mit Fehlern...

    0
Anmelden zum Antworten