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

これを解決するには、次の手順に従います-

• opeartions配列を定義し、演算子[* / +-]を格納し、空のスタックを1つ作成して、Nをスタックにプッシュします。
• インデックス：=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