Python 中笨拙的阶乘

pythonserver side programmingprogramming

众所周知,正整数 n 的阶乘是所有小于或等于 n 的正整数的乘积。因此阶乘(10)= 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1。我们将尝试找到一个笨拙的阶乘:使用按降序排列的整数,我们将乘法运算换成固定的循环运算:按此顺序乘法(*)、除法(/)、加法(+)和减法(-)。

笨拙的阶乘类似于笨拙的阶乘(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 推入堆栈。
  • 索引 := 0
  • 将 N 减少 1
  • 当 N 不为 0 时:
    • 如果操作 [索引] = *,则
      • 如果堆栈顶部元素 >= 0,则将堆栈顶部元素更新为 top_element := N * top_element
      • 否则堆栈顶部元素 := -1 * |N * 堆栈顶部元素|
    • 否则,如果操作 [索引] 为 /,则
      • 如果堆栈顶部元素 >= 0,则更新堆栈顶部元素为 top_element := top_element / N
      • 否则堆栈顶部元素 := -1 * |堆栈顶部元素 / N|
    • 否则,如果操作 [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

相关文章