0

Consider the following pseudo-code:

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

I'm searching for the explicit map that returns cont in function of g and h. I've tried with

cont = m*(g - 1) + [h - (g - 1)]

but this formula works only in the case m = 2.


observation for the following cycle

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

the value of cont in function of g and h is given by cont = m*(g - 1) + h

5
  • 4
    Try plotting the possible combinations of g and h in a coordinate system, and marking those where the counter is incremented. You'll find that the relevant cases form one half of a rectangle. That should tell you what the total number of increments is. Commented Jan 15, 2021 at 11:19
  • 2
    Hint: g and h are defined within that code, m is the only input
    – Caleth
    Commented Jan 15, 2021 at 11:20
  • Just to be sure: I don't want count how many increment there are in the two cycles (which are m*(m+1)/2) but I want to find the map that returns the value of cont in given g and h. For example, if m=3, what is the value of cont at the iteration withg=2 and h=3?
    – Gost91
    Commented Jan 15, 2021 at 14:37
  • 1
    So you want a container of (g, h, count) tuples? Or a function that - unlike the one you sketched - maps (m, g, h) -> count?
    – Useless
    Commented Jan 15, 2021 at 15:07
  • I'm searching for a mathematical function that given m, g, h compute the value of count. I'm sorry for my imprecision, I hope to have clarified my problem.
    – Gost91
    Commented Jan 15, 2021 at 15:12

1 Answer 1

2

Updated to reflect the question "Actually what I'm searching is an answer to the following question: given m, if suddenly I interrupt the cycle in a point where g and h has some specific value, e.g. g=2 and h=3, what is the value assumed by cont?" given in a comment.

If we stop the execution at the point where g = g' and h = h', we can represent that using the following algorithm:

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

(I'm assuming we stop execution after cont = cont + 1 is executed one last time. If that's not desired, you can simply subtract 1 from the final answer.)

We can do the same thing again:

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

Factor out the constants for simplicity:

cont = (g' - 1) * (m + 1) + h' - g' + 1
for g = 1,...,g' - 1
     cont = cont - g
end for

And we can use the triangle number trick again now:

cont = (g' - 1) * (m + 1) + h' - g' + 1 - (g' - 1) * g' / 2

Rearranging everything to get the final closed-form formula:

cont = (g' - 1) * (m - g' / 2) + h'

The original answer

As @Caleth mentioned, m is the only free variable in your code.

First:

for a = 1,...,b
        cont = cont + 1
end for

is equivalent to

cont = cont + b

And by extension:

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

is equivalent to

cont = cont + m - g + 1

We can now simplify the code to:

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

Factoring out the parts that don't depend on g:

cont = m * (m + 1)
for g = 1,...,m
         cont = cont - g
end for

we can change that to:

cont = m * (m + 1)
subtract = 0
for g = 1,...,m
         subtract = subtract + g
end for
cont = cont - subtract

You can now see that the final values of subtract for consecutive values of m for the triangular numbers. Wikipedia says n * (n + 1) / 2 as a closed-form formula for the nth triangle number. Plugging that in gives:

we can change that to:

cont = m * (m + 1)
subtract = m * (m + 1) / 2
cont = cont - subtract

which means we end up with:

cont = m * (m + 1) / 2
3
  • Thank you Jasmijn for your answer, but I'm not searching for the final value of the counter. I know that I have formulated the problem in a confusing way. Actually what I'm searching is an answer to the following question: given m , if suddenly I interrupt the cycle in a point where g and h has some specific value, e.g. g=2 and h=3, what is the value assumed by cont? I view cont as a mathematical function of g and h, where m plays the role of an external parameter.
    – Gost91
    Commented Jan 15, 2021 at 17:01
  • Ah, alright. I'll amend my answer then.
    – Jasmijn
    Commented Jan 15, 2021 at 21:39
  • Your solution works like a charm, thank you Jamsijn for your help.
    – Gost91
    Commented Jan 16, 2021 at 14:08

Not the answer you're looking for? Browse other questions tagged or ask your own question.