Python中的笨拙阶乘
众所周知,正整数n的阶乘是所有小于或等于n的正整数的乘积。因此factorial(10)=10*9*8*7*6*5*4*3*2*1。我们将尝试找到一个笨拙的阶乘:使用整数以递减的顺序,将乘法运算换成a固定旋转操作:按此顺序乘(*),除(/),加(+)和减(-)。
笨拙的阶乘就像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
为了解决这个问题,我们将遵循以下步骤-
定义opeartions数组,并存储运算符[*/+-],创建一个空堆栈,然后将N推入堆栈。
索引:=0
将N减少1
当N不为0时:
将N插入堆栈
如果堆栈顶部元素>=0,则将堆栈顶部元素更新为top_element:=top_element/N
否则,栈顶元素:=-1*|栈顶元素/N|
如果堆栈顶部元素>=0,则将堆栈顶部元素更新为top_element:=N*top_element
否则,堆栈顶部元素:=-1*|N*堆栈顶部元素|
如果operation[index]=*,则
否则,如果operation[index]为/,则
否则,如果operation[index]为+,则
否则将(-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