A tananyag vége felé közeledve kitekintünk a továbblépési lehetőségekre. Olyan feladatokat nézünk át, amelyek alapvetően más tantárgyak témakörébe tartoznak, de a Programozási alapismeretek tantárgy eszközkészletével tökéletesen megoldhatóak.
Ebben a leckében egy közelítő számítást mutatunk be, amely egy egyszerű másolás-függvényszámítás tétel alkalmazás (a matematikai háttértudáson kívül).
Számítsuk ki Gyök(2) értékét!
Probléma: irracionális számot biztosan nem tudunk ábrázolni a számítógépen!
Új feladat: Számítsuk ki azt a P,Q egész számpárt, amire P/Q elég közel van Gyök(2)-höz!
Probléma: Mi az, hogy „elég közel”?
Ötlet: |P2/Q2-2|<E, ahol E egy kicsi pozitív valós szám.
Állítás: az alábbi sorozat értéke Gyök(2)-höz tart, ha n tart végtelenhez (most ezt nem bizonyítjuk):
xn+1:=0,5*(xn+2/xn)
Pell-egyenlet: P2-N*Q2=4 végtelen sok megoldása van, ha N nem négyzetszám.
N=2 esetén:
Ha xn=Pn/Qn alakú, akkor xn+1:=0,5*(xn+2/xn)=(Pn2-2)/(Pn*Qn)=Pn+1/Qn+1 szintén megoldása a Pell-egyenletnek.
Pn/Qn→Gyök(2) (n→∞), így pl. P0=6726, Q0=4756 esetén 17 lépés alatt az eredmény 1000000 jegyre lesz pontos. (Jó P0=6, Q0=4 is.)
(P0,Q0) megkeresése:
(P,Q):=(1,1)
Ciklus amíg P2-2*Q2≠4
Ha P2-2*Q2<4 akkor P:=P+1 különben Q:=Q+1
Ciklus vége
Eljárás vége.
Közelítés(P,Q):
(P0,Q0) megkeresése
Ciklus amíg P*P-2*Q*Q≤E*Q*Q
Q:=P*Q; P:=P*P-2
Ciklus vége
Eljárás vége.
Tehát csak egész számokkal kell dolgozni, szorzás és kivonás műveletre van szükség.
Tekintse meg az alábbi animációt, amelyben összefoglaljuk a lecke lényegét!