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

输入

10

输出

12

更新于：2020年4月30日

1K+ 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告