Results 1 to 8 of 8

Math Help - A triple for-loop from our exam...

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    10

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Aug 2007
    From
    USA
    Posts
    3,111
    Thanks
    2
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2010
    Posts
    10
    Quote Originally Posted by TKHunny View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,444
    Thanks
    1863
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by jflurrie View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    May 2010
    Posts
    10
    Quote Originally Posted by HallsofIvy View Post
    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!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by jflurrie View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    May 2010
    Posts
    10
    Quote Originally Posted by awkward View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. simple for loop
    Posted in the Math Software Forum
    Replies: 0
    Last Post: September 29th 2011, 10:08 AM
  2. Matlab while loop, Please help!
    Posted in the Math Software Forum
    Replies: 1
    Last Post: April 23rd 2010, 02:14 AM
  3. Using a for loop and while loop.
    Posted in the Math Software Forum
    Replies: 1
    Last Post: April 19th 2010, 02:18 PM
  4. Loop invariants
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 13th 2009, 05:58 PM
  5. Matlab loop help
    Posted in the Math Software Forum
    Replies: 2
    Last Post: July 20th 2008, 11:47 AM

Search Tags


/mathhelpforum @mathhelpforum