CODEWITHSUNDEEP
pythonalgorithm
Marina Golovanova
Marina Golovanova

Reputation: 24

Write an algorithm for the sequence

Calculate the n member of the sequence given by the formulas

a[2 * n] = a[n] + 1
a[2 * n + 2] = a[2 * n + 1] - a[n]
a[0] = a[1] = 1

n > 0

I've tried a lot of variants, but I can't find correct one.

n = int(input())

a = [0 for i in range(n + 3)]

a[0] = a[1] = 1

i = 1
while i * 2 + 2 < n + 3:
    a[2 * i] = a[i] + 1;
    a[2 * i + 1] = a[2 * i + 2] + a[i]
    a[2 * i + 2] = a[2 * i + 1] - a[i]
    i += 1

print(a[n])

Upvotes: 0

Views: 245

Answers (3)

Y.T.
Y.T.

Reputation: 2739

We should first compute the expected output for the first few numbers to let us have an idea what the sequence is like first,

a[0] = a[1] = 1

Substitute n = 1 in the first recurrence relation gives a[2] = a[1] + 1 = 2

Substitute n = 1 in the second recurrence relation gives a[4] = a[3] - a[1]

But a[4] = a[2] + 1 = 3 according to the first recurrence relation, so 3 = a[3] - 1, which gives a[3] = 4

We have a = {1, 1, 2, 4, 3, ... }
Your program gives a = {1, 1, 2, 1, 3, ...}

What went wrong in your program?

We notice that when i = 1, the line a[2 * i + 1] = a[2 * i + 2] + a[i] evaluates to a[3] = a[4] + a[1]. However, at that time, a[4] is not evaluated yet, causing an incorrect output.

The issue, therefore, lies in how you order your statements in the while loop. Make sure that statements in your loop only make use of values that will not be changed later.

How should we do that?

if we manipulate the second recurrence relation as follows:

a[2 * i + 2] = a[2 * i + 1] - a[i]
a[2 * i + 1] = a[2 * (i + 1)] + a[i]

Using the first recurrence relation, we have
a[2 * i + 1] = a[i + 1] + 1 + a[i]

which should resolve the issue since 2 * n + 1 > n + 1 for all positive n.

After modifying the second statement, you check that every element in a is computed and you should be done.

Note

One more thing to note is that the third statement is redundant since the first statement covers all even elements in a already.

In fact, a more efficient approach, in particular a logarithmic solution exist2 if you only have to calculated the nth member of the sequence.

Upvotes: 1

Paul Hankin
Paul Hankin

Reputation: 58221

Your second formula gives a[2n+2] = a[2n+1] - a[n]. That can be rewritten: a[2n+1] = a[2n+2] + a[n] which is a[n+1] + a[n] + 1 from the first formula.

We can use this to write a simple dynamic programming algorithm that runs in linear time:

def A(n):
    a = [1] * (n+1)
    for i in range(2, n+1):
        if i%2 == 0:
            a[i] = a[i//2] + 1
        else:
            a[i] = a[i//2] + a[i//2+1] + 1
    return a[n]

However, we can note that we can solve this in logarithmic time, by noting that we can compute both a[n] and a[n+1] from a[n//2] and a[n//2+1].

If n is even, then a[n]=a[n//2]+1 and a[n+1]=a[n//2]+a[n//2+1]+1. And if n is odd, then a[n]=a[n//2]+a[n//2+1]+1 and a[n+1]=a[n//2+1]+1. These are just applications of the formulas we have already.

This gives us this solution:

def A2(n):
    if n == 0:
        return 1, 1
    if n == 1:
        return 1, 2
    a, b = A2(n//2)
    if n % 2 == 0:
        return a+1, a+b+1
    else:
        return a+b+1, b+1

Note that this returns 2 values, but for all n, A(n) == A2(n)[0].

Upvotes: 0

Marina Golovanova
Marina Golovanova

Reputation: 24

I found decision

n = int(input())
k = n if n % 2 == 0 else n + 1
a = [None for i in range(k + 1)]

a[0] = a[1] = 1

def fill_list(a):
  while None in a:
    i = 1
    while i * 2 <= k:
      if a[i] != None:
        a[2 * i] = a[i] + 1
      i += 1
    
    i = 1
    while i * 2 + 2 <= k:
      if a[i * 2 + 2] != None and a[i] != None:
        a[i * 2 + 1] = a[i * 2 + 2] + a[i]
        
      i += 1

    
fill_list(a)
print(a[n])

Upvotes: 0

Related Questions