Python 中笨拙的階乘

我們知道，正整數 n 的階乘是小於或等於 n 的所有正整數的乘積。因此，factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1。我們將嘗試找到一個笨拙的階乘：使用遞減順序的整數，我們將乘法運算替換為固定的運算旋轉：乘法 (*)、除法 (/)、加法 (+) 和減法 (-)，按此順序。

笨拙的階乘類似於 clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1。但是，這些運算仍然使用算術的常規運算順序：我們先執行所有乘法和除法步驟，然後再執行任何加法或減法步驟，並且乘法和除法步驟從左到右處理。我們使用的除法是地板除法，例如 10 * 9 / 8 等於 11。這保證結果為整數。

例如，如果輸入是 10，則結果將為 12，因為 12 = 10 * 9 / 8 + 7 – 6 * 5 / 4 + 3 – 2 * 1

為了解決這個問題，我們將遵循以下步驟：

定義運算陣列，並存儲運算子 [* / + -]，建立一個空棧，並將 N 推入棧中。
index := 0
N 減 1
當 N 不為 0 時
- 如果 operation[index] = *，則
  - 如果棧頂元素 >= 0，則將棧頂元素更新為 top_element := N * top_element
  - 否則，棧頂元素 := -1 * |N * 棧頂元素|
- 否則，如果 operation[index] 為 /，則
  - 如果棧頂元素 >= 0，則將棧頂元素更新為 top_element := top_element / N
  - 否則，棧頂元素 := -1 * |棧頂元素 / N|
- 否則，如果 operation[index] 為 +，則
  - 將 N 插入棧中
- 否則，將 (-1 * N) 插入棧中
- index := (index + 1) mod 運算陣列的長度
- N 減 1
返回棧元素的總和。

讓我們看看下面的實現以更好地理解：

示例

線上演示

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

輸入

輸出

Arnab Chakraborty

更新於：2020年4月30日

1K+ 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習