Espressione esplicita di un contatore

[boolilood]

Ho delle difficoltà nel determinare l'espressione esplicita del contatore del seguente pseudo-codice

Codice:

cont = 0
for g = 1, ..., m
     for h = g, ..., m
          cont = cont +1
     end for
end for


ho provato con la seguente funzione
\begin{equation}\text{cont}(g,h)\triangleq m(g-1)+[h-(g-1)]\end{equation}
ma questa funziona solamente nel caso $m=2$.

[apatriarca]

Devi usare i numeri triangolari.

Hai infatti la seguente sommatoria:
\[ \mathrm{cont}_m = \sum_{g=1}^m \sum_{h=g}^m 1 \]
La sommatoria interna è semplicemente il numero di valori da \(g\) a \(m\) (suppongo compresi entrambi) per cui:
\[
\begin{align*}
\mathrm{cont}_m &= \sum_{g=1}^m (m - g + 1) \\
&= \sum_{g=1}^m (m + 1) - \sum_{g=1}^m g \\
&= m\,(m + 1) - \frac{m\,(m + 1)}{2} \\
&= \frac{m\,(m + 1)}{2}
\end{align*}
\]

[boolilood]

ti ringrazio per la risposta, mi sapresti aiutare a trovare il valore di $\text{cont}_m$ in funzione di $g$ ed $h$?
Per esempio, se $m=6$ allora
\begin{equation}\begin{aligned}
\text{cont}_6(g=3, h=4)&=13\\
\text{cont}_6(g=5, h=5)&=19
\end{aligned}\end{equation}
vorrei trovare la regola generale per mappare $g$, $h$ in $\text{cont}_m$.

[boolilood]

Provo a spiegarmi meglio rendendo le cose un po' più concrete.


esempio

Tanto per fissare le idee, consideriamo il caso $m= 6$.
In questo caso la funzione $\text{cont}_m(\cdot,\cdot)=\text{cont}_6(\cdot,\cdot)$ è data dalla seguente lookup table
\[
\begin{array}{cc|c}
g & h & \text{cont}_6 \\
\hline
1 & 1 & 1 \\
1 & 2 & 2 \\
1 & 3 & 3 \\
1 & 4 & 4 \\
1 & 5 & 5 \\
1 & 6 & 6 \\
2 & 2 & 7 \\
2 & 3 & 8 \\
2 & 4 & 9 \\
2 & 5 & 10 \\
2 & 6 & 11
\end{array}
\quad
\begin{array}{cc|c}
g & h & \text{cont}_6 \\
\hline
3 & 3 & 12 \\
3 & 4 & 13 \\
3 & 5 & 14 \\
3 & 6 & 15 \\
4 & 4 & 16 \\
4 & 5 & 17 \\
4 & 6 & 18 \\
5 & 5 & 19 \\
5 & 6 & 20 \\
6 & 6 & 21
\end{array}
\]

magari può essere utile rappresentare $\text{cont}_6(\cdot, \cdot)$ in forma "triangolare"
\[\begin{array}{c |cccccc}
\text{g\h} & 1 & 2 & 3 & 4 & 5 & 6 \\
\hline
1 & 1 & 2 & 3 & 4 & 5 & 6\\
2 & & 7 & 8 & 9 & 10 & 11\\
3 & & & 12 & 13 & 14 & 15\\
4 & & & & 16 & 17 & 18\\
5 & & & & & 19 & 20\\
6 & & & & & & 21\\
\end{array}
\]


osservazione

per il seguente ciclo

Codice:

cont = 0
for g = 1, ...,m
     for h = 1, ...,m
          cont = cont +1
     end for
end for


l'espressione esplicita del contatore è la seguente
\begin{equation}\text{cont}_m(g,h)=m(g-1)+h\end{equation}

[apatriarca]

Fissiamo quindi i due valori \(G\) e \(H\) delle variabili a cui vuoi sapere il valore del contatore. In questo caso dovresti avere la seguente sommatoria:
\[
\begin{align*}
\mathrm{cont}_m(g=G, h=H) &= \sum_{g=0}^{G-1}\,\sum_{h=g}^{m} 1 + \sum_{h=G}^{H} 1 \\
&= \sum_{g=0}^{G-1} (m - g + 1) + (H - G + 1) \\
&= (G - 1)\,(m + 1) - \frac{(G - 1)G}{2} + H - G + 1 \\
&= H + (G - 1)\,\left( m - \frac{G}{2}\right)
\end{align*}
\]