Thread: A triple for-loop from our exam...

First of all, please move this thread if it is in totally wrong place.

Anyway, I took today in our university an exam in Discrete Mathematics. The question itself was easy and I know the answer too (by counting it with computer), but what is the formula to solve this? Here's the code as VBA code:

Code:

Sub forlooptask()
    Dim i As Long, j As Long, k As Long, x As Long
    
    For i = 1 To 200
        For j = 1 To i - 1
            For k = 1 To j
                x = x + 1
            Next k
        Next j
    Next i
    
    Debug.Print x
End Sub

the result is 1333300. The question is: How does the equation for solving this go? Where does that 200 go to?

Onhan huonossa!

1) That j-loop is troublesome. First it does a brief descending count, from 1 to zero. THEN it starts a more expected path of growth. It's not wrong, per se. It just looks a little funny.

2) Why is 'x' not initialized? I guess VB doesn't mind, but I would onsider it bad form.

3) Formula for what? You want a brief, convenient expression to caclulate the total?

Other than that, it looks pretty straight-forward.

Originally Posted by TKHunny

Onhan huonossa!

1) That j-loop is troublesome. First it does a brief descending count, from 1 to zero. THEN it starts a more expected path of growth. It's not wrong, per se. It just looks a little funny.

2) Why is 'x' not initialized? I guess VB doesn't mind, but I would onsider it bad form.

3) Formula for what? You want a brief, convenient expression to caclulate the total?

Other than that, it looks pretty straight-forward.

I could initialize that x to 0, but it wouldn't make difference. I just coded it quickly, the main thing here is that math problem. The exam paper itself has it like:

For i:=1 to 200 do
For j:=1 to i-1 do
For k:=1 to j do
Print "Hei"
How many times "Hei" is printed?

So the answer is 1333300, but how do I calculate that by numbers? I'm pretty sure it's about combinatory, but how?

For k= 1 to j- 1
x= x+1
Next k

Just adds 1 to x j-1 times: the result is x+ j-1- it just adds j- 1 to x.

And it does that for j running form 1 to i-1: That is, we will have x+ 1+ 2+ 3+ ...+ i-2. it is well know that so the result of the j loop will be x+ \frac{(i-1)i){2}[/tex]. (These are the "triangular numbers" 1, 3, 6, 10, ...)

Now, it does that for i going from i to 200 so it will be x+ 1+ 3+ 6... and the result will be x plus the sum of the first 199 (because it is "i-1", not "i" in the formula) triangular numbers.

To get those, look at .

is easy- it is just 1/2 the sum above- .

And is also well known: it is

I agree with TKHunny- it is peculiar that x is not initialized- without knowing its initial value we cannot know what the result is. I'ts been a long time since I programmed with Basic- and never with "Visual Basic" but in the dark, distant past, some versions of Basic assumed initial values of 0 (a really bad practice!). Is that still true?

Originally Posted by jflurrie

First of all, please move this thread if it is in totally wrong place.

Anyway, I took today in our university an exam in Discrete Mathematics. The question itself was easy and I know the answer too (by counting it with computer), but what is the formula to solve this? Here's the code as VBA code:

Code:

Sub forlooptask()
    Dim i As Long, j As Long, k As Long, x As Long
    
    For i = 1 To 200
        For j = 1 To i - 1
            For k = 1 To j
                x = x + 1
            Next k
        Next j
    Next i
    
    Debug.Print x
End Sub

the result is 1333300. The question is: How does the equation for solving this go? Where does that 200 go to?

EDIT: Apparently, I am unable to read an entire thread before posting. I therefore appologise for reapeating, well, everything, but this took me a while to type up (I'm a slow typer) so I'm refusing that to be (entirely) wasted time! So behold! my post...

Code:

    For i = 1 To 200
        For j = 1 To i - 1
            For k = 1 To j
                x = x + 1
            Next k
        Next j
    Next i

becomes

Code:

    For i = 1 To 200
        For j = 1 To i - 1
              x=x+j
        Next j
    Next i

because adding 1 on j times is the same as adding on j. Now, in this bit you are just summing up all the numbers between 1 and (i-1). There is a well-known formula for this,

. Here, a = (i-1). Thus, your code becomes,

Code:

    For i = 1 To 200
         x = x + i(i-1)/2
    Next i

and I suppose you can just write this as . If you want to do it more, expand it so you will have,



and then you can just plug in some formulas to evaluate these.

Originally Posted by HallsofIvy

For k= 1 to j- 1
x= x+1
Next k

Just adds 1 to x j-1 times: the result is x+ j-1- it just adds j- 1 to x.

And it does that for j running form 1 to i-1: That is, we will have x+ 1+ 2+ 3+ ...+ i-2. it is well know that so the result of the j loop will be x+ \frac{(i-1)i){2}[/tex]. (These are the "triangular numbers" 1, 3, 6, 10, ...)

Now, it does that for i going from i to 200 so it will be x+ 1+ 3+ 6... and the result will be x plus the sum of the first 199 (because it is "i-1", not "i" in the formula) triangular numbers.

To get those, look at .

is easy- it is just 1/2 the sum above- .

And is also well known: it is

I agree with TKHunny- it is peculiar that x is not initialized- without knowing its initial value we cannot know what the result is. I'ts been a long time since I programmed with Basic- and never with "Visual Basic" but in the dark, distant past, some versions of Basic assumed initial values of 0 (a really bad practice!). Is that still true?

At least in VBA I usually initialize them anyway, but this one I posted here made in like 30 seconds so I really didn't pay that much attention on that program, I just thought to show that the program returns a certain result.

What comes to your and Swlabr's answers, they look pretty good to me and I think I understood it now.

Thank you!

Originally Posted by jflurrie

First of all, please move this thread if it is in totally wrong place.

Anyway, I took today in our university an exam in Discrete Mathematics. The question itself was easy and I know the answer too (by counting it with computer), but what is the formula to solve this? Here's the code as VBA code:

Code:

Sub forlooptask()
    Dim i As Long, j As Long, k As Long, x As Long
    
    For i = 1 To 200
        For j = 1 To i - 1
            For k = 1 To j
                x = x + 1
            Next k
        Next j
    Next i
    
    Debug.Print x
End Sub

the result is 1333300. The question is: How does the equation for solving this go? Where does that 200 go to?

Are you sure the code isn't

Code:

Sub forlooptask()
    Dim i As Long, j As Long, k As Long, x As Long
    
    For i = 1 To 200
        For j = 1 To i - 1
            For k = 1 To j - 1
                x = x + 1
            Next k
        Next j
    Next i
    
    Debug.Print x
End Sub

with k running from 1 to j-1?

With this change, the loop generates all combinations of the integers from 1 to 200 taken 3 at a time.

Originally Posted by awkward

Are you sure the code isn't

Code:

Sub forlooptask()
    Dim i As Long, j As Long, k As Long, x As Long
    
    For i = 1 To 200
        For j = 1 To i - 1
            For k = 1 To j - 1
                x = x + 1
            Next k
        Next j
    Next i
    
    Debug.Print x
End Sub

with k running from 1 to j-1?

With this change, the loop generates all combinations of the integers from 1 to 200 taken 3 at a time.

No, k runs from 1 to j. We had in class version

i = 1 to 10
j = 1 to i
k = 1 to j

and that gives

In an earlier exam from 2006 this same teacher has asked also the version you suggested. I guess the big idea is to understand the difference of all those versions.