Giai thừa vụng về trong Python

Như chúng ta biết rằng giai thừa của một số nguyên dương n là tích của tất cả các số nguyên dương nhỏ hơn hoặc bằng n. Vì vậy, giai thừa (10) =10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1. Chúng tôi sẽ cố gắng tìm một giai thừa vụng về:sử dụng các số nguyên theo thứ tự giảm dần, chúng tôi hoán đổi các phép tính nhân cho một xoay vòng cố định của các phép toán:nhân (*), chia (/), cộng (+) và trừ (-) theo thứ tự này.

Giai thừa vụng về giống như vụng về (10) =10 * 9/8 + 7 - 6 * 5/4 + 3 - 2 * 1. Tuy nhiên, các phép toán này vẫn được áp dụng theo thứ tự các phép toán thông thường của số học:chúng ta thực hiện tất cả các phép nhân và các bước chia trước bất kỳ bước cộng hoặc trừ nào cũng như các bước nhân và chia được xử lý từ trái sang phải. Phép chia mà chúng tôi đang sử dụng là phép chia tầng sao cho 10 * 9/8 bằng 11. Điều này đảm bảo kết quả là một số nguyên.

Vì vậy, ví dụ:nếu đầu vào là 10, thì kết quả sẽ là 12, như 12 =10 * 9/8 + 7 - 6 * 5/4 + 3 - 2 * 1

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

xác định mảng thao tác và lưu trữ các toán tử [* / + -], tạo một ngăn xếp trống và đẩy N vào ngăn xếp.
chỉ mục:=0
giảm N đi 1
trong khi N không phải là 0:
- nếu hoạt động [index] =*, thì
  - nếu phần tử trên cùng của ngăn xếp là> =0, thì hãy cập nhật phần tử trên cùng của ngăn xếp thành top_element:=N * top_element
  - nếu không thì phần tử trên cùng ngăn xếp:=-1 * | N * phần tử trên cùng ngăn xếp |
- else nếu hoạt động [chỉ mục] là /, thì
  - nếu phần tử trên cùng của ngăn xếp là> =0, thì hãy cập nhật phần tử trên cùng của ngăn xếp thành top_element:=top_element / N
  - nếu không thì phần tử trên cùng của ngăn xếp:=-1 * | phần tử trên cùng của ngăn xếp / N |
- else nếu hoạt động [chỉ mục] là +, thì
  - chèn N vào ngăn xếp
- else insert (-1 * N) vào stack
- index:=(index + 1) mod độ dài của mảng hoạt động
- giảm N đi 1
trả về tổng của các phần tử ngăn xếp.

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

Ví dụ

class Solution(object):
   def clumsy(self, N):
      operations = ["*","/","+","-"]
      stack = []
      index = 0
      stack.append(N)
      N-=1
      while N:
         if operations[index] == "*":
            if stack[-1]>=0:
               stack[-1] *=N
            else:
               stack[-1] = -1*(abs(stack[-1])*N)
         elif operations[index] == "/":
            if stack[-1]>=0:
               stack[-1] //=N
            else:
               stack[-1] = -1*(abs(stack[-1])//N)
         elif operations[index] == "+":
            stack.append(N)
         else:
            stack.append(-1*N)
         index = (index+1) % len(operations)
         N-=1
      return sum(stack)
ob = Solution()
print(ob.clumsy(10))

Giai thừa vụng về trong Python

Ví dụ

Đầu vào

Đầu ra