RFÉK - Rekurzív függvény értékének kiszámítása

Before you start...

Rekurzív formulával adott függvény kiszámítása

Legyen \(H\) egy tetszőleges halmaz, \(0<k\in\N,\;F:\Z\times H^k\to H;\quad t_0,t_{-1},\dots,t_{-k+1}\in H;\quad f\in\Z\to H\) parciális függvény, hogy

\[ \begin{array}{rcl} f(m)&=&t_0 \\ f(m-1)&=&t_{-1}\\ \vdots&&\vdots \\ f(m-k+1)&=&t_{-k+1} \\ \end{array} \]

valamint \(\forall i\ge m:\)

\[ f(i+1)=F(i+1,\;f(i),\;\ldots,\;f(i-k+1)) \]

Specifikáció

\(\begin{array}{} A = &\Z&\times&\Z&\times&H&\times&H&\times&\ldots&\times&H \\ & m && n && y && t_0 && \ldots && t_{-k-1}\end{array}\)

\(\begin{array}{} B = &\Z&\times&\Z&\times&H&\times&\ldots&\times&H \\ & m' && n' && t_0' && \ldots && t'_{-k-1}\end{array}\)

\(Q:\big(m=m'\;\land\;n=n'\;\land\;n\ge m\;\land\;t_0=t_0'\;\land\;\ldots\;\land\;t_{-k+1}=t'_{-k+1}\big)\)

\(R:\big(Q\;\land\;y=f(n)\big)\)

Levezetési elemek

\(P=\Big(Q\,\land\,i\in[m..n]\,\land\,y=f(i)\,\land\,y_{-1} = f(i-1)\,\land\,\ldots\,\land\,y_{-k+1}=f(i-k+1)\Big)\)

\(Q'=\Big(Q\,\land\,i=m\,\land\,y=t_0\,\land\,y_{-1} = t_{-1}\,\land\,\ldots\,\land\,y_{-k+1}=t_{-k+1}\Big)\)

\(Q''= \Big(Q\,\land\,i+1\in[m..n]\,\land\,y=f(i+1)\,\land\,y_{-1} = f(i)\,\land\,\ldots\,\land\,y_{-k+1}=f(i-k+2)\Big)\)

\(\pi=(i\ne n)\)

\(t= (n-i)\)

Kód

\[\begin{array}{|lc|} \hline &i,y,y_{-1},\ldots,y_{-k+1}:=m,t_0,t_{-1},\ldots,t_{-k+1}\\ \hline & i\ne n \\ &\begin{array}{|l} \hline y,y_{-1},\ldots,y_{-k+1}:=F(i+1, y,\ldots, y_{-k+1}),y,\dots, y_{-k+2} \\ \hline i:= i + 1 \end{array}\\ \hline \end{array}\]