Printable View
How many times does the innermost loop execute:
I did the first few by hand to see if I noticed anything.Code:for k = 1 to n
for j = 1 to k
for i = 1 to j
#the inner loop
end for
end for
end for
Looking at Pascal's triangle I saw the numbers appear in the diagonal. Eventually I came up with the answer:
(n + 2) choose (n - 1)
But I don't know how I got there. Does this have anything to do with the Principle of Inclusion and Exclusion?
that can't be (n+2) or (n-1) iterations in that loop with "i" :D:D:DQuote:
Originally Posted by aarnold
i have question for you :D why don't compile this ? and is it ( k=1 ; k<= n or you need k<n ; k++ )
for n=2 there are 6 , for n=3 there is 18 , for n=4 there is 40 ... repetitions :D
lol for n = 50 there is 63 750 of executions of that loop :D
Hi, I'm assuming that I am calculating for k <= n.
A quick check with python gives the following results:
and here's Pascal's triangle:Code:>>> def iterate(n):
c = 0
for k in range(1, n + 1):
for j in range(1, k + 1):
for i in range(1, j + 1):
c = c + 1
print c
>>> iterate(1)
1
>>> iterate(2)
4
>>> iterate(3)
10
>>> iterate(4)
20
>>> iterate(5)
35
>>> iterate(6)
56
If the row and column's are 0-based, look at the n+2 row and the n-1 column and you get the number of iterations.Code:1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
So if n = 1, look at row 3, column 0: 1
n = 2, look at row 4, column 1: 4
n = 3, row 5, column 2: 10
etc.
I determined this to be (n+2) choose (n-1).
However, I don't think this is a mathematical enough answer.
hm...
and get totally something else :DCode:cin>> n ;
int iter = 0 ;
for (int k = 1 ; k<= n ; k++ ) {
for( int j= 1 ; j <= k ; j++ ) {}
for( int i =1 ; i< =j i ++ ) {}
iter++ ;}
cout << << "No." << iter << "." << i << endl;
Quote:
Originally Posted by aarnold
nth triangle number
nth tetrahedral number
The pattern continues. Notice that n+2-3 = n-1. (Combine this with the knowledge that.)
You can justify the triangular number formula by considering the handshake problem; given a group of n people, if everyone shakes everyone else's hand, how many handshakes took place? So the first person shakes n-1 hands. Add to that n-2 for the second person -- because if you added n-1 you would re-count the handshake with the first person. So you get (n-1) + n + ... + 1, which is the (n-1)st triangle number.
We can generalize as follows: Consider a set of n points, n > 2, such that no three points are collinear. How many triangles can we form by choosing vertices from these n points? Start with one point, and ask how many triangles can form with it. You get the (n-2)nd triangle number. (Because you are choosing any two points out of the n-1 remaining points, which is a problem we just solved above.) For the next point you get the (n-3)rd triangle number, etc.
There may be a cleaner way to state it, but that at least does the job.
For any value ofQuote:
Originally Posted by aarnold
the inner loop executes
For any value ofthe inner look executes
So the total number of executions of the inner code is
With a bit of jiggery-pokery this becomes:
CB
Here's that jiggery-pokery stuff:
![\sum_{k=1}^n \left[\sum_{j=1}^k j\right]=\sum_{k=1}^n\frac{k(k+1)}{2}=](http://latex.codecogs.com/png.latex?\sum_{k=1}^n \left[\sum_{j=1}^k j\right]=\sum_{k=1}^n\frac{k(k+1)}{2}=)