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