Jump to content

A Looping Problem


e(ho0n3

Recommended Posts

How many times does the print statement execute?

 

for i[1] = 1 to n do
 for i[2] = 1 to min(i[1], n - 1) do
   for i[3] = 1 to min(i[2], n - 2) do
     .
      .
       for i[n - 1] = 1 to min(i[n - 2], 2) do
         for i[n] = 1 to 1 do
           print i[1], i[2], ..., i[n]

 

I get a headache just from looking at it...

Link to comment
Share on other sites

If [MATH]fib(n)[/MATH] is the [MATH]n^{th}[/MATH] fibonacci number where the recurssion [MATH]fib(n)=fib(n-1)+fib(n-2)[/MATH] holds. Also you take [MATH]fib(1)=fib(2)=1[/MATH].

Next if given [MATH]n[/MATH], the number of times the loop runs is [MATH]P(n)[/MATH]..........

 

Your solution is [MATH]P(n)=fib(2n-1)[/MATH]

 

I can't write the full solution using LaTex due to obvious reasons of it being slightly cumbersome, but still if you want I can try and explain it sometime later.......

Nice question though, took me almost half an hour to solve it.

Link to comment
Share on other sites

I got the following reccursion :-

 

[MATH]P(n)=\Sigma_{i=1}^{n-1}P(i) + P(n-1)[/MATH]

 

Along with base cases of [MATH]P(1)=1[/MATH] and [MATH]P(2)=2[/MATH]

I think the problem stems from you definition of P(n). What exactly is your definition? I have something similar to what you have (and ended up with your exact same solution, i.e. P(n) = f(2n - 1)), but then I realized I made a mistake, that being the definition of P(n).

 

Note there are n for loops, with the top for loop going from 1 to n. This is different from n for loops going from 1 to k, k < n, which is still different from k for loops, k < n, the top for loop going from 1 to n.

 

So let me define P(a,b) as the number of times the print statement is executed given a for loops, the top for loop executing from 1 to b. I then get the following recurrence:

 

P(n,n) = 2P(n-1,n-1) + P(n-1,n-2) + P(n-1,n-3) + ... + P(n-1,1)

 

This is as far as I can go since I don't know how to solve such a recurrence relation. Maybe you can shine some light on this.

Link to comment
Share on other sites

I defined [MATH]P(n)[/MATH] as the number of print statements executed in n loops, with the top most going from 1 to n. Alternatively, it is the required answer in the case when you have n loops. The fact is that whenever there shall be n loops the outer most will go from 1 to n. There is no need to define it as [MATH]P(n,n)[/MATH] because all the terms that come out in the recurrance you mentioned can be reduced some [MATH]P(i)[/MATH]. In fact, [MATH]P(n-1,i)=P(i)[/MATH] for [MATH]i \leq n-1[/MATH] .

Link to comment
Share on other sites

It won't simply because you can't write a program with a generic number 'n' of loops. You would need to keep modifying the number of loops which would be very tedious and then need to figure out a pattern in the numbers that you get out......a hard task.

Link to comment
Share on other sites

I defined [MATH]P(n)[/MATH] as the number of print statements executed in n loops, with the top most going from 1 to n. Alternatively, it is the required answer in the case when you have n loops. The fact is that whenever there shall be n loops the outer most will go from 1 to n. There is no need to define it as [MATH]P(n,n)[/MATH] because all the terms that come out in the recurrance you mentioned can be reduced some [MATH]P(i)[/MATH]. In fact, [MATH]P(n-1,i)=P(i)[/MATH] for [MATH]i \leq n-1[/MATH'] .

Let's look at the second for loop, i.e. then one that goes from 1 to min(i[1], n - 1). When the i[1] = 1 (first iteration), the second loop goes from 1 to 1. This is your P(1). Then P(1) is "number of print statements executed in 1 loop, with the top most going from 1 to 1". This is clearly not true. It should be "the number of print statements executed in n - 1 for loops with the top most going from 1 to 1", which is just P(n-1,1).

 

For i[1] = 2 (next iteration), the second loop goes from 1 to 2. This is your P(2). Then P(2) is "number of print statements executed in 2 loops, with the top most going from 1 to 2". This is clearly not true either. It should be "the number of print statements executed in n - 1 for loops with the top most going from 1 to 2", which is just P(n-1,2). And so on.

 

Convinced?

 

E1 (echo-one) have you actualy tried to run it on a computer and used the "Trace" command to find out?

I'm supposed to solve this problem without the aid of a computer. As I said before, I know what the answer is; I just don't know how to derive it. The pattern isn't "pretty" so it would be very, very hard to guess from looking at a couple of numbers in the sequence.

Link to comment
Share on other sites

Let's look at the second for loop, i.e. then one that goes from 1 to min(i[1], n - 1). When the i[1] = 1 (first iteration), the second loop goes from 1 to 1. This is your P(1). Then P(1) is "number of print statements executed in 1 loop, with the top most going from 1 to 1". This is clearly not true. It should be "the number of print statements executed in n - 1 for loops with the top most going from 1 to 1", which is just P(n-1,1).

When i[2] goes from 1 to 1, all subsequent loops will also go from 1 to 1. For example, i[3] will go to min{i[2], n-2} which is 1, similarly i[4] will also go to 1. As a result the print statement is executed exactly once hence [MATH]P(1)=P(n-1,1)=1[/MATH]

 

Similarly if you work out for the case when the outermost loop reaches its 2nd iteration, then i[2] will go from 1 to 2. Again if you try to work out you'll see that from the 4th loop inwards all loops will only ever go from 1 to 1 making them redundant. As a result you can reduce the problem to just the loop numbers 2 and 3, which is just the case of P(2).

 

You can discuss generally and show [MATH]P(i)=P(n-1,i)[/MATH]

Link to comment
Share on other sites

OK, I'm convinced (I just did a proof by induction and it worked). But anyways, your solution (the one with the fibonacci equation) is wrong. I suggest we start looking for another route towards solving this. I was thinking of looking at the number generated by the print statement in each iteration.

 

In general we have that n ≥ i[1], n - 1 ≥ i[2], ... 1 ≥ i[n], and i[k] > 0 for k = 1, ..., n. Hmm...this is to ugly (and tricky). I'm becomming exasperated.

 

OK. We have that:

 

[math]P(n) = P(n-1) + \sum_{i=1}^{n-1}P(i)[/math]

[math]P(n-1) = P(n-2) + \sum_{i=1}^{n-2}P(i)[/math]

 

Then,

 

[math]P(n) - P(n-1) = P(n-1) + \sum_{i=1}^{n-1}P(i) - P(n-2) - \sum_{i=1}^{n-2}P(i)[/math]

 

Simplifying and solving for P(n) gives (and this seems strange to me),

 

[math]P(n) = 3P(n-1) - P(n-2)[/math]

 

This looks like the fibonacci recurrence doesn't it! Unfortunately this is all bogus (it doesn't work for n = 4).

Link to comment
Share on other sites

What doesn't work for n=4 ?

Atleast if I put in [MATH]fib(2n-1)=P(n)[/MATH] and [MATH]n=4[/MATH] then I get :-

[MATH]fib(2*4-1)=3*fib(2*3-1)-fib(2*2-1)[/MATH]

[MATH]fib(7)=fib(5)*3 - fib(3)[/MATH]

[MATH] fib(7)=13 \ldots fib(5)=5 \ldots fib(3)=2 [/MATH]

So it holds !

Link to comment
Share on other sites

P(n) is equal to the nth Catalan number. If you don't believe that P(4) is 14, here is printout of a program a made in perl for n = 4:

 

1 1 1 1

2 1 1 1

2 2 1 1

2 2 2 1

3 1 1 1

3 2 1 1

3 2 2 1

3 3 1 1

3 3 2 1

4 1 1 1

4 2 1 1

4 2 2 1

4 3 1 1

4 3 2 1

 

There are 14 number combinations above.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.