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])

CodePudding user response：

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] or

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.

CodePudding user response：

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])