Chương trình tìm số lượng lệnh gọi hàm tối thiểu để tạo mảng đích bằng Python

Giả sử chúng ta có định nghĩa hàm sau:

def modify(arr, op, index):
   if op == 0:
      arr[index] += 1
   if op == 1:
      for i in range(len(arr)):
         arr[i] *=2

Chúng ta phải tìm số lượng lệnh gọi hàm tối thiểu cần thiết để tạo một số mảng nhất định từ một mảng 0 có cùng kích thước?

Vì vậy, nếu đầu vào là nums =[1,5,3], thì đầu ra sẽ là 7 vì ban đầu tất cả các phần tử đều là 0, [0,0,0]

• Ở bước đầu tiên, tăng phần tử thứ hai lên 1, vì vậy mảng là [0,1,0]

• Nhân đôi phần tử thứ hai để tạo thành [0,2,0]

• Tăng phần tử thứ ba lên 1, vì vậy mảng là [0,2,1]

• Nhân đôi các phần tử từ chỉ mục 1 đến 2, vì vậy mảng là [0,4,2]

• Tăng tất cả các phần tử lên 1 [tổng cộng ba hoạt động tại đây]

vì vậy cần có tổng số 3 + 4 =7 hoạt động.

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

• ans:=một mảng có hai phần tử đều là 0

• đối với mỗi n trong số, thực hiện

  • gấp đôi:=0

  • trong khi n khác 0, thực hiện

    • nếu n là số lẻ thì

      • n:=thương số của n / 2

      • gấp đôi:=double + 1

    • nếu không,

      • n:=n - 1

      • ans [0]:=ans [0] + 1

  • ans [1]:=tối đa ans [1] và gấp đôi

• trả về tổng tất cả các phần tử của ans

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

Ví dụ

def solve(nums):
   ans = [0, 0]
   for n in nums:
      double = 0
      while(n):
         if not n%2:
            n = n//2
            double+=1
         else:
            n-=1
            ans[0]+=1
            ans[1] = max(ans[1], double)
   return sum(ans)
nums = [1,5,3]
print(solve(nums))

Đầu vào

[1,5,3]

Đầu ra

7