% -*- coding: iso-8859-2 -*-
\documentclass[a4paper]{article}
\usepackage{progm}
\analpacks
\analoldal{2. feladatsor, 74. feladat}
\begin{document}
\noindent
\emph{Feladat:} Adjunk meg egy olyan $k$ számot, amire az
(adott) $n$ természetes szám bináris alakjának $k$-adik helyiértékén
$1$-es áll!

\def\div{\text{ div }}

\emph{Specifikáció:}\\
$A = \alatt{\N}{n} \times \alatt{\Z}{k}$\\
$B = \alatt{\N}{n'}$\\
$Q = ( n=n' )$\\
$R = ( Q \es k\ge 0 \es (f(k) \bmod 2)=1)$, ahol
\begin{align*}
f&\colon[-1, 0] \cup \N\to\N \\
f(-1)&:=2n \\
\forall i\ge0&\colon f(i):=F(i, f(i-1)) \\
F(k,z)&:=z \div2
\end{align*}

Visszavezetés a lin. ker. 2-re, azt tudjuk, hogy az $f$ függvény
valamilyen nagy argumentumra páratlan számot ad vissza, hiszen minden
természetes $n$ szám esetén, $n$-et újra és újra 2-vel egész osztva
páratlan számot kapunk, legkésőbb akkor, amikor a kapott páratlan szám
az 1.  Megjegyezzük, hogy a feladat nem volt egyértelmű annak
tekintetében, hogy mit jelent a $k$-adik helyiérték, ezért mi a
számunkra kényelmes módon értettük, azaz a bináris felírásban jobbról
és 0-tól számoljuk a számjegyeket.  A program lefutása után egy plusz
szekvenciával a kapott értékhez hozzá lehet adni 1-et, ha azt
szeretnénk, hogy pl. a 12-nél (1100) a válasz 3 és ne 2 legyen.

Az $n$ a visszavezetés paramétere, az $m$-et a 0 konstanssal helyettesítjük.

\begin{tabular}{ccc}
  feladat &  & lin. ker. 2 \\
  \hline
  $0$ & \knyil & $m$ \\
  $k$ & \knyil & $i$ \\
  $(f(j) \bmod 2) = 1$ & \knyil & $\beta(j)$
\end{tabular}

\begin{stuki}[7cm]
  \stm{l,k:=\hamis,-1}
  \begin{WHILE}{2}{\stm{\nem l}}
    \stm{l:=(f(k+1) \bmod 2)=1}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}

Az $f$ függvény rekurzívan definiált, ezért alkalmazhatjuk a
rekurzívan definiált függvény változóval való helyettesítésének
programtranszformációs módszerét, amivel kapjuk a nem megengedett
értékadást már nem tartalmazó végeredmény programot:

\begin{stuki}[7cm]
  \stm{z,l,k:=2n,\hamis,-1}
  \begin{WHILE}{3}{\stm{\nem l}}
    \stm{z:=z\div2}
    \stm{l:=(z \bmod 2)=1}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}

\end{document}