Feladat: I.78 Korcsoport: - Nehézségi fok: -
Füzet: 2004/április, 235. oldal  PDF  |  MathML 
Témakör(ök): Feladat

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Egy nevezetes függvény Ackermann nevéhez fűződik, aki a függvények kiszámíthatóságával, bonyolultságával kapcsolatosan vizsgálódott. A róla elnevezett kétváltozós függvény különös érdekessége, hogy minden ,,normális'' függvénynél gyorsabban nő, és csak első néhány ,,tagjára'' találtak eddig zárt formulát.
Definíciója:

A(n;m)={m+1,ha  n=0A(n-1;1),ha  n>0  és  m=0A(n-1;A(n;m-1))ha  n>0  és  m>0,
ahol n és m nemnegatív egészek.
Készítsünk táblázatot (i78.xls), amely az Ackermann függvény értékeit számolja az alábbi formában (a #HIV! érték lehet ott, ahol nem tudjuk kiszámolni):
 
m\n012340123513123513#HIV!234729#HIV!345961#HIV!45611125#HIV!56713253#HIV!67815509#HIV!789171021#HIV!8910192045#HIV!91011214093#HIV!101112238189#HIV!1112132516381#HIV!12131427#HIV!#HIV!