MFF UK / Ústav teoretické fyziky / Tomáš Ledvinka
Přednášky
. . . . . . . . . . . . . . . . . . . . . . . . . .
Programování pro fyziky (1.r)
  Úvod
  Programy a algoritmy
  Píšeme program
  Píšeme program II
  Procedury a funkce
  Malujeme funkce
    Malujeme funkci (skoro)
    Používáme GNUPLOT
    Matematický vzoreček
    Řady
    Rekurentní vztahy
    Polynomy
    Iterační algoritmy
  Chyby. Typy I.
  Typy II. Pole a Záznamy
  Pole II.Řetězce.Soubory.
  Gnuplot.Interpolace...
  Matice. Velké O...
  Fronta,Zásobník. Postscript
  Bin. soubory, ...
  Ukazatele,Objekty, ...
Maple pro fyziky (3.r)
Klasická elektrodynamika (2.r)
Vybrané partie OTR

Cvičení
. . . . . . . . . . . . . . . . . . . . . . . . . .
Programování pro fyziky (1.r)
Teoretická mechanika (2.r)
Klasická elektrodynamika (2.r)


Věda
. . . . . . . . . . . . . . . . . . . . . . . . . .
Diskové zdroje v OTR
Hyperbolické systémy v OTR


Kontakt
. . . . . . . . . . . . . . . . . . . . . . . . . .
Email
Konzultační hodiny


Ostatní
. . . . . . . . . . . . . . . . . . . . . . . . .
Mallorca
Ze společnosti

Rekurentní vztahy

Nejjednodušším příkladem je samozřejmě funkce faktoriál:.

n! = n (n-1)!
0! = 1

Jiným standardním příkladem je Fibonacciho posloupnost:

F(n) = F(n-2)+F(n-1)
F(0) = 0
F(1) = 1

Jakkoli je nasnadě použít pro výpočet prostředky rekurse jazyka Pascal, nebudeme je v toěchto případech používat. Programová rekurse je znázorněna pro faktorial takto:

a odpovídá následujícímu kódu:

function faktorial(a:integer):real; 
begin   if a<=1 then faktorial := 1         
else faktorial := a*faktorial(a-1);
end;

Pro Fibonacciho posloupnost takto

kde je nevhodnost programové rekurse naprosto zřejmá.
Cvicení: Vyzkoušejte si napsat rekurentní versi funkce Fibonacci(n : integer).
Cvicení: Kolikrát se zavolá funkce Fibonacci, kdyz se takto pokoušíme spočíst Fibonacci(6)?

Jak tedy převedeme matematický rekurentní vztah na návod pro počítač? Nejjednodušší je samozrejme případ funkce faktorial

function faktorial(a:integer):real;
var i : integer;
       s : real
begin
  s:=1;
  for i:=2 to a do s := s*i;
  faktorial := s;
end;

Takto zapsaný postup má jediný háček: vrací rozumnou hodntu i pro záporné hodnoty parametru a. Podobně jako by nebylo nejlepší, kdyby nám sqrt vracelo nulu pro záporné parametry (dáváme přednost krachu programu), měli bychom přidat test na záporné hodnoty a a program případně ukončit.
Cvičení: Zkuste na cyklus prevést výpocet funkce Fibonacci.

Zde si ukázeme, jak převést na cyklus složitější variantu Fibonacciho vztahu. Zadání, které nalezneme v učebnici fyziky zní:

kde Pn(x) je tzv. Legendreuv polynom a během studia jej mnohokrát potkáte. Pro nás je úloha omezena na nalezení hodnoty Pn(x) pro dané celé n>=0 a reálné x. Jak je vidět, je potřeba rozlišit případy n=0, n=1 a zbytek, kdy použijeme uvedenou formulku opakovaně (n-1)-krát. Zde je jedna z variant:

function LegendreP( m : integer; x : real ) : real;
var Pn2, Pn1,Pn : real;
n : integer;
begin Pn := 1; {P0(x)}
if m = 1 then Pn := x; {P1(x)}
Pn2 := 1;
Pn1 := x;
for n := 2 to m do begin Pn := ((n+n-1)*x*Pn1 - (n-1)*Pn2 )/n; Pn2:= Pn1; {Pn->Pn1->Pn2} Pn1:= Pn; end;
LegendreP := Pn;
end;

Příkaz cyklu for se nám postará o zvyšování n od 2 až do m, ale s každým zvýšením hodnoty n je potřeba také posunout hodnoty v proměnných, které si "pamatují" hodnoty Pn-2 a Pn-1.

Pro vykreslení použijeme následující program

program MalujLegendreovyPolynomy;

const xa = -1;
xb = 1;
N = 400;

function LegendreP( m : integer; x : real ) : real;
...... viz výše ....

var k,i : integer;
x,y : real;

begin
for k := 0 to 12 do begin
for i := 0 to N do begin
x := xa + (xb-xa)*i/N;
writeln(x,' ',LegendreP(k,x));
end; {graf pro pevne x}
writeln; {vypiš dva prázdné rádky}
writeln;
end; {dalsi k}
end.

Ten vypíše tabulku hodnot Funkce P0(x), poté dva prázdné řádky, pak tabulku hodnot funkce P1(x), pak dva prázdné řádky atd. až nakonec tabulku funkčních hodnot P12(x). Zadáme-li programu guplot příkaz plot "legendre.dat", kde soubor legndre.dat obsahuje výstup našeho programu, dostaneme následující obrázek

Protože jsme ale oddělili jednotlivé tabulky hodnot dvěma prázdnými řádky, můžeme si z toho zmatku vybrat jen ty křivky, které nás zajímají a to pomocí slova index následujícího za názvem datového souboru. Např.

plot "legendre.dat" index 1,"legendre.dat" index 2,"legendre.dat" index 3, "legendre.dat" index 12

nám vymaluje tabulky hodnot polynomu P1, P2, P3 a P12. Ještě se k tomu vrátíme v povídání o polích, ale je dobré vědet, že první sekci dat odpovídá index 0 a tak shodou okolností se index sekce shoduje s řádem Legendreova polynomu.

 

Pozor: někdy se může stát, že rekurentní vztah podobný výše uvedenému pro Legendrovy polynomy nefunguje, neboť s rostoucím n může do závratných výšek narůst úplně drobná počátecní nepřesnost. Diskuse tohoto jevu je ovšem mimo možnosti této prednášky.


.