I have a simple question about an algorithm. I'm not an algorithmic specialist and I need some help to write a particular one.
I will stay a bit "schematic" because I know that my algorithm will stop and that it is valid (I still have to formally prove it, but anyway), I just need to know how to write it correctly and efficiently.
The idea is the following :
Initialization :
I have two input variables $a_{0}$ and $b_{0}$ and I set $c_{0} = \min \{a_{0}, b_{0}\}$.
Treatment :
IF $a_{0} = b_{0}$, THEN STOP (output variable : $c_{0}$)
OTHERWISE $a_{1} = \min \{c_{0}, f(c_{0})\}$, $b_{1} = \min \{c_{0}, g(c_{0})\}$, $c_{1} = \min \{a_{1}, b_{1}\}$
IF $a_{1} = b_{1}$, THEN STOP (output variable : $c_{1}$)
OTHERWISE $a_{2} = \min \{c_{1}, f(c_{1})\}$, $b_{2} = \min \{c_{1}, g(c_{1})\}$, $c_{2} = \min \{a_{2}, b_{2}\}$
etc.
until a certain $n \in \mathbb{N}$ (which exists, as I said, it is not the point here), where $f$ and $g$ are some mappings.
My problem is that, obviously, I cannot know the step $n$ where the algorithm must stop and that it is not well written here...
I tried to write it in that way, can you tell me if it is correct ?
Initialization :
Two input variables $a$ and $b$
$c = \min \{a, b\}$
Treatment :
WHILE $a \neq b$
$a := \min \{c, f(c)\}$
$b := \min \{c, g(c)\}$
$c := \min \{a, b\}$
ENDWHILE
STOP (output variable : $c$)
I apologize in advance if the different terms (IF, WHILE, etc.) are not well used and I hope you'll understand the idea.
Thank you !
I think you meant to perform a while loop, but you needed an iteration index, I would propose the following:
Initialization :
Input variables $a_{0}$ and $b_{0}$, and set $c_{0} = \min \{a_{0}, b_{0}\}$, a tolerance $\varepsilon>0$ and an index $k=0$.
Treatment :
While $|a_{k} - b_{k}| > \varepsilon$:
$\,\,\,\,a_{k+1} = \min \{c_{0}, f(c_{0})\}$
$\,\,\,\,b_{k+1} = \min \{c_{0}, g(c_{0})\}$
$\,\,\,\,c_{k+1} = \min \{a_{1}, b_{1}\}$
$\,\,\,\,k=k+1$
(End of while loop)
Return $c_{k}$