A triple for-loop from our exam...

Printable View

May 21st 2010, 03:28 AM
jflurrie

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?
May 21st 2010, 03:48 AM
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.
May 21st 2010, 04:06 AM
jflurrie

Quote:

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?
May 21st 2010, 04:40 AM
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 $1+ 2+ \cdot\cdot\cdot+ n= \frac{n(n+1)}{2}$ 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 $\frac{i(i+1)}{2}= \frac{i^2+ i}{2}= \frac{n^2}{2}+ \frac{n}{2}$ .

$\sum{i=1}^n \frac{i}{2}= \frac{1}\sum i$ is easy- it is just 1/2 the sum above- $\frac{n(n+1)}{4}$ .

And $\sum{n^2}$ is also well known: it is $\frac{n(n+1)(2n+1)}{6}$

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?
May 21st 2010, 04:51 AM
Swlabr

Quote:

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,

$\sum_a^na = \frac{a(a+1)}{2}$ . 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 $\sum_i^{200} \frac{i(i-1)}{2}$ . If you want to do it more, expand it so you will have,

$\frac{1}{2}\sum_i^{200} i^2 + \frac{1}{2}\sum_i^{200}i$

and then you can just plug in some formulas to evaluate these.
May 21st 2010, 08:14 AM
jflurrie

Quote:

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 $1+ 2+ \cdot\cdot\cdot+ n= \frac{n(n+1)}{2}$ 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 $\frac{i(i+1)}{2}= \frac{i^2+ i}{2}= \frac{n^2}{2}+ \frac{n}{2}$ .

$\sum{i=1}^n \frac{i}{2}= \frac{1}\sum i$ is easy- it is just 1/2 the sum above- $\frac{n(n+1)}{4}$ .

And $\sum{n^2}$ is also well known: it is $\frac{n(n+1)(2n+1)}{6}$

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!
May 21st 2010, 02:23 PM
awkward

Quote:

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 $\binom{200}{3} = 1,313,400$ combinations of the integers from 1 to 200 taken 3 at a time.
May 21st 2010, 02:46 PM
jflurrie

Quote:

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 $\binom{200}{3} = 1,313,400$ 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 $\binom{12}{3}$

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.