Chương trình tìm giá trị tối đa trong mảng được tạo bằng Python

Giả sử chúng ta có một số n. Chúng ta phải tạo một mảng A có độ dài n + 1 theo cách sau -

A [0] =0
A [1] =1
A [2 * i] =A [i] nếu 2 <=2 * i <=n
A [2 * i + 1] =A [i] + A [i + 1] nếu 2 <=2 * i + 1 <=n

Cuối cùng, chúng ta phải tìm số lớn nhất trong số mảng.

Vì vậy, nếu đầu vào là n =5, thì đầu ra sẽ là 3 vì

A [0] =0
A [1] =1
A [2] =A [1] =1
A [3] =A [1] + A [2] =1 + 1 =2
A [4] =A [2] =1
A [5] =A [2] + A [3] =1 + 2 =3
A [6] =A [3] =2

Vì vậy, tối đa là 3

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

A:=một danh sách mới từ 0 đến n
đối với mỗi phần tử tôi trong A, thực hiện
- nếu tôi giống 0 hoặc tôi giống 1, thì
  - chuyển đến lần lặp tiếp theo
- ngược lại khi tôi là số chẵn thì
  - A [i]:=A [số nguyên của i / 2]
- nếu không,
  - A [i]:=A [số nguyên của i / 2] + A [(số nguyên của i / 2) + 1]
trả về phần tử tối đa của A

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

def solve(n):
   A = list(range(0,n+1))
   for i in A:
      if i == 0 or i == 1:
         continue
      elif i%2 == 0:
         A[i] = A[i//2]
      else:
         A[i] = A[i//2] + A[(i//2) + 1]
   return max(A)

n = 5
print(solve(n))

Chương trình tìm giá trị tối đa trong mảng được tạo bằng Python

Ví dụ (Python)

Đầu vào

Đầu ra